iof-bird-daemon / nest / rt-table.c @ ae80a2de
History | View | Annotate | Download (59.7 KB)
| 1 |
/*
|
|---|---|
| 2 |
* BIRD -- Routing Tables
|
| 3 |
*
|
| 4 |
* (c) 1998--2000 Martin Mares <mj@ucw.cz>
|
| 5 |
*
|
| 6 |
* Can be freely distributed and used under the terms of the GNU GPL.
|
| 7 |
*/
|
| 8 |
|
| 9 |
/**
|
| 10 |
* DOC: Routing tables
|
| 11 |
*
|
| 12 |
* Routing tables are probably the most important structures BIRD uses. They
|
| 13 |
* hold all the information about known networks, the associated routes and
|
| 14 |
* their attributes.
|
| 15 |
*
|
| 16 |
* There are multiple routing tables (a primary one together with any
|
| 17 |
* number of secondary ones if requested by the configuration). Each table
|
| 18 |
* is basically a FIB containing entries describing the individual
|
| 19 |
* destination networks. For each network (represented by structure &net),
|
| 20 |
* there is a one-way linked list of route entries (&rte), the first entry
|
| 21 |
* on the list being the best one (i.e., the one we currently use
|
| 22 |
* for routing), the order of the other ones is undetermined.
|
| 23 |
*
|
| 24 |
* The &rte contains information specific to the route (preference, protocol
|
| 25 |
* metrics, time of last modification etc.) and a pointer to a &rta structure
|
| 26 |
* (see the route attribute module for a precise explanation) holding the
|
| 27 |
* remaining route attributes which are expected to be shared by multiple
|
| 28 |
* routes in order to conserve memory.
|
| 29 |
*/
|
| 30 |
|
| 31 |
#undef LOCAL_DEBUG
|
| 32 |
|
| 33 |
#include "nest/bird.h" |
| 34 |
#include "nest/route.h" |
| 35 |
#include "nest/protocol.h" |
| 36 |
#include "nest/cli.h" |
| 37 |
#include "nest/iface.h" |
| 38 |
#include "lib/resource.h" |
| 39 |
#include "lib/event.h" |
| 40 |
#include "lib/string.h" |
| 41 |
#include "conf/conf.h" |
| 42 |
#include "filter/filter.h" |
| 43 |
#include "lib/string.h" |
| 44 |
#include "lib/alloca.h" |
| 45 |
|
| 46 |
pool *rt_table_pool; |
| 47 |
|
| 48 |
static slab *rte_slab;
|
| 49 |
static linpool *rte_update_pool;
|
| 50 |
|
| 51 |
static list routing_tables;
|
| 52 |
|
| 53 |
static void rt_format_via(rte *e, byte *via); |
| 54 |
static void rt_free_hostcache(rtable *tab); |
| 55 |
static void rt_notify_hostcache(rtable *tab, net *net); |
| 56 |
static void rt_update_hostcache(rtable *tab); |
| 57 |
static void rt_next_hop_update(rtable *tab); |
| 58 |
static inline int rt_prune_table(rtable *tab); |
| 59 |
static inline void rt_schedule_gc(rtable *tab); |
| 60 |
static inline void rt_schedule_prune(rtable *tab); |
| 61 |
|
| 62 |
|
| 63 |
static inline struct ea_list * |
| 64 |
make_tmp_attrs(struct rte *rt, struct linpool *pool) |
| 65 |
{
|
| 66 |
struct ea_list *(*mta)(struct rte *rt, struct linpool *pool); |
| 67 |
mta = rt->attrs->src->proto->make_tmp_attrs; |
| 68 |
return mta ? mta(rt, rte_update_pool) : NULL; |
| 69 |
} |
| 70 |
|
| 71 |
/* Like fib_route(), but skips empty net entries */
|
| 72 |
static net *
|
| 73 |
net_route(rtable *tab, ip_addr a, int len)
|
| 74 |
{
|
| 75 |
ip_addr a0; |
| 76 |
net *n; |
| 77 |
|
| 78 |
while (len >= 0) |
| 79 |
{
|
| 80 |
a0 = ipa_and(a, ipa_mkmask(len)); |
| 81 |
n = fib_find(&tab->fib, &a0, len); |
| 82 |
if (n && rte_is_valid(n->routes))
|
| 83 |
return n;
|
| 84 |
len--; |
| 85 |
} |
| 86 |
return NULL; |
| 87 |
} |
| 88 |
|
| 89 |
static void |
| 90 |
rte_init(struct fib_node *N)
|
| 91 |
{
|
| 92 |
net *n = (net *) N; |
| 93 |
|
| 94 |
N->flags = 0;
|
| 95 |
n->routes = NULL;
|
| 96 |
} |
| 97 |
|
| 98 |
/**
|
| 99 |
* rte_find - find a route
|
| 100 |
* @net: network node
|
| 101 |
* @src: route source
|
| 102 |
*
|
| 103 |
* The rte_find() function returns a route for destination @net
|
| 104 |
* which is from route source @src.
|
| 105 |
*/
|
| 106 |
rte * |
| 107 |
rte_find(net *net, struct rte_src *src)
|
| 108 |
{
|
| 109 |
rte *e = net->routes; |
| 110 |
|
| 111 |
while (e && e->attrs->src != src)
|
| 112 |
e = e->next; |
| 113 |
return e;
|
| 114 |
} |
| 115 |
|
| 116 |
/**
|
| 117 |
* rte_get_temp - get a temporary &rte
|
| 118 |
* @a: attributes to assign to the new route (a &rta; in case it's
|
| 119 |
* un-cached, rte_update() will create a cached copy automatically)
|
| 120 |
*
|
| 121 |
* Create a temporary &rte and bind it with the attributes @a.
|
| 122 |
* Also set route preference to the default preference set for
|
| 123 |
* the protocol.
|
| 124 |
*/
|
| 125 |
rte * |
| 126 |
rte_get_temp(rta *a) |
| 127 |
{
|
| 128 |
rte *e = sl_alloc(rte_slab); |
| 129 |
|
| 130 |
e->attrs = a; |
| 131 |
e->flags = 0;
|
| 132 |
e->pref = a->src->proto->preference; |
| 133 |
return e;
|
| 134 |
} |
| 135 |
|
| 136 |
rte * |
| 137 |
rte_do_cow(rte *r) |
| 138 |
{
|
| 139 |
rte *e = sl_alloc(rte_slab); |
| 140 |
|
| 141 |
memcpy(e, r, sizeof(rte));
|
| 142 |
e->attrs = rta_clone(r->attrs); |
| 143 |
e->flags = 0;
|
| 144 |
return e;
|
| 145 |
} |
| 146 |
|
| 147 |
static int /* Actually better or at least as good as */ |
| 148 |
rte_better(rte *new, rte *old) |
| 149 |
{
|
| 150 |
int (*better)(rte *, rte *);
|
| 151 |
|
| 152 |
if (!rte_is_valid(old))
|
| 153 |
return 1; |
| 154 |
if (!rte_is_valid(new))
|
| 155 |
return 0; |
| 156 |
|
| 157 |
if (new->pref > old->pref)
|
| 158 |
return 1; |
| 159 |
if (new->pref < old->pref)
|
| 160 |
return 0; |
| 161 |
if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
|
| 162 |
{
|
| 163 |
/*
|
| 164 |
* If the user has configured protocol preferences, so that two different protocols
|
| 165 |
* have the same preference, try to break the tie by comparing addresses. Not too
|
| 166 |
* useful, but keeps the ordering of routes unambiguous.
|
| 167 |
*/
|
| 168 |
return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
|
| 169 |
} |
| 170 |
if (better = new->attrs->src->proto->rte_better)
|
| 171 |
return better(new, old);
|
| 172 |
return 0; |
| 173 |
} |
| 174 |
|
| 175 |
static void |
| 176 |
rte_trace(struct proto *p, rte *e, int dir, char *msg) |
| 177 |
{
|
| 178 |
byte via[STD_ADDRESS_P_LENGTH+32];
|
| 179 |
|
| 180 |
rt_format_via(e, via); |
| 181 |
log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
|
| 182 |
} |
| 183 |
|
| 184 |
static inline void |
| 185 |
rte_trace_in(uint flag, struct proto *p, rte *e, char *msg) |
| 186 |
{
|
| 187 |
if (p->debug & flag)
|
| 188 |
rte_trace(p, e, '>', msg);
|
| 189 |
} |
| 190 |
|
| 191 |
static inline void |
| 192 |
rte_trace_out(uint flag, struct proto *p, rte *e, char *msg) |
| 193 |
{
|
| 194 |
if (p->debug & flag)
|
| 195 |
rte_trace(p, e, '<', msg);
|
| 196 |
} |
| 197 |
|
| 198 |
static rte *
|
| 199 |
export_filter(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, int silent) |
| 200 |
{
|
| 201 |
struct proto *p = ah->proto;
|
| 202 |
struct filter *filter = ah->out_filter;
|
| 203 |
struct proto_stats *stats = ah->stats;
|
| 204 |
ea_list *tmpb = NULL;
|
| 205 |
rte *rt; |
| 206 |
int v;
|
| 207 |
|
| 208 |
rt = rt0; |
| 209 |
*rt_free = NULL;
|
| 210 |
|
| 211 |
/* If called does not care for eattrs, we prepare one internally */
|
| 212 |
if (!tmpa)
|
| 213 |
{
|
| 214 |
tmpb = make_tmp_attrs(rt, rte_update_pool); |
| 215 |
tmpa = &tmpb; |
| 216 |
} |
| 217 |
|
| 218 |
v = p->import_control ? p->import_control(p, &rt, tmpa, rte_update_pool) : 0;
|
| 219 |
if (v < 0) |
| 220 |
{
|
| 221 |
if (silent)
|
| 222 |
goto reject;
|
| 223 |
|
| 224 |
stats->exp_updates_rejected++; |
| 225 |
if (v == RIC_REJECT)
|
| 226 |
rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
|
| 227 |
goto reject;
|
| 228 |
} |
| 229 |
if (v > 0) |
| 230 |
{
|
| 231 |
if (!silent)
|
| 232 |
rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
|
| 233 |
goto accept;
|
| 234 |
} |
| 235 |
|
| 236 |
v = filter && ((filter == FILTER_REJECT) || |
| 237 |
(f_run(filter, &rt, tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)); |
| 238 |
if (v)
|
| 239 |
{
|
| 240 |
if (silent)
|
| 241 |
goto reject;
|
| 242 |
|
| 243 |
stats->exp_updates_filtered++; |
| 244 |
rte_trace_out(D_FILTERS, p, rt, "filtered out");
|
| 245 |
goto reject;
|
| 246 |
} |
| 247 |
|
| 248 |
accept:
|
| 249 |
if (rt != rt0)
|
| 250 |
*rt_free = rt; |
| 251 |
return rt;
|
| 252 |
|
| 253 |
reject:
|
| 254 |
/* Discard temporary rte */
|
| 255 |
if (rt != rt0)
|
| 256 |
rte_free(rt); |
| 257 |
return NULL; |
| 258 |
} |
| 259 |
|
| 260 |
static void |
| 261 |
do_rt_notify(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed) |
| 262 |
{
|
| 263 |
struct proto *p = ah->proto;
|
| 264 |
struct proto_stats *stats = ah->stats;
|
| 265 |
|
| 266 |
|
| 267 |
/*
|
| 268 |
* First, apply export limit.
|
| 269 |
*
|
| 270 |
* Export route limits has several problems. Because exp_routes
|
| 271 |
* counter is reset before refeed, we don't really know whether
|
| 272 |
* limit is breached and whether the update is new or not. Therefore
|
| 273 |
* the number of really exported routes may exceed the limit
|
| 274 |
* temporarily (routes exported before and new routes in refeed).
|
| 275 |
*
|
| 276 |
* Minor advantage is that if the limit is decreased and refeed is
|
| 277 |
* requested, the number of exported routes really decrease.
|
| 278 |
*
|
| 279 |
* Second problem is that with export limits, we don't know whether
|
| 280 |
* old was really exported (it might be blocked by limit). When a
|
| 281 |
* withdraw is exported, we announce it even when the previous
|
| 282 |
* update was blocked. This is not a big issue, but the same problem
|
| 283 |
* is in updating exp_routes counter. Therefore, to be consistent in
|
| 284 |
* increases and decreases of exp_routes, we count exported routes
|
| 285 |
* regardless of blocking by limits.
|
| 286 |
*
|
| 287 |
* Similar problem is in handling updates - when a new route is
|
| 288 |
* received and blocking is active, the route would be blocked, but
|
| 289 |
* when an update for the route will be received later, the update
|
| 290 |
* would be propagated (as old != NULL). Therefore, we have to block
|
| 291 |
* also non-new updates (contrary to import blocking).
|
| 292 |
*/
|
| 293 |
|
| 294 |
struct proto_limit *l = ah->out_limit;
|
| 295 |
if (l && new)
|
| 296 |
{
|
| 297 |
if ((!old || refeed) && (stats->exp_routes >= l->limit))
|
| 298 |
proto_notify_limit(ah, l, PLD_OUT, stats->exp_routes); |
| 299 |
|
| 300 |
if (l->state == PLS_BLOCKED)
|
| 301 |
{
|
| 302 |
stats->exp_routes++; /* see note above */
|
| 303 |
stats->exp_updates_rejected++; |
| 304 |
rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
|
| 305 |
new = NULL;
|
| 306 |
|
| 307 |
if (!old)
|
| 308 |
return;
|
| 309 |
} |
| 310 |
} |
| 311 |
|
| 312 |
|
| 313 |
if (new)
|
| 314 |
stats->exp_updates_accepted++; |
| 315 |
else
|
| 316 |
stats->exp_withdraws_accepted++; |
| 317 |
|
| 318 |
/* Hack: We do not decrease exp_routes during refeed, we instead
|
| 319 |
reset exp_routes at the start of refeed. */
|
| 320 |
if (new)
|
| 321 |
stats->exp_routes++; |
| 322 |
if (old && !refeed)
|
| 323 |
stats->exp_routes--; |
| 324 |
|
| 325 |
if (p->debug & D_ROUTES)
|
| 326 |
{
|
| 327 |
if (new && old)
|
| 328 |
rte_trace_out(D_ROUTES, p, new, "replaced");
|
| 329 |
else if (new) |
| 330 |
rte_trace_out(D_ROUTES, p, new, "added");
|
| 331 |
else if (old) |
| 332 |
rte_trace_out(D_ROUTES, p, old, "removed");
|
| 333 |
} |
| 334 |
if (!new)
|
| 335 |
p->rt_notify(p, ah->table, net, NULL, old, NULL); |
| 336 |
else if (tmpa) |
| 337 |
{
|
| 338 |
ea_list *t = tmpa; |
| 339 |
while (t->next)
|
| 340 |
t = t->next; |
| 341 |
t->next = new->attrs->eattrs; |
| 342 |
p->rt_notify(p, ah->table, net, new, old, tmpa); |
| 343 |
t->next = NULL;
|
| 344 |
} |
| 345 |
else
|
| 346 |
p->rt_notify(p, ah->table, net, new, old, new->attrs->eattrs); |
| 347 |
} |
| 348 |
|
| 349 |
static void |
| 350 |
rt_notify_basic(struct announce_hook *ah, net *net, rte *new0, rte *old0, ea_list *tmpa, int refeed) |
| 351 |
{
|
| 352 |
struct proto *p = ah->proto;
|
| 353 |
struct proto_stats *stats = ah->stats;
|
| 354 |
|
| 355 |
rte *new = new0; |
| 356 |
rte *old = old0; |
| 357 |
rte *new_free = NULL;
|
| 358 |
rte *old_free = NULL;
|
| 359 |
|
| 360 |
if (new)
|
| 361 |
stats->exp_updates_received++; |
| 362 |
else
|
| 363 |
stats->exp_withdraws_received++; |
| 364 |
|
| 365 |
/*
|
| 366 |
* This is a tricky part - we don't know whether route 'old' was
|
| 367 |
* exported to protocol 'p' or was filtered by the export filter.
|
| 368 |
* We try to run the export filter to know this to have a correct
|
| 369 |
* value in 'old' argument of rte_update (and proper filter value)
|
| 370 |
*
|
| 371 |
* FIXME - this is broken because 'configure soft' may change
|
| 372 |
* filters but keep routes. Refeed is expected to be called after
|
| 373 |
* change of the filters and with old == new, therefore we do not
|
| 374 |
* even try to run the filter on an old route, This may lead to
|
| 375 |
* 'spurious withdraws' but ensure that there are no 'missing
|
| 376 |
* withdraws'.
|
| 377 |
*
|
| 378 |
* This is not completely safe as there is a window between
|
| 379 |
* reconfiguration and the end of refeed - if a newly filtered
|
| 380 |
* route disappears during this period, proper withdraw is not
|
| 381 |
* sent (because old would be also filtered) and the route is
|
| 382 |
* not refeeded (because it disappeared before that).
|
| 383 |
*/
|
| 384 |
|
| 385 |
if (new)
|
| 386 |
new = export_filter(ah, new, &new_free, &tmpa, 0);
|
| 387 |
|
| 388 |
if (old && !refeed)
|
| 389 |
old = export_filter(ah, old, &old_free, NULL, 1); |
| 390 |
|
| 391 |
if (!new && !old)
|
| 392 |
{
|
| 393 |
/*
|
| 394 |
* As mentioned above, 'old' value may be incorrect in some race conditions.
|
| 395 |
* We generally ignore it with the exception of withdraw to pipe protocol.
|
| 396 |
* In that case we rather propagate unfiltered withdraws regardless of
|
| 397 |
* export filters to ensure that when a protocol is flushed, its routes are
|
| 398 |
* removed from all tables. Possible spurious unfiltered withdraws are not
|
| 399 |
* problem here as they are ignored if there is no corresponding route at
|
| 400 |
* the other end of the pipe. We directly call rt_notify() hook instead of
|
| 401 |
* do_rt_notify() to avoid logging and stat counters.
|
| 402 |
*/
|
| 403 |
|
| 404 |
#ifdef CONFIG_PIPE
|
| 405 |
if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto))
|
| 406 |
p->rt_notify(p, ah->table, net, NULL, old0, NULL); |
| 407 |
#endif
|
| 408 |
|
| 409 |
return;
|
| 410 |
} |
| 411 |
|
| 412 |
do_rt_notify(ah, net, new, old, tmpa, refeed); |
| 413 |
|
| 414 |
/* Discard temporary rte's */
|
| 415 |
if (new_free)
|
| 416 |
rte_free(new_free); |
| 417 |
if (old_free)
|
| 418 |
rte_free(old_free); |
| 419 |
} |
| 420 |
|
| 421 |
static void |
| 422 |
rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old,
|
| 423 |
ea_list *tmpa, int feed)
|
| 424 |
{
|
| 425 |
// struct proto *p = ah->proto;
|
| 426 |
struct proto_stats *stats = ah->stats;
|
| 427 |
|
| 428 |
rte *new_best = NULL;
|
| 429 |
rte *old_best = NULL;
|
| 430 |
rte *new_free = NULL;
|
| 431 |
rte *old_free = NULL;
|
| 432 |
rte *r; |
| 433 |
|
| 434 |
/* Used to track whether we met old_changed position. If before_old is NULL
|
| 435 |
old_changed was the first and we met it implicitly before current best route. */
|
| 436 |
int old_meet = old_changed && !before_old;
|
| 437 |
|
| 438 |
/* Note that before_old is either NULL or valid (not rejected) route.
|
| 439 |
If old_changed is valid, before_old have to be too. If old changed route
|
| 440 |
was not valid, caller must use NULL for both old_changed and before_old. */
|
| 441 |
|
| 442 |
if (new_changed)
|
| 443 |
stats->exp_updates_received++; |
| 444 |
else
|
| 445 |
stats->exp_withdraws_received++; |
| 446 |
|
| 447 |
/* First, find the new_best route - first accepted by filters */
|
| 448 |
for (r=net->routes; rte_is_valid(r); r=r->next)
|
| 449 |
{
|
| 450 |
if (new_best = export_filter(ah, r, &new_free, &tmpa, 0)) |
| 451 |
break;
|
| 452 |
|
| 453 |
/* Note if we walked around the position of old_changed route */
|
| 454 |
if (r == before_old)
|
| 455 |
old_meet = 1;
|
| 456 |
} |
| 457 |
|
| 458 |
/*
|
| 459 |
* Second, handle the feed case. That means we do not care for
|
| 460 |
* old_best. It is NULL for feed, and the new_best for refeed.
|
| 461 |
* For refeed, there is a hack similar to one in rt_notify_basic()
|
| 462 |
* to ensure withdraws in case of changed filters
|
| 463 |
*/
|
| 464 |
if (feed)
|
| 465 |
{
|
| 466 |
if (feed == 2) /* refeed */ |
| 467 |
old_best = new_best ? new_best : |
| 468 |
(rte_is_valid(net->routes) ? net->routes : NULL);
|
| 469 |
else
|
| 470 |
old_best = NULL;
|
| 471 |
|
| 472 |
if (!new_best && !old_best)
|
| 473 |
return;
|
| 474 |
|
| 475 |
goto found;
|
| 476 |
} |
| 477 |
|
| 478 |
/*
|
| 479 |
* Now, we find the old_best route. Generally, it is the same as the
|
| 480 |
* new_best, unless new_best is the same as new_changed or
|
| 481 |
* old_changed is accepted before new_best.
|
| 482 |
*
|
| 483 |
* There are four cases:
|
| 484 |
*
|
| 485 |
* - We would find and accept old_changed before new_best, therefore
|
| 486 |
* old_changed is old_best. In remaining cases we suppose this
|
| 487 |
* is not true.
|
| 488 |
*
|
| 489 |
* - We found no new_best, therefore there is also no old_best and
|
| 490 |
* we ignore this withdraw.
|
| 491 |
*
|
| 492 |
* - We found new_best different than new_changed, therefore
|
| 493 |
* old_best is the same as new_best and we ignore this update.
|
| 494 |
*
|
| 495 |
* - We found new_best the same as new_changed, therefore it cannot
|
| 496 |
* be old_best and we have to continue search for old_best.
|
| 497 |
*/
|
| 498 |
|
| 499 |
/* First case */
|
| 500 |
if (old_meet)
|
| 501 |
if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1)) |
| 502 |
goto found;
|
| 503 |
|
| 504 |
/* Second case */
|
| 505 |
if (!new_best)
|
| 506 |
return;
|
| 507 |
|
| 508 |
/* Third case, we use r instead of new_best, because export_filter() could change it */
|
| 509 |
if (r != new_changed)
|
| 510 |
{
|
| 511 |
if (new_free)
|
| 512 |
rte_free(new_free); |
| 513 |
return;
|
| 514 |
} |
| 515 |
|
| 516 |
/* Fourth case */
|
| 517 |
for (r=r->next; rte_is_valid(r); r=r->next)
|
| 518 |
{
|
| 519 |
if (old_best = export_filter(ah, r, &old_free, NULL, 1)) |
| 520 |
goto found;
|
| 521 |
|
| 522 |
if (r == before_old)
|
| 523 |
if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1)) |
| 524 |
goto found;
|
| 525 |
} |
| 526 |
|
| 527 |
/* Implicitly, old_best is NULL and new_best is non-NULL */
|
| 528 |
|
| 529 |
found:
|
| 530 |
do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2));
|
| 531 |
|
| 532 |
/* Discard temporary rte's */
|
| 533 |
if (new_free)
|
| 534 |
rte_free(new_free); |
| 535 |
if (old_free)
|
| 536 |
rte_free(old_free); |
| 537 |
} |
| 538 |
|
| 539 |
/**
|
| 540 |
* rte_announce - announce a routing table change
|
| 541 |
* @tab: table the route has been added to
|
| 542 |
* @type: type of route announcement (RA_OPTIMAL or RA_ANY)
|
| 543 |
* @net: network in question
|
| 544 |
* @new: the new route to be announced
|
| 545 |
* @old: the previous route for the same network
|
| 546 |
* @tmpa: a list of temporary attributes belonging to the new route
|
| 547 |
*
|
| 548 |
* This function gets a routing table update and announces it
|
| 549 |
* to all protocols that acccepts given type of route announcement
|
| 550 |
* and are connected to the same table by their announcement hooks.
|
| 551 |
*
|
| 552 |
* Route announcement of type RA_OPTIMAL si generated when optimal
|
| 553 |
* route (in routing table @tab) changes. In that case @old stores the
|
| 554 |
* old optimal route.
|
| 555 |
*
|
| 556 |
* Route announcement of type RA_ANY si generated when any route (in
|
| 557 |
* routing table @tab) changes In that case @old stores the old route
|
| 558 |
* from the same protocol.
|
| 559 |
*
|
| 560 |
* For each appropriate protocol, we first call its import_control()
|
| 561 |
* hook which performs basic checks on the route (each protocol has a
|
| 562 |
* right to veto or force accept of the route before any filter is
|
| 563 |
* asked) and adds default values of attributes specific to the new
|
| 564 |
* protocol (metrics, tags etc.). Then it consults the protocol's
|
| 565 |
* export filter and if it accepts the route, the rt_notify() hook of
|
| 566 |
* the protocol gets called.
|
| 567 |
*/
|
| 568 |
static void |
| 569 |
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *before_old, ea_list *tmpa)
|
| 570 |
{
|
| 571 |
if (!rte_is_valid(old))
|
| 572 |
old = before_old = NULL;
|
| 573 |
|
| 574 |
if (!rte_is_valid(new))
|
| 575 |
new = NULL;
|
| 576 |
|
| 577 |
if (!old && !new)
|
| 578 |
return;
|
| 579 |
|
| 580 |
if (type == RA_OPTIMAL)
|
| 581 |
{
|
| 582 |
if (new)
|
| 583 |
new->attrs->src->proto->stats.pref_routes++; |
| 584 |
if (old)
|
| 585 |
old->attrs->src->proto->stats.pref_routes--; |
| 586 |
|
| 587 |
if (tab->hostcache)
|
| 588 |
rt_notify_hostcache(tab, net); |
| 589 |
} |
| 590 |
|
| 591 |
struct announce_hook *a;
|
| 592 |
WALK_LIST(a, tab->hooks) |
| 593 |
{
|
| 594 |
ASSERT(a->proto->export_state != ES_DOWN); |
| 595 |
if (a->proto->accept_ra_types == type)
|
| 596 |
if (type == RA_ACCEPTED)
|
| 597 |
rt_notify_accepted(a, net, new, old, before_old, tmpa, 0);
|
| 598 |
else
|
| 599 |
rt_notify_basic(a, net, new, old, tmpa, 0);
|
| 600 |
} |
| 601 |
} |
| 602 |
|
| 603 |
static inline int |
| 604 |
rte_validate(rte *e) |
| 605 |
{
|
| 606 |
int c;
|
| 607 |
net *n = e->net; |
| 608 |
|
| 609 |
if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
|
| 610 |
{
|
| 611 |
log(L_WARN "Ignoring bogus prefix %I/%d received via %s",
|
| 612 |
n->n.prefix, n->n.pxlen, e->sender->proto->name); |
| 613 |
return 0; |
| 614 |
} |
| 615 |
|
| 616 |
c = ipa_classify_net(n->n.prefix); |
| 617 |
if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK)) |
| 618 |
{
|
| 619 |
log(L_WARN "Ignoring bogus route %I/%d received via %s",
|
| 620 |
n->n.prefix, n->n.pxlen, e->sender->proto->name); |
| 621 |
return 0; |
| 622 |
} |
| 623 |
|
| 624 |
return 1; |
| 625 |
} |
| 626 |
|
| 627 |
/**
|
| 628 |
* rte_free - delete a &rte
|
| 629 |
* @e: &rte to be deleted
|
| 630 |
*
|
| 631 |
* rte_free() deletes the given &rte from the routing table it's linked to.
|
| 632 |
*/
|
| 633 |
void
|
| 634 |
rte_free(rte *e) |
| 635 |
{
|
| 636 |
if (rta_is_cached(e->attrs))
|
| 637 |
rta_free(e->attrs); |
| 638 |
sl_free(rte_slab, e); |
| 639 |
} |
| 640 |
|
| 641 |
static inline void |
| 642 |
rte_free_quick(rte *e) |
| 643 |
{
|
| 644 |
rta_free(e->attrs); |
| 645 |
sl_free(rte_slab, e); |
| 646 |
} |
| 647 |
|
| 648 |
static int |
| 649 |
rte_same(rte *x, rte *y) |
| 650 |
{
|
| 651 |
return
|
| 652 |
x->attrs == y->attrs && |
| 653 |
x->flags == y->flags && |
| 654 |
x->pflags == y->pflags && |
| 655 |
x->pref == y->pref && |
| 656 |
(!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y)); |
| 657 |
} |
| 658 |
|
| 659 |
static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); } |
| 660 |
|
| 661 |
static void |
| 662 |
rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, struct rte_src *src) |
| 663 |
{
|
| 664 |
struct proto *p = ah->proto;
|
| 665 |
struct rtable *table = ah->table;
|
| 666 |
struct proto_stats *stats = ah->stats;
|
| 667 |
static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS; |
| 668 |
rte *before_old = NULL;
|
| 669 |
rte *old_best = net->routes; |
| 670 |
rte *old = NULL;
|
| 671 |
rte **k; |
| 672 |
|
| 673 |
k = &net->routes; /* Find and remove original route from the same protocol */
|
| 674 |
while (old = *k)
|
| 675 |
{
|
| 676 |
if (old->attrs->src == src)
|
| 677 |
{
|
| 678 |
/* If there is the same route in the routing table but from
|
| 679 |
* a different sender, then there are two paths from the
|
| 680 |
* source protocol to this routing table through transparent
|
| 681 |
* pipes, which is not allowed.
|
| 682 |
*
|
| 683 |
* We log that and ignore the route. If it is withdraw, we
|
| 684 |
* ignore it completely (there might be 'spurious withdraws',
|
| 685 |
* see FIXME in do_rte_announce())
|
| 686 |
*/
|
| 687 |
if (old->sender->proto != p)
|
| 688 |
{
|
| 689 |
if (new)
|
| 690 |
{
|
| 691 |
log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %I/%d to table %s",
|
| 692 |
net->n.prefix, net->n.pxlen, table->name); |
| 693 |
rte_free_quick(new); |
| 694 |
} |
| 695 |
return;
|
| 696 |
} |
| 697 |
|
| 698 |
if (new && rte_same(old, new))
|
| 699 |
{
|
| 700 |
/* No changes, ignore the new route */
|
| 701 |
|
| 702 |
if (!rte_is_filtered(new))
|
| 703 |
{
|
| 704 |
stats->imp_updates_ignored++; |
| 705 |
rte_trace_in(D_ROUTES, p, new, "ignored");
|
| 706 |
} |
| 707 |
|
| 708 |
rte_free_quick(new); |
| 709 |
#ifdef CONFIG_RIP
|
| 710 |
/* lastmod is used internally by RIP as the last time
|
| 711 |
when the route was received. */
|
| 712 |
if (src->proto->proto == &proto_rip)
|
| 713 |
old->lastmod = now; |
| 714 |
#endif
|
| 715 |
return;
|
| 716 |
} |
| 717 |
*k = old->next; |
| 718 |
break;
|
| 719 |
} |
| 720 |
k = &old->next; |
| 721 |
before_old = old; |
| 722 |
} |
| 723 |
|
| 724 |
if (!old)
|
| 725 |
before_old = NULL;
|
| 726 |
|
| 727 |
if (!old && !new)
|
| 728 |
{
|
| 729 |
stats->imp_withdraws_ignored++; |
| 730 |
return;
|
| 731 |
} |
| 732 |
|
| 733 |
int new_ok = rte_is_ok(new);
|
| 734 |
int old_ok = rte_is_ok(old);
|
| 735 |
|
| 736 |
struct proto_limit *l = ah->rx_limit;
|
| 737 |
if (l && !old && new)
|
| 738 |
{
|
| 739 |
u32 all_routes = stats->imp_routes + stats->filt_routes; |
| 740 |
|
| 741 |
if (all_routes >= l->limit)
|
| 742 |
proto_notify_limit(ah, l, PLD_RX, all_routes); |
| 743 |
|
| 744 |
if (l->state == PLS_BLOCKED)
|
| 745 |
{
|
| 746 |
/* In receive limit the situation is simple, old is NULL so
|
| 747 |
we just free new and exit like nothing happened */
|
| 748 |
|
| 749 |
stats->imp_updates_ignored++; |
| 750 |
rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
|
| 751 |
rte_free_quick(new); |
| 752 |
return;
|
| 753 |
} |
| 754 |
} |
| 755 |
|
| 756 |
l = ah->in_limit; |
| 757 |
if (l && !old_ok && new_ok)
|
| 758 |
{
|
| 759 |
if (stats->imp_routes >= l->limit)
|
| 760 |
proto_notify_limit(ah, l, PLD_IN, stats->imp_routes); |
| 761 |
|
| 762 |
if (l->state == PLS_BLOCKED)
|
| 763 |
{
|
| 764 |
/* In import limit the situation is more complicated. We
|
| 765 |
shouldn't just drop the route, we should handle it like
|
| 766 |
it was filtered. We also have to continue the route
|
| 767 |
processing if old or new is non-NULL, but we should exit
|
| 768 |
if both are NULL as this case is probably assumed to be
|
| 769 |
already handled. */
|
| 770 |
|
| 771 |
stats->imp_updates_ignored++; |
| 772 |
rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
|
| 773 |
|
| 774 |
if (ah->in_keep_filtered)
|
| 775 |
new->flags |= REF_FILTERED; |
| 776 |
else
|
| 777 |
{ rte_free_quick(new); new = NULL; }
|
| 778 |
|
| 779 |
/* Note that old && !new could be possible when
|
| 780 |
ah->in_keep_filtered changed in the recent past. */
|
| 781 |
|
| 782 |
if (!old && !new)
|
| 783 |
return;
|
| 784 |
|
| 785 |
new_ok = 0;
|
| 786 |
goto skip_stats1;
|
| 787 |
} |
| 788 |
} |
| 789 |
|
| 790 |
if (new_ok)
|
| 791 |
stats->imp_updates_accepted++; |
| 792 |
else if (old_ok) |
| 793 |
stats->imp_withdraws_accepted++; |
| 794 |
else
|
| 795 |
stats->imp_withdraws_ignored++; |
| 796 |
|
| 797 |
skip_stats1:
|
| 798 |
|
| 799 |
if (new)
|
| 800 |
rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++; |
| 801 |
if (old)
|
| 802 |
rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--; |
| 803 |
|
| 804 |
if (table->config->sorted)
|
| 805 |
{
|
| 806 |
/* If routes are sorted, just insert new route to appropriate position */
|
| 807 |
if (new)
|
| 808 |
{
|
| 809 |
if (before_old && !rte_better(new, before_old))
|
| 810 |
k = &before_old->next; |
| 811 |
else
|
| 812 |
k = &net->routes; |
| 813 |
|
| 814 |
for (; *k; k=&(*k)->next)
|
| 815 |
if (rte_better(new, *k))
|
| 816 |
break;
|
| 817 |
|
| 818 |
new->next = *k; |
| 819 |
*k = new; |
| 820 |
} |
| 821 |
} |
| 822 |
else
|
| 823 |
{
|
| 824 |
/* If routes are not sorted, find the best route and move it on
|
| 825 |
the first position. There are several optimized cases. */
|
| 826 |
|
| 827 |
if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
|
| 828 |
goto do_recalculate;
|
| 829 |
|
| 830 |
if (new && rte_better(new, old_best))
|
| 831 |
{
|
| 832 |
/* The first case - the new route is cleary optimal,
|
| 833 |
we link it at the first position */
|
| 834 |
|
| 835 |
new->next = net->routes; |
| 836 |
net->routes = new; |
| 837 |
} |
| 838 |
else if (old == old_best) |
| 839 |
{
|
| 840 |
/* The second case - the old best route disappeared, we add the
|
| 841 |
new route (if we have any) to the list (we don't care about
|
| 842 |
position) and then we elect the new optimal route and relink
|
| 843 |
that route at the first position and announce it. New optimal
|
| 844 |
route might be NULL if there is no more routes */
|
| 845 |
|
| 846 |
do_recalculate:
|
| 847 |
/* Add the new route to the list */
|
| 848 |
if (new)
|
| 849 |
{
|
| 850 |
new->next = net->routes; |
| 851 |
net->routes = new; |
| 852 |
} |
| 853 |
|
| 854 |
/* Find a new optimal route (if there is any) */
|
| 855 |
if (net->routes)
|
| 856 |
{
|
| 857 |
rte **bp = &net->routes; |
| 858 |
for (k=&(*bp)->next; *k; k=&(*k)->next)
|
| 859 |
if (rte_better(*k, *bp))
|
| 860 |
bp = k; |
| 861 |
|
| 862 |
/* And relink it */
|
| 863 |
rte *best = *bp; |
| 864 |
*bp = best->next; |
| 865 |
best->next = net->routes; |
| 866 |
net->routes = best; |
| 867 |
} |
| 868 |
} |
| 869 |
else if (new) |
| 870 |
{
|
| 871 |
/* The third case - the new route is not better than the old
|
| 872 |
best route (therefore old_best != NULL) and the old best
|
| 873 |
route was not removed (therefore old_best == net->routes).
|
| 874 |
We just link the new route after the old best route. */
|
| 875 |
|
| 876 |
ASSERT(net->routes != NULL);
|
| 877 |
new->next = net->routes->next; |
| 878 |
net->routes->next = new; |
| 879 |
} |
| 880 |
/* The fourth (empty) case - suboptimal route was removed, nothing to do */
|
| 881 |
} |
| 882 |
|
| 883 |
if (new)
|
| 884 |
new->lastmod = now; |
| 885 |
|
| 886 |
/* Log the route change */
|
| 887 |
if (p->debug & D_ROUTES)
|
| 888 |
{
|
| 889 |
if (new_ok)
|
| 890 |
rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added"); |
| 891 |
else if (old_ok) |
| 892 |
{
|
| 893 |
if (old != old_best)
|
| 894 |
rte_trace(p, old, '>', "removed"); |
| 895 |
else if (rte_is_ok(net->routes)) |
| 896 |
rte_trace(p, old, '>', "removed [replaced]"); |
| 897 |
else
|
| 898 |
rte_trace(p, old, '>', "removed [sole]"); |
| 899 |
} |
| 900 |
} |
| 901 |
|
| 902 |
/* Propagate the route change */
|
| 903 |
rte_announce(table, RA_ANY, net, new, old, NULL, tmpa);
|
| 904 |
if (net->routes != old_best)
|
| 905 |
rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, tmpa);
|
| 906 |
if (table->config->sorted)
|
| 907 |
rte_announce(table, RA_ACCEPTED, net, new, old, before_old, tmpa); |
| 908 |
|
| 909 |
if (!net->routes &&
|
| 910 |
(table->gc_counter++ >= table->config->gc_max_ops) && |
| 911 |
(table->gc_time + table->config->gc_min_time <= now)) |
| 912 |
rt_schedule_gc(table); |
| 913 |
|
| 914 |
if (old_ok && p->rte_remove)
|
| 915 |
p->rte_remove(net, old); |
| 916 |
if (new_ok && p->rte_insert)
|
| 917 |
p->rte_insert(net, new); |
| 918 |
|
| 919 |
if (old)
|
| 920 |
rte_free_quick(old); |
| 921 |
} |
| 922 |
|
| 923 |
static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */ |
| 924 |
|
| 925 |
static inline void |
| 926 |
rte_update_lock(void)
|
| 927 |
{
|
| 928 |
rte_update_nest_cnt++; |
| 929 |
} |
| 930 |
|
| 931 |
static inline void |
| 932 |
rte_update_unlock(void)
|
| 933 |
{
|
| 934 |
if (!--rte_update_nest_cnt)
|
| 935 |
lp_flush(rte_update_pool); |
| 936 |
} |
| 937 |
|
| 938 |
static inline void |
| 939 |
rte_hide_dummy_routes(net *net, rte **dummy) |
| 940 |
{
|
| 941 |
if (net->routes && net->routes->attrs->source == RTS_DUMMY)
|
| 942 |
{
|
| 943 |
*dummy = net->routes; |
| 944 |
net->routes = (*dummy)->next; |
| 945 |
} |
| 946 |
} |
| 947 |
|
| 948 |
static inline void |
| 949 |
rte_unhide_dummy_routes(net *net, rte **dummy) |
| 950 |
{
|
| 951 |
if (*dummy)
|
| 952 |
{
|
| 953 |
(*dummy)->next = net->routes; |
| 954 |
net->routes = *dummy; |
| 955 |
} |
| 956 |
} |
| 957 |
|
| 958 |
/**
|
| 959 |
* rte_update - enter a new update to a routing table
|
| 960 |
* @table: table to be updated
|
| 961 |
* @ah: pointer to table announce hook
|
| 962 |
* @net: network node
|
| 963 |
* @p: protocol submitting the update
|
| 964 |
* @src: protocol originating the update
|
| 965 |
* @new: a &rte representing the new route or %NULL for route removal.
|
| 966 |
*
|
| 967 |
* This function is called by the routing protocols whenever they discover
|
| 968 |
* a new route or wish to update/remove an existing route. The right announcement
|
| 969 |
* sequence is to build route attributes first (either un-cached with @aflags set
|
| 970 |
* to zero or a cached one using rta_lookup(); in this case please note that
|
| 971 |
* you need to increase the use count of the attributes yourself by calling
|
| 972 |
* rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
|
| 973 |
* the appropriate data and finally submit the new &rte by calling rte_update().
|
| 974 |
*
|
| 975 |
* @src specifies the protocol that originally created the route and the meaning
|
| 976 |
* of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
|
| 977 |
* same value as @new->attrs->proto. @p specifies the protocol that called
|
| 978 |
* rte_update(). In most cases it is the same protocol as @src. rte_update()
|
| 979 |
* stores @p in @new->sender;
|
| 980 |
*
|
| 981 |
* When rte_update() gets any route, it automatically validates it (checks,
|
| 982 |
* whether the network and next hop address are valid IP addresses and also
|
| 983 |
* whether a normal routing protocol doesn't try to smuggle a host or link
|
| 984 |
* scope route to the table), converts all protocol dependent attributes stored
|
| 985 |
* in the &rte to temporary extended attributes, consults import filters of the
|
| 986 |
* protocol to see if the route should be accepted and/or its attributes modified,
|
| 987 |
* stores the temporary attributes back to the &rte.
|
| 988 |
*
|
| 989 |
* Now, having a "public" version of the route, we
|
| 990 |
* automatically find any old route defined by the protocol @src
|
| 991 |
* for network @n, replace it by the new one (or removing it if @new is %NULL),
|
| 992 |
* recalculate the optimal route for this destination and finally broadcast
|
| 993 |
* the change (if any) to all routing protocols by calling rte_announce().
|
| 994 |
*
|
| 995 |
* All memory used for attribute lists and other temporary allocations is taken
|
| 996 |
* from a special linear pool @rte_update_pool and freed when rte_update()
|
| 997 |
* finishes.
|
| 998 |
*/
|
| 999 |
|
| 1000 |
void
|
| 1001 |
rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src) |
| 1002 |
{
|
| 1003 |
struct proto *p = ah->proto;
|
| 1004 |
struct proto_stats *stats = ah->stats;
|
| 1005 |
struct filter *filter = ah->in_filter;
|
| 1006 |
ea_list *tmpa = NULL;
|
| 1007 |
rte *dummy = NULL;
|
| 1008 |
|
| 1009 |
rte_update_lock(); |
| 1010 |
if (new)
|
| 1011 |
{
|
| 1012 |
new->sender = ah; |
| 1013 |
|
| 1014 |
stats->imp_updates_received++; |
| 1015 |
if (!rte_validate(new))
|
| 1016 |
{
|
| 1017 |
rte_trace_in(D_FILTERS, p, new, "invalid");
|
| 1018 |
stats->imp_updates_invalid++; |
| 1019 |
goto drop;
|
| 1020 |
} |
| 1021 |
|
| 1022 |
if (filter == FILTER_REJECT)
|
| 1023 |
{
|
| 1024 |
stats->imp_updates_filtered++; |
| 1025 |
rte_trace_in(D_FILTERS, p, new, "filtered out");
|
| 1026 |
|
| 1027 |
if (! ah->in_keep_filtered)
|
| 1028 |
goto drop;
|
| 1029 |
|
| 1030 |
/* new is a private copy, i could modify it */
|
| 1031 |
new->flags |= REF_FILTERED; |
| 1032 |
} |
| 1033 |
else
|
| 1034 |
{
|
| 1035 |
tmpa = make_tmp_attrs(new, rte_update_pool); |
| 1036 |
if (filter && (filter != FILTER_REJECT))
|
| 1037 |
{
|
| 1038 |
ea_list *old_tmpa = tmpa; |
| 1039 |
int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0); |
| 1040 |
if (fr > F_ACCEPT)
|
| 1041 |
{
|
| 1042 |
stats->imp_updates_filtered++; |
| 1043 |
rte_trace_in(D_FILTERS, p, new, "filtered out");
|
| 1044 |
|
| 1045 |
if (! ah->in_keep_filtered)
|
| 1046 |
goto drop;
|
| 1047 |
|
| 1048 |
new->flags |= REF_FILTERED; |
| 1049 |
} |
| 1050 |
if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
|
| 1051 |
src->proto->store_tmp_attrs(new, tmpa); |
| 1052 |
} |
| 1053 |
} |
| 1054 |
if (!rta_is_cached(new->attrs)) /* Need to copy attributes */ |
| 1055 |
new->attrs = rta_lookup(new->attrs); |
| 1056 |
new->flags |= REF_COW; |
| 1057 |
} |
| 1058 |
else
|
| 1059 |
{
|
| 1060 |
stats->imp_withdraws_received++; |
| 1061 |
|
| 1062 |
if (!net || !src)
|
| 1063 |
{
|
| 1064 |
stats->imp_withdraws_ignored++; |
| 1065 |
rte_update_unlock(); |
| 1066 |
return;
|
| 1067 |
} |
| 1068 |
} |
| 1069 |
|
| 1070 |
recalc:
|
| 1071 |
rte_hide_dummy_routes(net, &dummy); |
| 1072 |
rte_recalculate(ah, net, new, tmpa, src); |
| 1073 |
rte_unhide_dummy_routes(net, &dummy); |
| 1074 |
rte_update_unlock(); |
| 1075 |
return;
|
| 1076 |
|
| 1077 |
drop:
|
| 1078 |
rte_free(new); |
| 1079 |
new = NULL;
|
| 1080 |
tmpa = NULL;
|
| 1081 |
goto recalc;
|
| 1082 |
} |
| 1083 |
|
| 1084 |
/* Independent call to rte_announce(), used from next hop
|
| 1085 |
recalculation, outside of rte_update(). new must be non-NULL */
|
| 1086 |
static inline void |
| 1087 |
rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old)
|
| 1088 |
{
|
| 1089 |
ea_list *tmpa; |
| 1090 |
|
| 1091 |
rte_update_lock(); |
| 1092 |
tmpa = make_tmp_attrs(new, rte_update_pool); |
| 1093 |
rte_announce(tab, type, n, new, old, NULL, tmpa);
|
| 1094 |
rte_update_unlock(); |
| 1095 |
} |
| 1096 |
|
| 1097 |
void
|
| 1098 |
rte_discard(rtable *t, rte *old) /* Non-filtered route deletion, used during garbage collection */
|
| 1099 |
{
|
| 1100 |
rte_update_lock(); |
| 1101 |
rte_recalculate(old->sender, old->net, NULL, NULL, old->attrs->src); |
| 1102 |
rte_update_unlock(); |
| 1103 |
} |
| 1104 |
|
| 1105 |
/* Check rtable for best route to given net whether it would be exported do p */
|
| 1106 |
int
|
| 1107 |
rt_examine(rtable *t, ip_addr prefix, int pxlen, struct proto *p, struct filter *filter) |
| 1108 |
{
|
| 1109 |
net *n = net_find(t, prefix, pxlen); |
| 1110 |
rte *rt = n ? n->routes : NULL;
|
| 1111 |
|
| 1112 |
if (!rte_is_valid(rt))
|
| 1113 |
return 0; |
| 1114 |
|
| 1115 |
rte_update_lock(); |
| 1116 |
|
| 1117 |
/* Rest is stripped down export_filter() */
|
| 1118 |
ea_list *tmpa = make_tmp_attrs(rt, rte_update_pool); |
| 1119 |
int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0; |
| 1120 |
if (v == RIC_PROCESS)
|
| 1121 |
v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT); |
| 1122 |
|
| 1123 |
/* Discard temporary rte */
|
| 1124 |
if (rt != n->routes)
|
| 1125 |
rte_free(rt); |
| 1126 |
|
| 1127 |
rte_update_unlock(); |
| 1128 |
|
| 1129 |
return v > 0; |
| 1130 |
} |
| 1131 |
|
| 1132 |
|
| 1133 |
/**
|
| 1134 |
* rt_refresh_begin - start a refresh cycle
|
| 1135 |
* @t: related routing table
|
| 1136 |
* @ah: related announce hook
|
| 1137 |
*
|
| 1138 |
* This function starts a refresh cycle for given routing table and announce
|
| 1139 |
* hook. The refresh cycle is a sequence where the protocol sends all its valid
|
| 1140 |
* routes to the routing table (by rte_update()). After that, all protocol
|
| 1141 |
* routes (more precisely routes with @ah as @sender) not sent during the
|
| 1142 |
* refresh cycle but still in the table from the past are pruned. This is
|
| 1143 |
* implemented by marking all related routes as stale by REF_STALE flag in
|
| 1144 |
* rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
|
| 1145 |
* flag in rt_refresh_end() and then removing such routes in the prune loop.
|
| 1146 |
*/
|
| 1147 |
void
|
| 1148 |
rt_refresh_begin(rtable *t, struct announce_hook *ah)
|
| 1149 |
{
|
| 1150 |
net *n; |
| 1151 |
rte *e; |
| 1152 |
|
| 1153 |
FIB_WALK(&t->fib, fn) |
| 1154 |
{
|
| 1155 |
n = (net *) fn; |
| 1156 |
for (e = n->routes; e; e = e->next)
|
| 1157 |
if (e->sender == ah)
|
| 1158 |
e->flags |= REF_STALE; |
| 1159 |
} |
| 1160 |
FIB_WALK_END; |
| 1161 |
} |
| 1162 |
|
| 1163 |
/**
|
| 1164 |
* rt_refresh_end - end a refresh cycle
|
| 1165 |
* @t: related routing table
|
| 1166 |
* @ah: related announce hook
|
| 1167 |
*
|
| 1168 |
* This function starts a refresh cycle for given routing table and announce
|
| 1169 |
* hook. See rt_refresh_begin() for description of refresh cycles.
|
| 1170 |
*/
|
| 1171 |
void
|
| 1172 |
rt_refresh_end(rtable *t, struct announce_hook *ah)
|
| 1173 |
{
|
| 1174 |
int prune = 0; |
| 1175 |
net *n; |
| 1176 |
rte *e; |
| 1177 |
|
| 1178 |
FIB_WALK(&t->fib, fn) |
| 1179 |
{
|
| 1180 |
n = (net *) fn; |
| 1181 |
for (e = n->routes; e; e = e->next)
|
| 1182 |
if ((e->sender == ah) && (e->flags & REF_STALE))
|
| 1183 |
{
|
| 1184 |
e->flags |= REF_DISCARD; |
| 1185 |
prune = 1;
|
| 1186 |
} |
| 1187 |
} |
| 1188 |
FIB_WALK_END; |
| 1189 |
|
| 1190 |
if (prune)
|
| 1191 |
rt_schedule_prune(t); |
| 1192 |
} |
| 1193 |
|
| 1194 |
|
| 1195 |
/**
|
| 1196 |
* rte_dump - dump a route
|
| 1197 |
* @e: &rte to be dumped
|
| 1198 |
*
|
| 1199 |
* This functions dumps contents of a &rte to debug output.
|
| 1200 |
*/
|
| 1201 |
void
|
| 1202 |
rte_dump(rte *e) |
| 1203 |
{
|
| 1204 |
net *n = e->net; |
| 1205 |
debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
|
| 1206 |
debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
|
| 1207 |
rta_dump(e->attrs); |
| 1208 |
if (e->attrs->src->proto->proto->dump_attrs)
|
| 1209 |
e->attrs->src->proto->proto->dump_attrs(e); |
| 1210 |
debug("\n");
|
| 1211 |
} |
| 1212 |
|
| 1213 |
/**
|
| 1214 |
* rt_dump - dump a routing table
|
| 1215 |
* @t: routing table to be dumped
|
| 1216 |
*
|
| 1217 |
* This function dumps contents of a given routing table to debug output.
|
| 1218 |
*/
|
| 1219 |
void
|
| 1220 |
rt_dump(rtable *t) |
| 1221 |
{
|
| 1222 |
rte *e; |
| 1223 |
net *n; |
| 1224 |
struct announce_hook *a;
|
| 1225 |
|
| 1226 |
debug("Dump of routing table <%s>\n", t->name);
|
| 1227 |
#ifdef DEBUGGING
|
| 1228 |
fib_check(&t->fib); |
| 1229 |
#endif
|
| 1230 |
FIB_WALK(&t->fib, fn) |
| 1231 |
{
|
| 1232 |
n = (net *) fn; |
| 1233 |
for(e=n->routes; e; e=e->next)
|
| 1234 |
rte_dump(e); |
| 1235 |
} |
| 1236 |
FIB_WALK_END; |
| 1237 |
WALK_LIST(a, t->hooks) |
| 1238 |
debug("\tAnnounces routes to protocol %s\n", a->proto->name);
|
| 1239 |
debug("\n");
|
| 1240 |
} |
| 1241 |
|
| 1242 |
/**
|
| 1243 |
* rt_dump_all - dump all routing tables
|
| 1244 |
*
|
| 1245 |
* This function dumps contents of all routing tables to debug output.
|
| 1246 |
*/
|
| 1247 |
void
|
| 1248 |
rt_dump_all(void)
|
| 1249 |
{
|
| 1250 |
rtable *t; |
| 1251 |
|
| 1252 |
WALK_LIST(t, routing_tables) |
| 1253 |
rt_dump(t); |
| 1254 |
} |
| 1255 |
|
| 1256 |
static inline void |
| 1257 |
rt_schedule_prune(rtable *tab) |
| 1258 |
{
|
| 1259 |
rt_mark_for_prune(tab); |
| 1260 |
ev_schedule(tab->rt_event); |
| 1261 |
} |
| 1262 |
|
| 1263 |
static inline void |
| 1264 |
rt_schedule_gc(rtable *tab) |
| 1265 |
{
|
| 1266 |
if (tab->gc_scheduled)
|
| 1267 |
return;
|
| 1268 |
|
| 1269 |
tab->gc_scheduled = 1;
|
| 1270 |
ev_schedule(tab->rt_event); |
| 1271 |
} |
| 1272 |
|
| 1273 |
static inline void |
| 1274 |
rt_schedule_hcu(rtable *tab) |
| 1275 |
{
|
| 1276 |
if (tab->hcu_scheduled)
|
| 1277 |
return;
|
| 1278 |
|
| 1279 |
tab->hcu_scheduled = 1;
|
| 1280 |
ev_schedule(tab->rt_event); |
| 1281 |
} |
| 1282 |
|
| 1283 |
static inline void |
| 1284 |
rt_schedule_nhu(rtable *tab) |
| 1285 |
{
|
| 1286 |
if (tab->nhu_state == 0) |
| 1287 |
ev_schedule(tab->rt_event); |
| 1288 |
|
| 1289 |
/* state change 0->1, 2->3 */
|
| 1290 |
tab->nhu_state |= 1;
|
| 1291 |
} |
| 1292 |
|
| 1293 |
|
| 1294 |
static void |
| 1295 |
rt_prune_nets(rtable *tab) |
| 1296 |
{
|
| 1297 |
struct fib_iterator fit;
|
| 1298 |
int ncnt = 0, ndel = 0; |
| 1299 |
|
| 1300 |
#ifdef DEBUGGING
|
| 1301 |
fib_check(&tab->fib); |
| 1302 |
#endif
|
| 1303 |
|
| 1304 |
FIB_ITERATE_INIT(&fit, &tab->fib); |
| 1305 |
again:
|
| 1306 |
FIB_ITERATE_START(&tab->fib, &fit, f) |
| 1307 |
{
|
| 1308 |
net *n = (net *) f; |
| 1309 |
ncnt++; |
| 1310 |
if (!n->routes) /* Orphaned FIB entry */ |
| 1311 |
{
|
| 1312 |
FIB_ITERATE_PUT(&fit, f); |
| 1313 |
fib_delete(&tab->fib, f); |
| 1314 |
ndel++; |
| 1315 |
goto again;
|
| 1316 |
} |
| 1317 |
} |
| 1318 |
FIB_ITERATE_END(f); |
| 1319 |
DBG("Pruned %d of %d networks\n", ndel, ncnt);
|
| 1320 |
|
| 1321 |
tab->gc_counter = 0;
|
| 1322 |
tab->gc_time = now; |
| 1323 |
tab->gc_scheduled = 0;
|
| 1324 |
} |
| 1325 |
|
| 1326 |
static void |
| 1327 |
rt_event(void *ptr)
|
| 1328 |
{
|
| 1329 |
rtable *tab = ptr; |
| 1330 |
|
| 1331 |
if (tab->hcu_scheduled)
|
| 1332 |
rt_update_hostcache(tab); |
| 1333 |
|
| 1334 |
if (tab->nhu_state)
|
| 1335 |
rt_next_hop_update(tab); |
| 1336 |
|
| 1337 |
if (tab->prune_state)
|
| 1338 |
if (!rt_prune_table(tab))
|
| 1339 |
{
|
| 1340 |
/* Table prune unfinished */
|
| 1341 |
ev_schedule(tab->rt_event); |
| 1342 |
return;
|
| 1343 |
} |
| 1344 |
|
| 1345 |
if (tab->gc_scheduled)
|
| 1346 |
{
|
| 1347 |
rt_prune_nets(tab); |
| 1348 |
rt_prune_sources(); // FIXME this should be moved to independent event
|
| 1349 |
} |
| 1350 |
} |
| 1351 |
|
| 1352 |
void
|
| 1353 |
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf) |
| 1354 |
{
|
| 1355 |
bzero(t, sizeof(*t));
|
| 1356 |
fib_init(&t->fib, p, sizeof(net), 0, rte_init); |
| 1357 |
t->name = name; |
| 1358 |
t->config = cf; |
| 1359 |
init_list(&t->hooks); |
| 1360 |
if (cf)
|
| 1361 |
{
|
| 1362 |
t->rt_event = ev_new(p); |
| 1363 |
t->rt_event->hook = rt_event; |
| 1364 |
t->rt_event->data = t; |
| 1365 |
t->gc_time = now; |
| 1366 |
} |
| 1367 |
} |
| 1368 |
|
| 1369 |
/**
|
| 1370 |
* rt_init - initialize routing tables
|
| 1371 |
*
|
| 1372 |
* This function is called during BIRD startup. It initializes the
|
| 1373 |
* routing table module.
|
| 1374 |
*/
|
| 1375 |
void
|
| 1376 |
rt_init(void)
|
| 1377 |
{
|
| 1378 |
rta_init(); |
| 1379 |
rt_table_pool = rp_new(&root_pool, "Routing tables");
|
| 1380 |
rte_update_pool = lp_new(rt_table_pool, 4080);
|
| 1381 |
rte_slab = sl_new(rt_table_pool, sizeof(rte));
|
| 1382 |
init_list(&routing_tables); |
| 1383 |
} |
| 1384 |
|
| 1385 |
|
| 1386 |
static int |
| 1387 |
rt_prune_step(rtable *tab, int *limit)
|
| 1388 |
{
|
| 1389 |
struct fib_iterator *fit = &tab->prune_fit;
|
| 1390 |
|
| 1391 |
DBG("Pruning route table %s\n", tab->name);
|
| 1392 |
#ifdef DEBUGGING
|
| 1393 |
fib_check(&tab->fib); |
| 1394 |
#endif
|
| 1395 |
|
| 1396 |
if (tab->prune_state == RPS_NONE)
|
| 1397 |
return 1; |
| 1398 |
|
| 1399 |
if (tab->prune_state == RPS_SCHEDULED)
|
| 1400 |
{
|
| 1401 |
FIB_ITERATE_INIT(fit, &tab->fib); |
| 1402 |
tab->prune_state = RPS_RUNNING; |
| 1403 |
} |
| 1404 |
|
| 1405 |
again:
|
| 1406 |
FIB_ITERATE_START(&tab->fib, fit, fn) |
| 1407 |
{
|
| 1408 |
net *n = (net *) fn; |
| 1409 |
rte *e; |
| 1410 |
|
| 1411 |
rescan:
|
| 1412 |
for (e=n->routes; e; e=e->next)
|
| 1413 |
if (e->sender->proto->flushing || (e->flags & REF_DISCARD))
|
| 1414 |
{
|
| 1415 |
if (*limit <= 0) |
| 1416 |
{
|
| 1417 |
FIB_ITERATE_PUT(fit, fn); |
| 1418 |
return 0; |
| 1419 |
} |
| 1420 |
|
| 1421 |
rte_discard(tab, e); |
| 1422 |
(*limit)--; |
| 1423 |
|
| 1424 |
goto rescan;
|
| 1425 |
} |
| 1426 |
if (!n->routes) /* Orphaned FIB entry */ |
| 1427 |
{
|
| 1428 |
FIB_ITERATE_PUT(fit, fn); |
| 1429 |
fib_delete(&tab->fib, fn); |
| 1430 |
goto again;
|
| 1431 |
} |
| 1432 |
} |
| 1433 |
FIB_ITERATE_END(fn); |
| 1434 |
|
| 1435 |
#ifdef DEBUGGING
|
| 1436 |
fib_check(&tab->fib); |
| 1437 |
#endif
|
| 1438 |
|
| 1439 |
tab->prune_state = RPS_NONE; |
| 1440 |
return 1; |
| 1441 |
} |
| 1442 |
|
| 1443 |
/**
|
| 1444 |
* rt_prune_table - prune a routing table
|
| 1445 |
*
|
| 1446 |
* This function scans the routing table @tab and removes routes belonging to
|
| 1447 |
* flushing protocols, discarded routes and also stale network entries, in a
|
| 1448 |
* similar fashion like rt_prune_loop(). Returns 1 when all such routes are
|
| 1449 |
* pruned. Contrary to rt_prune_loop(), this function is not a part of the
|
| 1450 |
* protocol flushing loop, but it is called from rt_event() for just one routing
|
| 1451 |
* table.
|
| 1452 |
*
|
| 1453 |
* Note that rt_prune_table() and rt_prune_loop() share (for each table) the
|
| 1454 |
* prune state (@prune_state) and also the pruning iterator (@prune_fit).
|
| 1455 |
*/
|
| 1456 |
static inline int |
| 1457 |
rt_prune_table(rtable *tab) |
| 1458 |
{
|
| 1459 |
int limit = 512; |
| 1460 |
return rt_prune_step(tab, &limit);
|
| 1461 |
} |
| 1462 |
|
| 1463 |
/**
|
| 1464 |
* rt_prune_loop - prune routing tables
|
| 1465 |
*
|
| 1466 |
* The prune loop scans routing tables and removes routes belonging to flushing
|
| 1467 |
* protocols, discarded routes and also stale network entries. Returns 1 when
|
| 1468 |
* all such routes are pruned. It is a part of the protocol flushing loop.
|
| 1469 |
*/
|
| 1470 |
int
|
| 1471 |
rt_prune_loop(void)
|
| 1472 |
{
|
| 1473 |
int limit = 512; |
| 1474 |
rtable *t; |
| 1475 |
|
| 1476 |
WALK_LIST(t, routing_tables) |
| 1477 |
if (! rt_prune_step(t, &limit))
|
| 1478 |
return 0; |
| 1479 |
|
| 1480 |
return 1; |
| 1481 |
} |
| 1482 |
|
| 1483 |
void
|
| 1484 |
rt_preconfig(struct config *c)
|
| 1485 |
{
|
| 1486 |
struct symbol *s = cf_find_symbol("master"); |
| 1487 |
|
| 1488 |
init_list(&c->tables); |
| 1489 |
c->master_rtc = rt_new_table(s); |
| 1490 |
} |
| 1491 |
|
| 1492 |
|
| 1493 |
/*
|
| 1494 |
* Some functions for handing internal next hop updates
|
| 1495 |
* triggered by rt_schedule_nhu().
|
| 1496 |
*/
|
| 1497 |
|
| 1498 |
static inline int |
| 1499 |
rta_next_hop_outdated(rta *a) |
| 1500 |
{
|
| 1501 |
struct hostentry *he = a->hostentry;
|
| 1502 |
|
| 1503 |
if (!he)
|
| 1504 |
return 0; |
| 1505 |
|
| 1506 |
if (!he->src)
|
| 1507 |
return a->dest != RTD_UNREACHABLE;
|
| 1508 |
|
| 1509 |
return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) ||
|
| 1510 |
(a->dest != he->dest) || (a->igp_metric != he->igp_metric) || |
| 1511 |
!mpnh_same(a->nexthops, he->src->nexthops); |
| 1512 |
} |
| 1513 |
|
| 1514 |
static inline void |
| 1515 |
rta_apply_hostentry(rta *a, struct hostentry *he)
|
| 1516 |
{
|
| 1517 |
a->hostentry = he; |
| 1518 |
a->iface = he->src ? he->src->iface : NULL;
|
| 1519 |
a->gw = he->gw; |
| 1520 |
a->dest = he->dest; |
| 1521 |
a->igp_metric = he->igp_metric; |
| 1522 |
a->nexthops = he->src ? he->src->nexthops : NULL;
|
| 1523 |
} |
| 1524 |
|
| 1525 |
static inline rte * |
| 1526 |
rt_next_hop_update_rte(rtable *tab, rte *old) |
| 1527 |
{
|
| 1528 |
rta a; |
| 1529 |
memcpy(&a, old->attrs, sizeof(rta));
|
| 1530 |
rta_apply_hostentry(&a, old->attrs->hostentry); |
| 1531 |
a.aflags = 0;
|
| 1532 |
|
| 1533 |
rte *e = sl_alloc(rte_slab); |
| 1534 |
memcpy(e, old, sizeof(rte));
|
| 1535 |
e->attrs = rta_lookup(&a); |
| 1536 |
|
| 1537 |
return e;
|
| 1538 |
} |
| 1539 |
|
| 1540 |
static inline int |
| 1541 |
rt_next_hop_update_net(rtable *tab, net *n) |
| 1542 |
{
|
| 1543 |
rte **k, *e, *new, *old_best, **new_best; |
| 1544 |
int count = 0; |
| 1545 |
int free_old_best = 0; |
| 1546 |
|
| 1547 |
old_best = n->routes; |
| 1548 |
if (!old_best)
|
| 1549 |
return 0; |
| 1550 |
|
| 1551 |
for (k = &n->routes; e = *k; k = &e->next)
|
| 1552 |
if (rta_next_hop_outdated(e->attrs))
|
| 1553 |
{
|
| 1554 |
new = rt_next_hop_update_rte(tab, e); |
| 1555 |
*k = new; |
| 1556 |
|
| 1557 |
rte_announce_i(tab, RA_ANY, n, new, e); |
| 1558 |
rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
|
| 1559 |
|
| 1560 |
/* Call a pre-comparison hook */
|
| 1561 |
/* Not really an efficient way to compute this */
|
| 1562 |
if (e->attrs->src->proto->rte_recalculate)
|
| 1563 |
e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
|
| 1564 |
|
| 1565 |
if (e != old_best)
|
| 1566 |
rte_free_quick(e); |
| 1567 |
else /* Freeing of the old best rte is postponed */ |
| 1568 |
free_old_best = 1;
|
| 1569 |
|
| 1570 |
e = new; |
| 1571 |
count++; |
| 1572 |
} |
| 1573 |
|
| 1574 |
if (!count)
|
| 1575 |
return 0; |
| 1576 |
|
| 1577 |
/* Find the new best route */
|
| 1578 |
new_best = NULL;
|
| 1579 |
for (k = &n->routes; e = *k; k = &e->next)
|
| 1580 |
{
|
| 1581 |
if (!new_best || rte_better(e, *new_best))
|
| 1582 |
new_best = k; |
| 1583 |
} |
| 1584 |
|
| 1585 |
/* Relink the new best route to the first position */
|
| 1586 |
new = *new_best; |
| 1587 |
if (new != n->routes)
|
| 1588 |
{
|
| 1589 |
*new_best = new->next; |
| 1590 |
new->next = n->routes; |
| 1591 |
n->routes = new; |
| 1592 |
} |
| 1593 |
|
| 1594 |
/* Announce the new best route */
|
| 1595 |
if (new != old_best)
|
| 1596 |
{
|
| 1597 |
rte_announce_i(tab, RA_OPTIMAL, n, new, old_best); |
| 1598 |
rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
|
| 1599 |
} |
| 1600 |
|
| 1601 |
if (free_old_best)
|
| 1602 |
rte_free_quick(old_best); |
| 1603 |
|
| 1604 |
return count;
|
| 1605 |
} |
| 1606 |
|
| 1607 |
static void |
| 1608 |
rt_next_hop_update(rtable *tab) |
| 1609 |
{
|
| 1610 |
struct fib_iterator *fit = &tab->nhu_fit;
|
| 1611 |
int max_feed = 32; |
| 1612 |
|
| 1613 |
if (tab->nhu_state == 0) |
| 1614 |
return;
|
| 1615 |
|
| 1616 |
if (tab->nhu_state == 1) |
| 1617 |
{
|
| 1618 |
FIB_ITERATE_INIT(fit, &tab->fib); |
| 1619 |
tab->nhu_state = 2;
|
| 1620 |
} |
| 1621 |
|
| 1622 |
FIB_ITERATE_START(&tab->fib, fit, fn) |
| 1623 |
{
|
| 1624 |
if (max_feed <= 0) |
| 1625 |
{
|
| 1626 |
FIB_ITERATE_PUT(fit, fn); |
| 1627 |
ev_schedule(tab->rt_event); |
| 1628 |
return;
|
| 1629 |
} |
| 1630 |
max_feed -= rt_next_hop_update_net(tab, (net *) fn); |
| 1631 |
} |
| 1632 |
FIB_ITERATE_END(fn); |
| 1633 |
|
| 1634 |
/* state change 2->0, 3->1 */
|
| 1635 |
tab->nhu_state &= 1;
|
| 1636 |
|
| 1637 |
if (tab->nhu_state > 0) |
| 1638 |
ev_schedule(tab->rt_event); |
| 1639 |
} |
| 1640 |
|
| 1641 |
|
| 1642 |
struct rtable_config *
|
| 1643 |
rt_new_table(struct symbol *s)
|
| 1644 |
{
|
| 1645 |
/* Hack that allows to 'redefine' the master table */
|
| 1646 |
if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc))
|
| 1647 |
return s->def;
|
| 1648 |
|
| 1649 |
struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config)); |
| 1650 |
|
| 1651 |
cf_define_symbol(s, SYM_TABLE, c); |
| 1652 |
c->name = s->name; |
| 1653 |
add_tail(&new_config->tables, &c->n); |
| 1654 |
c->gc_max_ops = 1000;
|
| 1655 |
c->gc_min_time = 5;
|
| 1656 |
return c;
|
| 1657 |
} |
| 1658 |
|
| 1659 |
/**
|
| 1660 |
* rt_lock_table - lock a routing table
|
| 1661 |
* @r: routing table to be locked
|
| 1662 |
*
|
| 1663 |
* Lock a routing table, because it's in use by a protocol,
|
| 1664 |
* preventing it from being freed when it gets undefined in a new
|
| 1665 |
* configuration.
|
| 1666 |
*/
|
| 1667 |
void
|
| 1668 |
rt_lock_table(rtable *r) |
| 1669 |
{
|
| 1670 |
r->use_count++; |
| 1671 |
} |
| 1672 |
|
| 1673 |
/**
|
| 1674 |
* rt_unlock_table - unlock a routing table
|
| 1675 |
* @r: routing table to be unlocked
|
| 1676 |
*
|
| 1677 |
* Unlock a routing table formerly locked by rt_lock_table(),
|
| 1678 |
* that is decrease its use count and delete it if it's scheduled
|
| 1679 |
* for deletion by configuration changes.
|
| 1680 |
*/
|
| 1681 |
void
|
| 1682 |
rt_unlock_table(rtable *r) |
| 1683 |
{
|
| 1684 |
if (!--r->use_count && r->deleted)
|
| 1685 |
{
|
| 1686 |
struct config *conf = r->deleted;
|
| 1687 |
DBG("Deleting routing table %s\n", r->name);
|
| 1688 |
if (r->hostcache)
|
| 1689 |
rt_free_hostcache(r); |
| 1690 |
rem_node(&r->n); |
| 1691 |
fib_free(&r->fib); |
| 1692 |
rfree(r->rt_event); |
| 1693 |
mb_free(r); |
| 1694 |
config_del_obstacle(conf); |
| 1695 |
} |
| 1696 |
} |
| 1697 |
|
| 1698 |
/**
|
| 1699 |
* rt_commit - commit new routing table configuration
|
| 1700 |
* @new: new configuration
|
| 1701 |
* @old: original configuration or %NULL if it's boot time config
|
| 1702 |
*
|
| 1703 |
* Scan differences between @old and @new configuration and modify
|
| 1704 |
* the routing tables according to these changes. If @new defines a
|
| 1705 |
* previously unknown table, create it, if it omits a table existing
|
| 1706 |
* in @old, schedule it for deletion (it gets deleted when all protocols
|
| 1707 |
* disconnect from it by calling rt_unlock_table()), if it exists
|
| 1708 |
* in both configurations, leave it unchanged.
|
| 1709 |
*/
|
| 1710 |
void
|
| 1711 |
rt_commit(struct config *new, struct config *old) |
| 1712 |
{
|
| 1713 |
struct rtable_config *o, *r;
|
| 1714 |
|
| 1715 |
DBG("rt_commit:\n");
|
| 1716 |
if (old)
|
| 1717 |
{
|
| 1718 |
WALK_LIST(o, old->tables) |
| 1719 |
{
|
| 1720 |
rtable *ot = o->table; |
| 1721 |
if (!ot->deleted)
|
| 1722 |
{
|
| 1723 |
struct symbol *sym = cf_find_symbol(o->name);
|
| 1724 |
if (sym && sym->class == SYM_TABLE && !new->shutdown)
|
| 1725 |
{
|
| 1726 |
DBG("\t%s: same\n", o->name);
|
| 1727 |
r = sym->def; |
| 1728 |
r->table = ot; |
| 1729 |
ot->name = r->name; |
| 1730 |
ot->config = r; |
| 1731 |
if (o->sorted != r->sorted)
|
| 1732 |
log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
|
| 1733 |
} |
| 1734 |
else
|
| 1735 |
{
|
| 1736 |
DBG("\t%s: deleted\n", o->name);
|
| 1737 |
ot->deleted = old; |
| 1738 |
config_add_obstacle(old); |
| 1739 |
rt_lock_table(ot); |
| 1740 |
rt_unlock_table(ot); |
| 1741 |
} |
| 1742 |
} |
| 1743 |
} |
| 1744 |
} |
| 1745 |
|
| 1746 |
WALK_LIST(r, new->tables) |
| 1747 |
if (!r->table)
|
| 1748 |
{
|
| 1749 |
rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable)); |
| 1750 |
DBG("\t%s: created\n", r->name);
|
| 1751 |
rt_setup(rt_table_pool, t, r->name, r); |
| 1752 |
add_tail(&routing_tables, &t->n); |
| 1753 |
r->table = t; |
| 1754 |
} |
| 1755 |
DBG("\tdone\n");
|
| 1756 |
} |
| 1757 |
|
| 1758 |
static inline void |
| 1759 |
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e) |
| 1760 |
{
|
| 1761 |
ea_list *tmpa; |
| 1762 |
|
| 1763 |
rte_update_lock(); |
| 1764 |
tmpa = make_tmp_attrs(e, rte_update_pool); |
| 1765 |
if (type == RA_ACCEPTED)
|
| 1766 |
rt_notify_accepted(h, n, e, NULL, NULL, tmpa, p->refeeding ? 2 : 1); |
| 1767 |
else
|
| 1768 |
rt_notify_basic(h, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding);
|
| 1769 |
rte_update_unlock(); |
| 1770 |
} |
| 1771 |
|
| 1772 |
/**
|
| 1773 |
* rt_feed_baby - advertise routes to a new protocol
|
| 1774 |
* @p: protocol to be fed
|
| 1775 |
*
|
| 1776 |
* This function performs one pass of advertisement of routes to a newly
|
| 1777 |
* initialized protocol. It's called by the protocol code as long as it
|
| 1778 |
* has something to do. (We avoid transferring all the routes in single
|
| 1779 |
* pass in order not to monopolize CPU time.)
|
| 1780 |
*/
|
| 1781 |
int
|
| 1782 |
rt_feed_baby(struct proto *p)
|
| 1783 |
{
|
| 1784 |
struct announce_hook *h;
|
| 1785 |
struct fib_iterator *fit;
|
| 1786 |
int max_feed = 256; |
| 1787 |
|
| 1788 |
if (!p->feed_ahook) /* Need to initialize first */ |
| 1789 |
{
|
| 1790 |
if (!p->ahooks)
|
| 1791 |
return 1; |
| 1792 |
DBG("Announcing routes to new protocol %s\n", p->name);
|
| 1793 |
p->feed_ahook = p->ahooks; |
| 1794 |
fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator)); |
| 1795 |
goto next_hook;
|
| 1796 |
} |
| 1797 |
fit = p->feed_iterator; |
| 1798 |
|
| 1799 |
again:
|
| 1800 |
h = p->feed_ahook; |
| 1801 |
FIB_ITERATE_START(&h->table->fib, fit, fn) |
| 1802 |
{
|
| 1803 |
net *n = (net *) fn; |
| 1804 |
rte *e = n->routes; |
| 1805 |
if (max_feed <= 0) |
| 1806 |
{
|
| 1807 |
FIB_ITERATE_PUT(fit, fn); |
| 1808 |
return 0; |
| 1809 |
} |
| 1810 |
|
| 1811 |
/* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
|
| 1812 |
|
| 1813 |
if ((p->accept_ra_types == RA_OPTIMAL) ||
|
| 1814 |
(p->accept_ra_types == RA_ACCEPTED)) |
| 1815 |
if (rte_is_valid(e))
|
| 1816 |
{
|
| 1817 |
if (p->export_state != ES_FEEDING)
|
| 1818 |
return 1; /* In the meantime, the protocol fell down. */ |
| 1819 |
do_feed_baby(p, p->accept_ra_types, h, n, e); |
| 1820 |
max_feed--; |
| 1821 |
} |
| 1822 |
|
| 1823 |
if (p->accept_ra_types == RA_ANY)
|
| 1824 |
for(e = n->routes; rte_is_valid(e); e = e->next)
|
| 1825 |
{
|
| 1826 |
if (p->export_state != ES_FEEDING)
|
| 1827 |
return 1; /* In the meantime, the protocol fell down. */ |
| 1828 |
do_feed_baby(p, RA_ANY, h, n, e); |
| 1829 |
max_feed--; |
| 1830 |
} |
| 1831 |
} |
| 1832 |
FIB_ITERATE_END(fn); |
| 1833 |
p->feed_ahook = h->next; |
| 1834 |
if (!p->feed_ahook)
|
| 1835 |
{
|
| 1836 |
mb_free(p->feed_iterator); |
| 1837 |
p->feed_iterator = NULL;
|
| 1838 |
return 1; |
| 1839 |
} |
| 1840 |
|
| 1841 |
next_hook:
|
| 1842 |
h = p->feed_ahook; |
| 1843 |
FIB_ITERATE_INIT(fit, &h->table->fib); |
| 1844 |
goto again;
|
| 1845 |
} |
| 1846 |
|
| 1847 |
/**
|
| 1848 |
* rt_feed_baby_abort - abort protocol feeding
|
| 1849 |
* @p: protocol
|
| 1850 |
*
|
| 1851 |
* This function is called by the protocol code when the protocol
|
| 1852 |
* stops or ceases to exist before the last iteration of rt_feed_baby()
|
| 1853 |
* has finished.
|
| 1854 |
*/
|
| 1855 |
void
|
| 1856 |
rt_feed_baby_abort(struct proto *p)
|
| 1857 |
{
|
| 1858 |
if (p->feed_ahook)
|
| 1859 |
{
|
| 1860 |
/* Unlink the iterator and exit */
|
| 1861 |
fit_get(&p->feed_ahook->table->fib, p->feed_iterator); |
| 1862 |
p->feed_ahook = NULL;
|
| 1863 |
} |
| 1864 |
} |
| 1865 |
|
| 1866 |
|
| 1867 |
static inline unsigned |
| 1868 |
ptr_hash(void *ptr)
|
| 1869 |
{
|
| 1870 |
uintptr_t p = (uintptr_t) ptr; |
| 1871 |
return p ^ (p << 8) ^ (p >> 16); |
| 1872 |
} |
| 1873 |
|
| 1874 |
static inline unsigned |
| 1875 |
hc_hash(ip_addr a, rtable *dep) |
| 1876 |
{
|
| 1877 |
return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff; |
| 1878 |
} |
| 1879 |
|
| 1880 |
static inline void |
| 1881 |
hc_insert(struct hostcache *hc, struct hostentry *he) |
| 1882 |
{
|
| 1883 |
uint k = he->hash_key >> hc->hash_shift; |
| 1884 |
he->next = hc->hash_table[k]; |
| 1885 |
hc->hash_table[k] = he; |
| 1886 |
} |
| 1887 |
|
| 1888 |
static inline void |
| 1889 |
hc_remove(struct hostcache *hc, struct hostentry *he) |
| 1890 |
{
|
| 1891 |
struct hostentry **hep;
|
| 1892 |
uint k = he->hash_key >> hc->hash_shift; |
| 1893 |
|
| 1894 |
for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
|
| 1895 |
*hep = he->next; |
| 1896 |
} |
| 1897 |
|
| 1898 |
#define HC_DEF_ORDER 10 |
| 1899 |
#define HC_HI_MARK *4 |
| 1900 |
#define HC_HI_STEP 2 |
| 1901 |
#define HC_HI_ORDER 16 /* Must be at most 16 */ |
| 1902 |
#define HC_LO_MARK /5 |
| 1903 |
#define HC_LO_STEP 2 |
| 1904 |
#define HC_LO_ORDER 10 |
| 1905 |
|
| 1906 |
static void |
| 1907 |
hc_alloc_table(struct hostcache *hc, unsigned order) |
| 1908 |
{
|
| 1909 |
unsigned hsize = 1 << order; |
| 1910 |
hc->hash_order = order; |
| 1911 |
hc->hash_shift = 16 - order;
|
| 1912 |
hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
|
| 1913 |
hc->hash_min = (order <= HC_LO_ORDER) ? 0 : (hsize HC_LO_MARK);
|
| 1914 |
|
| 1915 |
hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *)); |
| 1916 |
} |
| 1917 |
|
| 1918 |
static void |
| 1919 |
hc_resize(struct hostcache *hc, unsigned new_order) |
| 1920 |
{
|
| 1921 |
unsigned old_size = 1 << hc->hash_order; |
| 1922 |
struct hostentry **old_table = hc->hash_table;
|
| 1923 |
struct hostentry *he, *hen;
|
| 1924 |
int i;
|
| 1925 |
|
| 1926 |
hc_alloc_table(hc, new_order); |
| 1927 |
for (i = 0; i < old_size; i++) |
| 1928 |
for (he = old_table[i]; he != NULL; he=hen) |
| 1929 |
{
|
| 1930 |
hen = he->next; |
| 1931 |
hc_insert(hc, he); |
| 1932 |
} |
| 1933 |
mb_free(old_table); |
| 1934 |
} |
| 1935 |
|
| 1936 |
static struct hostentry * |
| 1937 |
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k) |
| 1938 |
{
|
| 1939 |
struct hostentry *he = sl_alloc(hc->slab);
|
| 1940 |
|
| 1941 |
he->addr = a; |
| 1942 |
he->link = ll; |
| 1943 |
he->tab = dep; |
| 1944 |
he->hash_key = k; |
| 1945 |
he->uc = 0;
|
| 1946 |
he->src = NULL;
|
| 1947 |
|
| 1948 |
add_tail(&hc->hostentries, &he->ln); |
| 1949 |
hc_insert(hc, he); |
| 1950 |
|
| 1951 |
hc->hash_items++; |
| 1952 |
if (hc->hash_items > hc->hash_max)
|
| 1953 |
hc_resize(hc, hc->hash_order + HC_HI_STEP); |
| 1954 |
|
| 1955 |
return he;
|
| 1956 |
} |
| 1957 |
|
| 1958 |
static void |
| 1959 |
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he) |
| 1960 |
{
|
| 1961 |
rta_free(he->src); |
| 1962 |
|
| 1963 |
rem_node(&he->ln); |
| 1964 |
hc_remove(hc, he); |
| 1965 |
sl_free(hc->slab, he); |
| 1966 |
|
| 1967 |
hc->hash_items--; |
| 1968 |
if (hc->hash_items < hc->hash_min)
|
| 1969 |
hc_resize(hc, hc->hash_order - HC_LO_STEP); |
| 1970 |
} |
| 1971 |
|
| 1972 |
static void |
| 1973 |
rt_init_hostcache(rtable *tab) |
| 1974 |
{
|
| 1975 |
struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache)); |
| 1976 |
init_list(&hc->hostentries); |
| 1977 |
|
| 1978 |
hc->hash_items = 0;
|
| 1979 |
hc_alloc_table(hc, HC_DEF_ORDER); |
| 1980 |
hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry)); |
| 1981 |
|
| 1982 |
hc->lp = lp_new(rt_table_pool, 1008);
|
| 1983 |
hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node)); |
| 1984 |
|
| 1985 |
tab->hostcache = hc; |
| 1986 |
} |
| 1987 |
|
| 1988 |
static void |
| 1989 |
rt_free_hostcache(rtable *tab) |
| 1990 |
{
|
| 1991 |
struct hostcache *hc = tab->hostcache;
|
| 1992 |
|
| 1993 |
node *n; |
| 1994 |
WALK_LIST(n, hc->hostentries) |
| 1995 |
{
|
| 1996 |
struct hostentry *he = SKIP_BACK(struct hostentry, ln, n); |
| 1997 |
rta_free(he->src); |
| 1998 |
|
| 1999 |
if (he->uc)
|
| 2000 |
log(L_ERR "Hostcache is not empty in table %s", tab->name);
|
| 2001 |
} |
| 2002 |
|
| 2003 |
rfree(hc->slab); |
| 2004 |
rfree(hc->lp); |
| 2005 |
mb_free(hc->hash_table); |
| 2006 |
mb_free(hc); |
| 2007 |
} |
| 2008 |
|
| 2009 |
static void |
| 2010 |
rt_notify_hostcache(rtable *tab, net *net) |
| 2011 |
{
|
| 2012 |
struct hostcache *hc = tab->hostcache;
|
| 2013 |
|
| 2014 |
if (tab->hcu_scheduled)
|
| 2015 |
return;
|
| 2016 |
|
| 2017 |
if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
|
| 2018 |
rt_schedule_hcu(tab); |
| 2019 |
} |
| 2020 |
|
| 2021 |
static int |
| 2022 |
if_local_addr(ip_addr a, struct iface *i)
|
| 2023 |
{
|
| 2024 |
struct ifa *b;
|
| 2025 |
|
| 2026 |
WALK_LIST(b, i->addrs) |
| 2027 |
if (ipa_equal(a, b->ip))
|
| 2028 |
return 1; |
| 2029 |
|
| 2030 |
return 0; |
| 2031 |
} |
| 2032 |
|
| 2033 |
static u32
|
| 2034 |
rt_get_igp_metric(rte *rt) |
| 2035 |
{
|
| 2036 |
eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC); |
| 2037 |
|
| 2038 |
if (ea)
|
| 2039 |
return ea->u.data;
|
| 2040 |
|
| 2041 |
rta *a = rt->attrs; |
| 2042 |
|
| 2043 |
#ifdef CONFIG_OSPF
|
| 2044 |
if ((a->source == RTS_OSPF) ||
|
| 2045 |
(a->source == RTS_OSPF_IA) || |
| 2046 |
(a->source == RTS_OSPF_EXT1)) |
| 2047 |
return rt->u.ospf.metric1;
|
| 2048 |
#endif
|
| 2049 |
|
| 2050 |
#ifdef CONFIG_RIP
|
| 2051 |
if (a->source == RTS_RIP)
|
| 2052 |
return rt->u.rip.metric;
|
| 2053 |
#endif
|
| 2054 |
|
| 2055 |
/* Device routes */
|
| 2056 |
if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
|
| 2057 |
return 0; |
| 2058 |
|
| 2059 |
return IGP_METRIC_UNKNOWN;
|
| 2060 |
} |
| 2061 |
|
| 2062 |
static int |
| 2063 |
rt_update_hostentry(rtable *tab, struct hostentry *he)
|
| 2064 |
{
|
| 2065 |
rta *old_src = he->src; |
| 2066 |
int pxlen = 0; |
| 2067 |
|
| 2068 |
/* Reset the hostentry */
|
| 2069 |
he->src = NULL;
|
| 2070 |
he->gw = IPA_NONE; |
| 2071 |
he->dest = RTD_UNREACHABLE; |
| 2072 |
he->igp_metric = 0;
|
| 2073 |
|
| 2074 |
net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH); |
| 2075 |
if (n)
|
| 2076 |
{
|
| 2077 |
rte *e = n->routes; |
| 2078 |
rta *a = e->attrs; |
| 2079 |
pxlen = n->n.pxlen; |
| 2080 |
|
| 2081 |
if (a->hostentry)
|
| 2082 |
{
|
| 2083 |
/* Recursive route should not depend on another recursive route */
|
| 2084 |
log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d",
|
| 2085 |
he->addr, n->n.prefix, pxlen); |
| 2086 |
goto done;
|
| 2087 |
} |
| 2088 |
|
| 2089 |
if (a->dest == RTD_DEVICE)
|
| 2090 |
{
|
| 2091 |
if (if_local_addr(he->addr, a->iface))
|
| 2092 |
{
|
| 2093 |
/* The host address is a local address, this is not valid */
|
| 2094 |
log(L_WARN "Next hop address %I is a local address of iface %s",
|
| 2095 |
he->addr, a->iface->name); |
| 2096 |
goto done;
|
| 2097 |
} |
| 2098 |
|
| 2099 |
/* The host is directly reachable, use link as a gateway */
|
| 2100 |
he->gw = he->link; |
| 2101 |
he->dest = RTD_ROUTER; |
| 2102 |
} |
| 2103 |
else
|
| 2104 |
{
|
| 2105 |
/* The host is reachable through some route entry */
|
| 2106 |
he->gw = a->gw; |
| 2107 |
he->dest = a->dest; |
| 2108 |
} |
| 2109 |
|
| 2110 |
he->src = rta_clone(a); |
| 2111 |
he->igp_metric = rt_get_igp_metric(e); |
| 2112 |
} |
| 2113 |
|
| 2114 |
done:
|
| 2115 |
/* Add a prefix range to the trie */
|
| 2116 |
trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH); |
| 2117 |
|
| 2118 |
rta_free(old_src); |
| 2119 |
return old_src != he->src;
|
| 2120 |
} |
| 2121 |
|
| 2122 |
static void |
| 2123 |
rt_update_hostcache(rtable *tab) |
| 2124 |
{
|
| 2125 |
struct hostcache *hc = tab->hostcache;
|
| 2126 |
struct hostentry *he;
|
| 2127 |
node *n, *x; |
| 2128 |
|
| 2129 |
/* Reset the trie */
|
| 2130 |
lp_flush(hc->lp); |
| 2131 |
hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node)); |
| 2132 |
|
| 2133 |
WALK_LIST_DELSAFE(n, x, hc->hostentries) |
| 2134 |
{
|
| 2135 |
he = SKIP_BACK(struct hostentry, ln, n);
|
| 2136 |
if (!he->uc)
|
| 2137 |
{
|
| 2138 |
hc_delete_hostentry(hc, he); |
| 2139 |
continue;
|
| 2140 |
} |
| 2141 |
|
| 2142 |
if (rt_update_hostentry(tab, he))
|
| 2143 |
rt_schedule_nhu(he->tab); |
| 2144 |
} |
| 2145 |
|
| 2146 |
tab->hcu_scheduled = 0;
|
| 2147 |
} |
| 2148 |
|
| 2149 |
static struct hostentry * |
| 2150 |
rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep) |
| 2151 |
{
|
| 2152 |
struct hostentry *he;
|
| 2153 |
|
| 2154 |
if (!tab->hostcache)
|
| 2155 |
rt_init_hostcache(tab); |
| 2156 |
|
| 2157 |
uint k = hc_hash(a, dep); |
| 2158 |
struct hostcache *hc = tab->hostcache;
|
| 2159 |
for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next) |
| 2160 |
if (ipa_equal(he->addr, a) && (he->tab == dep))
|
| 2161 |
return he;
|
| 2162 |
|
| 2163 |
he = hc_new_hostentry(hc, a, ll, dep, k); |
| 2164 |
rt_update_hostentry(tab, he); |
| 2165 |
return he;
|
| 2166 |
} |
| 2167 |
|
| 2168 |
void
|
| 2169 |
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll) |
| 2170 |
{
|
| 2171 |
rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep)); |
| 2172 |
} |
| 2173 |
|
| 2174 |
|
| 2175 |
/*
|
| 2176 |
* CLI commands
|
| 2177 |
*/
|
| 2178 |
|
| 2179 |
static void |
| 2180 |
rt_format_via(rte *e, byte *via) |
| 2181 |
{
|
| 2182 |
rta *a = e->attrs; |
| 2183 |
|
| 2184 |
switch (a->dest)
|
| 2185 |
{
|
| 2186 |
case RTD_ROUTER: bsprintf(via, "via %I on %s", a->gw, a->iface->name); break; |
| 2187 |
case RTD_DEVICE: bsprintf(via, "dev %s", a->iface->name); break; |
| 2188 |
case RTD_BLACKHOLE: bsprintf(via, "blackhole"); break; |
| 2189 |
case RTD_UNREACHABLE: bsprintf(via, "unreachable"); break; |
| 2190 |
case RTD_PROHIBIT: bsprintf(via, "prohibited"); break; |
| 2191 |
case RTD_MULTIPATH: bsprintf(via, "multipath"); break; |
| 2192 |
default: bsprintf(via, "???"); |
| 2193 |
} |
| 2194 |
} |
| 2195 |
|
| 2196 |
static void |
| 2197 |
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa) |
| 2198 |
{
|
| 2199 |
byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8]; |
| 2200 |
byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
|
| 2201 |
rta *a = e->attrs; |
| 2202 |
int primary = (e->net->routes == e);
|
| 2203 |
int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
|
| 2204 |
void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs); |
| 2205 |
struct mpnh *nh;
|
| 2206 |
|
| 2207 |
rt_format_via(e, via); |
| 2208 |
tm_format_datetime(tm, &config->tf_route, e->lastmod); |
| 2209 |
if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
|
| 2210 |
bsprintf(from, " from %I", a->from);
|
| 2211 |
else
|
| 2212 |
from[0] = 0; |
| 2213 |
|
| 2214 |
get_route_info = a->src->proto->proto->get_route_info; |
| 2215 |
if (get_route_info || d->verbose)
|
| 2216 |
{
|
| 2217 |
/* Need to normalize the extended attributes */
|
| 2218 |
ea_list *t = tmpa; |
| 2219 |
t = ea_append(t, a->eattrs); |
| 2220 |
tmpa = alloca(ea_scan(t)); |
| 2221 |
ea_merge(t, tmpa); |
| 2222 |
ea_sort(tmpa); |
| 2223 |
} |
| 2224 |
if (get_route_info)
|
| 2225 |
get_route_info(e, info, tmpa); |
| 2226 |
else
|
| 2227 |
bsprintf(info, " (%d)", e->pref);
|
| 2228 |
cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->src->proto->name, |
| 2229 |
tm, from, primary ? (sync_error ? " !" : " *") : "", info); |
| 2230 |
for (nh = a->nexthops; nh; nh = nh->next)
|
| 2231 |
cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1); |
| 2232 |
if (d->verbose)
|
| 2233 |
rta_show(c, a, tmpa); |
| 2234 |
} |
| 2235 |
|
| 2236 |
static void |
| 2237 |
rt_show_net(struct cli *c, net *n, struct rt_show_data *d) |
| 2238 |
{
|
| 2239 |
rte *e, *ee; |
| 2240 |
byte ia[STD_ADDRESS_P_LENGTH+8];
|
| 2241 |
struct ea_list *tmpa;
|
| 2242 |
struct announce_hook *a = NULL; |
| 2243 |
int first = 1; |
| 2244 |
int pass = 0; |
| 2245 |
|
| 2246 |
bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
|
| 2247 |
|
| 2248 |
if (d->export_mode)
|
| 2249 |
{
|
| 2250 |
if (! d->export_protocol->rt_notify)
|
| 2251 |
return;
|
| 2252 |
|
| 2253 |
a = proto_find_announce_hook(d->export_protocol, d->table); |
| 2254 |
if (!a)
|
| 2255 |
return;
|
| 2256 |
} |
| 2257 |
|
| 2258 |
for (e = n->routes; e; e = e->next)
|
| 2259 |
{
|
| 2260 |
if (rte_is_filtered(e) != d->filtered)
|
| 2261 |
continue;
|
| 2262 |
|
| 2263 |
d->rt_counter++; |
| 2264 |
d->net_counter += first; |
| 2265 |
first = 0;
|
| 2266 |
|
| 2267 |
if (pass)
|
| 2268 |
continue;
|
| 2269 |
|
| 2270 |
ee = e; |
| 2271 |
rte_update_lock(); /* We use the update buffer for filtering */
|
| 2272 |
tmpa = make_tmp_attrs(e, rte_update_pool); |
| 2273 |
|
| 2274 |
if (d->export_mode)
|
| 2275 |
{
|
| 2276 |
struct proto *ep = d->export_protocol;
|
| 2277 |
int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0; |
| 2278 |
|
| 2279 |
if (ep->accept_ra_types == RA_OPTIMAL)
|
| 2280 |
pass = 1;
|
| 2281 |
|
| 2282 |
if (ic < 0) |
| 2283 |
goto skip;
|
| 2284 |
|
| 2285 |
if (d->export_mode > RSEM_PREEXPORT)
|
| 2286 |
{
|
| 2287 |
/*
|
| 2288 |
* FIXME - This shows what should be exported according to current
|
| 2289 |
* filters, but not what was really exported. 'configure soft'
|
| 2290 |
* command may change the export filter and do not update routes.
|
| 2291 |
*/
|
| 2292 |
int do_export = (ic > 0) || |
| 2293 |
(f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT); |
| 2294 |
|
| 2295 |
if (do_export != (d->export_mode == RSEM_EXPORT))
|
| 2296 |
goto skip;
|
| 2297 |
|
| 2298 |
if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED))
|
| 2299 |
pass = 1;
|
| 2300 |
} |
| 2301 |
} |
| 2302 |
|
| 2303 |
if (d->show_protocol && (d->show_protocol != e->attrs->src->proto))
|
| 2304 |
goto skip;
|
| 2305 |
|
| 2306 |
if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
|
| 2307 |
goto skip;
|
| 2308 |
|
| 2309 |
d->show_counter++; |
| 2310 |
if (d->stats < 2) |
| 2311 |
rt_show_rte(c, ia, e, d, tmpa); |
| 2312 |
ia[0] = 0; |
| 2313 |
|
| 2314 |
skip:
|
| 2315 |
if (e != ee)
|
| 2316 |
{
|
| 2317 |
rte_free(e); |
| 2318 |
e = ee; |
| 2319 |
} |
| 2320 |
rte_update_unlock(); |
| 2321 |
|
| 2322 |
if (d->primary_only)
|
| 2323 |
break;
|
| 2324 |
} |
| 2325 |
} |
| 2326 |
|
| 2327 |
static void |
| 2328 |
rt_show_cont(struct cli *c)
|
| 2329 |
{
|
| 2330 |
struct rt_show_data *d = c->rover;
|
| 2331 |
#ifdef DEBUGGING
|
| 2332 |
unsigned max = 4; |
| 2333 |
#else
|
| 2334 |
unsigned max = 64; |
| 2335 |
#endif
|
| 2336 |
struct fib *fib = &d->table->fib;
|
| 2337 |
struct fib_iterator *it = &d->fit;
|
| 2338 |
|
| 2339 |
FIB_ITERATE_START(fib, it, f) |
| 2340 |
{
|
| 2341 |
net *n = (net *) f; |
| 2342 |
if (d->running_on_config && d->running_on_config != config)
|
| 2343 |
{
|
| 2344 |
cli_printf(c, 8004, "Stopped due to reconfiguration"); |
| 2345 |
goto done;
|
| 2346 |
} |
| 2347 |
if (d->export_protocol && (d->export_protocol->export_state == ES_DOWN))
|
| 2348 |
{
|
| 2349 |
cli_printf(c, 8005, "Protocol is down"); |
| 2350 |
goto done;
|
| 2351 |
} |
| 2352 |
if (!max--)
|
| 2353 |
{
|
| 2354 |
FIB_ITERATE_PUT(it, f); |
| 2355 |
return;
|
| 2356 |
} |
| 2357 |
rt_show_net(c, n, d); |
| 2358 |
} |
| 2359 |
FIB_ITERATE_END(f); |
| 2360 |
if (d->stats)
|
| 2361 |
cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter); |
| 2362 |
else
|
| 2363 |
cli_printf(c, 0, ""); |
| 2364 |
done:
|
| 2365 |
c->cont = c->cleanup = NULL;
|
| 2366 |
} |
| 2367 |
|
| 2368 |
static void |
| 2369 |
rt_show_cleanup(struct cli *c)
|
| 2370 |
{
|
| 2371 |
struct rt_show_data *d = c->rover;
|
| 2372 |
|
| 2373 |
/* Unlink the iterator */
|
| 2374 |
fit_get(&d->table->fib, &d->fit); |
| 2375 |
} |
| 2376 |
|
| 2377 |
void
|
| 2378 |
rt_show(struct rt_show_data *d)
|
| 2379 |
{
|
| 2380 |
net *n; |
| 2381 |
|
| 2382 |
/* Default is either a master table or a table related to a respective protocol */
|
| 2383 |
if (!d->table && d->export_protocol) d->table = d->export_protocol->table;
|
| 2384 |
if (!d->table && d->show_protocol) d->table = d->show_protocol->table;
|
| 2385 |
if (!d->table) d->table = config->master_rtc->table;
|
| 2386 |
|
| 2387 |
/* Filtered routes are neither exported nor have sensible ordering */
|
| 2388 |
if (d->filtered && (d->export_mode || d->primary_only))
|
| 2389 |
cli_msg(0, ""); |
| 2390 |
|
| 2391 |
if (d->pxlen == 256) |
| 2392 |
{
|
| 2393 |
FIB_ITERATE_INIT(&d->fit, &d->table->fib); |
| 2394 |
this_cli->cont = rt_show_cont; |
| 2395 |
this_cli->cleanup = rt_show_cleanup; |
| 2396 |
this_cli->rover = d; |
| 2397 |
} |
| 2398 |
else
|
| 2399 |
{
|
| 2400 |
if (d->show_for)
|
| 2401 |
n = net_route(d->table, d->prefix, d->pxlen); |
| 2402 |
else
|
| 2403 |
n = net_find(d->table, d->prefix, d->pxlen); |
| 2404 |
|
| 2405 |
if (n)
|
| 2406 |
rt_show_net(this_cli, n, d); |
| 2407 |
|
| 2408 |
if (d->rt_counter)
|
| 2409 |
cli_msg(0, ""); |
| 2410 |
else
|
| 2411 |
cli_msg(8001, "Network not in table"); |
| 2412 |
} |
| 2413 |
} |
| 2414 |
|
| 2415 |
/*
|
| 2416 |
* Documentation for functions declared inline in route.h
|
| 2417 |
*/
|
| 2418 |
#if 0
|
| 2419 |
|
| 2420 |
/**
|
| 2421 |
* net_find - find a network entry
|
| 2422 |
* @tab: a routing table
|
| 2423 |
* @addr: address of the network
|
| 2424 |
* @len: length of the network prefix
|
| 2425 |
*
|
| 2426 |
* net_find() looks up the given network in routing table @tab and
|
| 2427 |
* returns a pointer to its &net entry or %NULL if no such network
|
| 2428 |
* exists.
|
| 2429 |
*/
|
| 2430 |
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
|
| 2431 |
{ DUMMY; }
|
| 2432 |
|
| 2433 |
/**
|
| 2434 |
* net_get - obtain a network entry
|
| 2435 |
* @tab: a routing table
|
| 2436 |
* @addr: address of the network
|
| 2437 |
* @len: length of the network prefix
|
| 2438 |
*
|
| 2439 |
* net_get() looks up the given network in routing table @tab and
|
| 2440 |
* returns a pointer to its &net entry. If no such entry exists, it's
|
| 2441 |
* created.
|
| 2442 |
*/
|
| 2443 |
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
|
| 2444 |
{ DUMMY; }
|
| 2445 |
|
| 2446 |
/**
|
| 2447 |
* rte_cow - copy a route for writing
|
| 2448 |
* @r: a route entry to be copied
|
| 2449 |
*
|
| 2450 |
* rte_cow() takes a &rte and prepares it for modification. The exact action
|
| 2451 |
* taken depends on the flags of the &rte -- if it's a temporary entry, it's
|
| 2452 |
* just returned unchanged, else a new temporary entry with the same contents
|
| 2453 |
* is created.
|
| 2454 |
*
|
| 2455 |
* The primary use of this function is inside the filter machinery -- when
|
| 2456 |
* a filter wants to modify &rte contents (to change the preference or to
|
| 2457 |
* attach another set of attributes), it must ensure that the &rte is not
|
| 2458 |
* shared with anyone else (and especially that it isn't stored in any routing
|
| 2459 |
* table).
|
| 2460 |
*
|
| 2461 |
* Result: a pointer to the new writable &rte.
|
| 2462 |
*/
|
| 2463 |
static inline rte * rte_cow(rte *r)
|
| 2464 |
{ DUMMY; }
|
| 2465 |
|
| 2466 |
#endif
|