Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 0e6eef62

History | View | Annotate | Download (27.9 KB)

1 62aa008a Martin Mares
/*
2 58740ed4 Martin Mares
 *        BIRD -- Routing Tables
3 62aa008a Martin Mares
 *
4 50fe90ed Martin Mares
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5 62aa008a Martin Mares
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8
9 58740ed4 Martin Mares
/**
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 725270cb Martin Mares
 * There are multiple routing tables (a primary one together with any
17 58740ed4 Martin Mares
 * number of secondary ones if requested by the configuration). Each table
18
 * is basically a FIB containing entries describing the individual
19 58f7d004 Martin Mares
 * destination networks. For each network (represented by structure &net),
20 725270cb Martin Mares
 * 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 58740ed4 Martin Mares
 * 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 6b9fa320 Martin Mares
#undef LOCAL_DEBUG
32 1a54b1c6 Martin Mares
33 62aa008a Martin Mares
#include "nest/bird.h"
34
#include "nest/route.h"
35 2326b001 Martin Mares
#include "nest/protocol.h"
36 730f2e2c Martin Mares
#include "nest/cli.h"
37
#include "nest/iface.h"
38 2326b001 Martin Mares
#include "lib/resource.h"
39 5996da6a Martin Mares
#include "lib/event.h"
40 730f2e2c Martin Mares
#include "lib/string.h"
41 0e02abfd Martin Mares
#include "conf/conf.h"
42 529c4149 Martin Mares
#include "filter/filter.h"
43 221135d6 Martin Mares
#include "lib/string.h"
44 0e6eef62 Ondrej Filip
#include "alloca.h"
45 7d875e09 Martin Mares
46 2326b001 Martin Mares
static slab *rte_slab;
47 e2dc2f30 Martin Mares
static linpool *rte_update_pool;
48 2326b001 Martin Mares
49 5996da6a Martin Mares
static pool *rt_table_pool;
50 0e02abfd Martin Mares
static list routing_tables;
51 5996da6a Martin Mares
52 cfd46ee4 Martin Mares
static void rt_format_via(rte *e, byte *via);
53
54 5996da6a Martin Mares
static void
55 2326b001 Martin Mares
rte_init(struct fib_node *N)
56
{
57
  net *n = (net *) N;
58
59 4c45595e Martin Mares
  N->flags = 0;
60 2326b001 Martin Mares
  n->routes = NULL;
61
}
62
63 58740ed4 Martin Mares
/**
64
 * rte_find - find a route
65
 * @net: network node
66
 * @p: protocol
67
 *
68
 * The rte_find() function returns a route for destination @net
69
 * which belongs has been defined by protocol @p.
70
 */
71 2326b001 Martin Mares
rte *
72
rte_find(net *net, struct proto *p)
73
{
74
  rte *e = net->routes;
75
76
  while (e && e->attrs->proto != p)
77
    e = e->next;
78
  return e;
79
}
80
81 58740ed4 Martin Mares
/**
82
 * rte_get_temp - get a temporary &rte
83 3ce8c610 Martin Mares
 * @a: attributes to assign to the new route (a &rta; in case it's
84 2e9b2421 Martin Mares
 * un-cached, rte_update() will create a cached copy automatically)
85 58740ed4 Martin Mares
 *
86
 * Create a temporary &rte and bind it with the attributes @a.
87
 * Also set route preference to the default preference set for
88
 * the protocol.
89
 */
90 2326b001 Martin Mares
rte *
91
rte_get_temp(rta *a)
92
{
93
  rte *e = sl_alloc(rte_slab);
94
95
  e->attrs = a;
96 0cdbd397 Martin Mares
  e->flags = 0;
97 2326b001 Martin Mares
  e->pref = a->proto->preference;
98
  return e;
99
}
100
101 e2dc2f30 Martin Mares
rte *
102
rte_do_cow(rte *r)
103
{
104
  rte *e = sl_alloc(rte_slab);
105
106
  memcpy(e, r, sizeof(rte));
107
  e->attrs = rta_clone(r->attrs);
108
  e->flags = 0;
109
  return e;
110
}
111
112 2326b001 Martin Mares
static int                                /* Actually better or at least as good as */
113
rte_better(rte *new, rte *old)
114
{
115 d9f330c5 Martin Mares
  int (*better)(rte *, rte *);
116
117 2326b001 Martin Mares
  if (!old)
118
    return 1;
119
  if (new->pref > old->pref)
120
    return 1;
121
  if (new->pref < old->pref)
122
    return 0;
123 739ebd8e Martin Mares
  if (new->attrs->proto->proto != old->attrs->proto->proto)
124 4c1b4e1a Martin Mares
    {
125
      /*
126
       *  If the user has configured protocol preferences, so that two different protocols
127
       *  have the same preference, try to break the tie by comparing addresses. Not too
128
       *  useful, but keeps the ordering of routes unambiguous.
129
       */
130
      return new->attrs->proto->proto > old->attrs->proto->proto;
131
    }
132 d9f330c5 Martin Mares
  if (better = new->attrs->proto->rte_better)
133
    return better(new, old);
134
  return 0;
135 2326b001 Martin Mares
}
136
137 cfd46ee4 Martin Mares
static void
138
rte_trace(struct proto *p, rte *e, int dir, char *msg)
139
{
140
  byte via[STD_ADDRESS_P_LENGTH+32];
141
142
  rt_format_via(e, via);
143
  log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
144
}
145
146
static inline void
147
rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg)
148
{
149
  if (p->debug & flag)
150 b0a47440 Martin Mares
    rte_trace(p, e, '>', msg);
151 cfd46ee4 Martin Mares
}
152
153
static inline void
154
rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg)
155
{
156
  if (p->debug & flag)
157 b0a47440 Martin Mares
    rte_trace(p, e, '<', msg);
158 cfd46ee4 Martin Mares
}
159
160 529c4149 Martin Mares
static inline void
161 0da472d7 Martin Mares
do_rte_announce(struct announce_hook *a, net *net, rte *new, rte *old, ea_list *tmpa, int class)
162 529c4149 Martin Mares
{
163 0e02abfd Martin Mares
  struct proto *p = a->proto;
164 e2dc2f30 Martin Mares
  rte *new0 = new;
165
  rte *old0 = old;
166 08f0290a Martin Mares
  int ok;
167 7de45ba4 Martin Mares
168 e2dc2f30 Martin Mares
  if (new)
169 529c4149 Martin Mares
    {
170 13b75bac Martin Mares
      char *drop_reason = NULL;
171 cfd46ee4 Martin Mares
      if ((class & IADDR_SCOPE_MASK) < p->min_scope)
172 13b75bac Martin Mares
        drop_reason = "out of scope";
173 cfd46ee4 Martin Mares
      else if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
174 13b75bac Martin Mares
        drop_reason = "rejected by protocol";
175 cfd46ee4 Martin Mares
      else if (ok)
176
        rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
177
      else if (p->out_filter == FILTER_REJECT ||
178 3a6337ec Martin Mares
               p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
179 13b75bac Martin Mares
        drop_reason = "filtered out";
180
      if (drop_reason)
181 cfd46ee4 Martin Mares
        {
182 13b75bac Martin Mares
          rte_trace_out(D_FILTERS, p, new, drop_reason);
183 2adab6ae Martin Mares
          if (new != new0)
184
            rte_free(new);
185 cfd46ee4 Martin Mares
          new = NULL;
186
        }
187 529c4149 Martin Mares
    }
188 e2dc2f30 Martin Mares
  if (old && p->out_filter)
189
    {
190
      if (p->out_filter == FILTER_REJECT)
191
        old = NULL;
192
      else
193
        {
194
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
195 08f0290a Martin Mares
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
196
          if (ok < 0 || (!ok && f_run(p->out_filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
197 13b75bac Martin Mares
            {
198
              if (old != old0)
199
                rte_free(old);
200
              old = NULL;
201
            }
202 e2dc2f30 Martin Mares
        }
203
    }
204 cfd46ee4 Martin Mares
  if (p->debug & D_ROUTES)
205
    {
206
      if (new && old)
207
        rte_trace_out(D_ROUTES, p, new, "replaced");
208
      else if (new)
209
        rte_trace_out(D_ROUTES, p, new, "added");
210 349e21bb Martin Mares
      else if (old)
211 cfd46ee4 Martin Mares
        rte_trace_out(D_ROUTES, p, old, "removed");
212
    }
213 08f0290a Martin Mares
  if (!new && !old)
214
    return;
215
  if (!new)
216
    p->rt_notify(p, net, NULL, old, NULL);
217
  else if (tmpa)
218
    {
219 2f711231 Martin Mares
      ea_list *t = tmpa;
220
      while (t->next)
221
        t = t->next;
222
      t->next = new->attrs->eattrs;
223 08f0290a Martin Mares
      p->rt_notify(p, net, new, old, tmpa);
224 2f711231 Martin Mares
      t->next = NULL;
225 08f0290a Martin Mares
    }
226
  else
227
    p->rt_notify(p, net, new, old, new->attrs->eattrs);
228 e2dc2f30 Martin Mares
  if (new && new != new0)        /* Discard temporary rte's */
229
    rte_free(new);
230
  if (old && old != old0)
231
    rte_free(old);
232 529c4149 Martin Mares
}
233
234 9a8f20fc Martin Mares
/**
235
 * rte_announce - announce a routing table change
236
 * @tab: table the route has been added to
237
 * @net: network in question
238
 * @new: the new route to be announced
239
 * @old: previous optimal route for the same network
240
 * @tmpa: a list of temporary attributes belonging to the new route
241
 *
242
 * This function gets a routing table update and announces it
243
 * to all protocols connected to the same table by their announcement hooks.
244
 *
245
 * For each such protocol, we first call its import_control() hook which
246
 * performs basic checks on the route (each protocol has a right to veto
247
 * or force accept of the route before any filter is asked) and adds default
248
 * values of attributes specific to the new protocol (metrics, tags etc.).
249
 * Then it consults the protocol's export filter and if it accepts the
250
 * route, the rt_notify() hook of the protocol gets called.
251
 */
252 e2dc2f30 Martin Mares
static void
253 0e02abfd Martin Mares
rte_announce(rtable *tab, net *net, rte *new, rte *old, ea_list *tmpa)
254 2326b001 Martin Mares
{
255 0e02abfd Martin Mares
  struct announce_hook *a;
256 0da472d7 Martin Mares
  int class = ipa_classify(net->n.prefix);
257 2326b001 Martin Mares
258 0e02abfd Martin Mares
  WALK_LIST(a, tab->hooks)
259 0a2e9d9f Martin Mares
    {
260 8c943173 Martin Mares
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
261 0da472d7 Martin Mares
      do_rte_announce(a, net, new, old, tmpa, class);
262 0a2e9d9f Martin Mares
    }
263 2326b001 Martin Mares
}
264
265 421838ff Martin Mares
static inline int
266
rte_validate(rte *e)
267
{
268
  int c;
269
  net *n = e->net;
270
271 cfd46ee4 Martin Mares
  if (ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))))
272
    {
273
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
274
          n->n.prefix, n->n.pxlen, e->attrs->proto->name);
275
      return 0;
276
    }
277 421838ff Martin Mares
  if (n->n.pxlen)
278
    {
279
      c = ipa_classify(n->n.prefix);
280
      if (c < 0 || !(c & IADDR_HOST))
281
        {
282 85a291ff Martin Mares
          if (!ipa_nonzero(n->n.prefix))
283
            {
284
              /* Various default routes */
285
#ifdef IPV6
286
              if (n->n.pxlen == 96)
287
#else
288
              if (n->n.pxlen <= 1)
289
#endif
290
                return 1;
291
            }
292
          log(L_WARN "Ignoring bogus route %I/%d received via %s",
293
              n->n.prefix, n->n.pxlen, e->attrs->proto->name);
294 421838ff Martin Mares
          return 0;
295
        }
296 0da472d7 Martin Mares
      if ((c & IADDR_SCOPE_MASK) < e->attrs->proto->min_scope)
297 421838ff Martin Mares
        {
298 0da472d7 Martin Mares
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
299
              ip_scope_text(c & IADDR_SCOPE_MASK),
300
              n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
301
          return 0;
302 421838ff Martin Mares
        }
303
    }
304
  return 1;
305
}
306
307 58740ed4 Martin Mares
/**
308
 * rte_free - delete a &rte
309
 * @e: &rte to be deleted
310
 *
311
 * rte_free() deletes the given &rte from the routing table it's linked to.
312
 */
313 04925e90 Martin Mares
void
314 2326b001 Martin Mares
rte_free(rte *e)
315
{
316 04925e90 Martin Mares
  if (e->attrs->aflags & RTAF_CACHED)
317
    rta_free(e->attrs);
318
  sl_free(rte_slab, e);
319
}
320
321
static inline void
322
rte_free_quick(rte *e)
323
{
324 2326b001 Martin Mares
  rta_free(e->attrs);
325
  sl_free(rte_slab, e);
326
}
327
328 67be5b23 Martin Mares
static int
329
rte_same(rte *x, rte *y)
330
{
331
  return
332
    x->attrs == y->attrs &&
333
    x->flags == y->flags &&
334
    x->pflags == y->pflags &&
335
    x->pref == y->pref &&
336
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
337
}
338
339 e2dc2f30 Martin Mares
static void
340 0e02abfd Martin Mares
rte_recalculate(rtable *table, net *net, struct proto *p, rte *new, ea_list *tmpa)
341 2326b001 Martin Mares
{
342
  rte *old_best = net->routes;
343
  rte *old = NULL;
344
  rte **k, *r, *s;
345
346
  k = &net->routes;                        /* Find and remove original route from the same protocol */
347
  while (old = *k)
348
    {
349
      if (old->attrs->proto == p)
350
        {
351 0b761098 Martin Mares
          if (new && rte_same(old, new))
352 67be5b23 Martin Mares
            {
353
              /* No changes, ignore the new route */
354
              rte_trace_in(D_ROUTES, p, new, "ignored");
355
              rte_free_quick(new);
356
              old->lastmod = now;
357
              return;
358
            }
359 2326b001 Martin Mares
          *k = old->next;
360
          break;
361
        }
362
      k = &old->next;
363
    }
364
365 0cdbd397 Martin Mares
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
366 2326b001 Martin Mares
    {
367 85810613 Martin Mares
      rte_trace_in(D_ROUTES, p, new, "added [best]");
368 0e02abfd Martin Mares
      rte_announce(table, net, new, old_best, tmpa);
369 2326b001 Martin Mares
      new->next = net->routes;
370
      net->routes = new;
371
    }
372
  else
373
    {
374
      if (old == old_best)                /* It has _replaced_ the old optimal route */
375
        {
376
          r = new;                        /* Find new optimal route and announce it */
377
          for(s=net->routes; s; s=s->next)
378
            if (rte_better(s, r))
379
              r = s;
380 0e02abfd Martin Mares
          rte_announce(table, net, r, old_best, tmpa);
381 2326b001 Martin Mares
          if (r)                        /* Re-link the new optimal route */
382
            {
383
              k = &net->routes;
384
              while (s = *k)
385
                {
386
                  if (s == r)
387
                    {
388
                      *k = r->next;
389
                      break;
390
                    }
391 dafd580e Martin Mares
                  k = &s->next;
392 2326b001 Martin Mares
                }
393
              r->next = net->routes;
394
              net->routes = r;
395
            }
396 2eca3b3a Martin Mares
          else if (table->gc_counter++ >= table->config->gc_max_ops &&
397
                   table->gc_time + table->config->gc_min_time <= now)
398
            ev_schedule(table->gc_event);
399 2326b001 Martin Mares
        }
400
      if (new)                                /* Link in the new non-optimal route */
401
        {
402
          new->next = old_best->next;
403
          old_best->next = new;
404 cfd46ee4 Martin Mares
          rte_trace_in(D_ROUTES, p, new, "added");
405
        }
406
      else if (old && (p->debug & D_ROUTES))
407
        {
408
          if (old != old_best)
409
            rte_trace_in(D_ROUTES, p, old, "removed");
410
          else if (net->routes)
411
            rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
412
          else
413
            rte_trace_in(D_ROUTES, p, old, "removed [sole]");
414 2326b001 Martin Mares
        }
415
    }
416
  if (old)
417 5b22683d Martin Mares
    {
418
      if (p->rte_remove)
419
        p->rte_remove(net, old);
420 04925e90 Martin Mares
      rte_free_quick(old);
421 5b22683d Martin Mares
    }
422 8ca8683c Martin Mares
  if (new)
423
    {
424
      new->lastmod = now;
425
      if (p->rte_insert)
426
        p->rte_insert(net, new);
427
    }
428 5b22683d Martin Mares
}
429
430 e2dc2f30 Martin Mares
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
431
432
static inline void
433
rte_update_lock(void)
434
{
435
  rte_update_nest_cnt++;
436
}
437
438
static inline void
439
rte_update_unlock(void)
440
{
441
  if (!--rte_update_nest_cnt)
442
    lp_flush(rte_update_pool);
443
}
444
445 58740ed4 Martin Mares
/**
446
 * rte_update - enter a new update to a routing table
447
 * @table: table to be updated
448
 * @net: network node
449
 * @p: protocol submitting the update
450
 * @new: a &rte representing the new route or %NULL for route removal.
451
 *
452
 * This function is called by the routing protocols whenever they discover
453
 * a new route or wish to update/remove an existing route. The right announcement
454 2e9b2421 Martin Mares
 * sequence is to build route attributes first (either un-cached with @aflags set
455 58740ed4 Martin Mares
 * to zero or a cached one using rta_lookup(); in this case please note that
456
 * you need to increase the use count of the attributes yourself by calling
457
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
458
 * the appropriate data and finally submit the new &rte by calling rte_update().
459
 *
460 9a8f20fc Martin Mares
 * When rte_update() gets any route, it automatically validates it (checks,
461
 * whether the network and next hop address are valid IP addresses and also
462
 * whether a normal routing protocol doesn't try to smuggle a host or link
463
 * scope route to the table), converts all protocol dependent attributes stored
464
 * in the &rte to temporary extended attributes, consults import filters of the
465
 * protocol to see if the route should be accepted and/or its attributes modified,
466
 * stores the temporary attributes back to the &rte.
467
 *
468
 * Now, having a "public" version of the route, we
469
 * automatically find any old route defined by the protocol @p
470 58740ed4 Martin Mares
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
471
 * recalculate the optimal route for this destination and finally broadcast
472 9a8f20fc Martin Mares
 * the change (if any) to all routing protocols by calling rte_announce().
473 3ce8c610 Martin Mares
 *
474
 * All memory used for attribute lists and other temporary allocations is taken
475
 * from a special linear pool @rte_update_pool and freed when rte_update()
476
 * finishes.
477 58740ed4 Martin Mares
 */
478 e2dc2f30 Martin Mares
void
479 0e02abfd Martin Mares
rte_update(rtable *table, net *net, struct proto *p, rte *new)
480 e2dc2f30 Martin Mares
{
481
  ea_list *tmpa = NULL;
482
483
  rte_update_lock();
484
  if (new)
485
    {
486 cfd46ee4 Martin Mares
      if (!rte_validate(new))
487
        {
488
          rte_trace_in(D_FILTERS, p, new, "invalid");
489
          goto drop;
490
        }
491
      if (p->in_filter == FILTER_REJECT)
492
        {
493
          rte_trace_in(D_FILTERS, p, new, "filtered out");
494
          goto drop;
495
        }
496 e2dc2f30 Martin Mares
      if (p->make_tmp_attrs)
497
        tmpa = p->make_tmp_attrs(new, rte_update_pool);
498
      if (p->in_filter)
499
        {
500 ccdc3397 Martin Mares
          ea_list *old_tmpa = tmpa;
501 0a06a9b8 Pavel Machek
          int fr = f_run(p->in_filter, &new, &tmpa, rte_update_pool, 0);
502 ccdc3397 Martin Mares
          if (fr > F_ACCEPT)
503 cfd46ee4 Martin Mares
            {
504
              rte_trace_in(D_FILTERS, p, new, "filtered out");
505
              goto drop;
506
            }
507 ccdc3397 Martin Mares
          if (tmpa != old_tmpa && p->store_tmp_attrs)
508 e2dc2f30 Martin Mares
            p->store_tmp_attrs(new, tmpa);
509
        }
510
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
511
        new->attrs = rta_lookup(new->attrs);
512
      new->flags |= REF_COW;
513
    }
514 0e02abfd Martin Mares
  rte_recalculate(table, net, p, new, tmpa);
515 e2dc2f30 Martin Mares
  rte_update_unlock();
516
  return;
517
518
drop:
519
  rte_free(new);
520
  rte_update_unlock();
521
}
522
523 5b22683d Martin Mares
void
524 0e02abfd Martin Mares
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
525 5b22683d Martin Mares
{
526 cfd46ee4 Martin Mares
  net *n = old->net;
527
  struct proto *p = old->attrs->proto;
528
529 e2dc2f30 Martin Mares
  rte_update_lock();
530 cfd46ee4 Martin Mares
  rte_recalculate(t, n, p, NULL, NULL);
531 e2dc2f30 Martin Mares
  rte_update_unlock();
532 2326b001 Martin Mares
}
533
534 58740ed4 Martin Mares
/**
535
 * rte_dump - dump a route
536
 * @e: &rte to be dumped
537
 *
538
 * This functions dumps contents of a &rte to debug output.
539
 */
540 2326b001 Martin Mares
void
541 a0762910 Martin Mares
rte_dump(rte *e)
542 2326b001 Martin Mares
{
543 a0762910 Martin Mares
  net *n = e->net;
544 0cdbd397 Martin Mares
  if (n)
545 e43ae633 Martin Mares
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
546 a0762910 Martin Mares
  else
547
    debug("??? ");
548 c10421d3 Martin Mares
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
549 0cdbd397 Martin Mares
  rta_dump(e->attrs);
550 c10421d3 Martin Mares
  if (e->attrs->proto->proto->dump_attrs)
551
    e->attrs->proto->proto->dump_attrs(e);
552 0cdbd397 Martin Mares
  debug("\n");
553 2326b001 Martin Mares
}
554 62aa008a Martin Mares
555 58740ed4 Martin Mares
/**
556
 * rt_dump - dump a routing table
557
 * @t: routing table to be dumped
558
 *
559
 * This function dumps contents of a given routing table to debug output.
560
 */
561 2326b001 Martin Mares
void
562
rt_dump(rtable *t)
563
{
564 0cdbd397 Martin Mares
  rte *e;
565
  net *n;
566 0e02abfd Martin Mares
  struct announce_hook *a;
567 0cdbd397 Martin Mares
568
  debug("Dump of routing table <%s>\n", t->name);
569 e440395d Martin Mares
#ifdef DEBUGGING
570 08e2d625 Martin Mares
  fib_check(&t->fib);
571 e440395d Martin Mares
#endif
572 08e2d625 Martin Mares
  FIB_WALK(&t->fib, fn)
573
    {
574
      n = (net *) fn;
575
      for(e=n->routes; e; e=e->next)
576
        rte_dump(e);
577 0cdbd397 Martin Mares
    }
578 08e2d625 Martin Mares
  FIB_WALK_END;
579 0e02abfd Martin Mares
  WALK_LIST(a, t->hooks)
580
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
581 0cdbd397 Martin Mares
  debug("\n");
582 2326b001 Martin Mares
}
583 62aa008a Martin Mares
584 58740ed4 Martin Mares
/**
585
 * rt_dump_all - dump all routing tables
586
 *
587
 * This function dumps contents of all routing tables to debug output.
588
 */
589 2326b001 Martin Mares
void
590 6d45cf21 Martin Mares
rt_dump_all(void)
591
{
592 0e02abfd Martin Mares
  rtable *t;
593
594
  WALK_LIST(t, routing_tables)
595
    rt_dump(t);
596 6d45cf21 Martin Mares
}
597
598 8f6accb5 Martin Mares
static void
599 b9626ec6 Martin Mares
rt_gc(void *tab)
600 5996da6a Martin Mares
{
601 b9626ec6 Martin Mares
  rtable *t = tab;
602 0e02abfd Martin Mares
603 b9626ec6 Martin Mares
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
604
      t->name, (int)(now - t->gc_time), t->gc_counter);
605
  rt_prune(t);
606 5996da6a Martin Mares
}
607
608 6d45cf21 Martin Mares
void
609 b9626ec6 Martin Mares
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
610
{
611
  bzero(t, sizeof(*t));
612
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
613
  t->name = name;
614
  t->config = cf;
615
  init_list(&t->hooks);
616
  if (cf)
617
    {
618
      t->gc_event = ev_new(p);
619
      t->gc_event->hook = rt_gc;
620
      t->gc_event->data = t;
621 2eca3b3a Martin Mares
      t->gc_time = now;
622 b9626ec6 Martin Mares
    }
623
}
624
625 58740ed4 Martin Mares
/**
626
 * rt_init - initialize routing tables
627
 *
628
 * This function is called during BIRD startup. It initializes the
629
 * routing table module.
630
 */
631 b9626ec6 Martin Mares
void
632 2326b001 Martin Mares
rt_init(void)
633
{
634
  rta_init();
635 5996da6a Martin Mares
  rt_table_pool = rp_new(&root_pool, "Routing tables");
636 e2dc2f30 Martin Mares
  rte_update_pool = lp_new(rt_table_pool, 4080);
637 5996da6a Martin Mares
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
638 0e02abfd Martin Mares
  init_list(&routing_tables);
639 2326b001 Martin Mares
}
640 1a54b1c6 Martin Mares
641 58740ed4 Martin Mares
/**
642
 * rt_prune - prune a routing table
643
 * @tab: routing table to be pruned
644
 *
645
 * This function is called whenever a protocol shuts down. It scans
646
 * the routing table and removes all routes belonging to inactive
647
 * protocols and also stale network entries.
648
 */
649 1a54b1c6 Martin Mares
void
650
rt_prune(rtable *tab)
651
{
652
  struct fib_iterator fit;
653 5996da6a Martin Mares
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
654 1a54b1c6 Martin Mares
655
  DBG("Pruning route table %s\n", tab->name);
656 0521e4f6 Martin Mares
#ifdef DEBUGGING
657
  fib_check(&tab->fib);
658
#endif
659 08e2d625 Martin Mares
  FIB_ITERATE_INIT(&fit, &tab->fib);
660
again:
661
  FIB_ITERATE_START(&tab->fib, &fit, f)
662 1a54b1c6 Martin Mares
    {
663 08e2d625 Martin Mares
      net *n = (net *) f;
664
      rte *e;
665
      ncnt++;
666
    rescan:
667
      for (e=n->routes; e; e=e->next, rcnt++)
668 0521e4f6 Martin Mares
        if (e->attrs->proto->core_state != FS_HAPPY &&
669
            e->attrs->proto->core_state != FS_FEEDING)
670 08e2d625 Martin Mares
          {
671 0e02abfd Martin Mares
            rte_discard(tab, e);
672 08e2d625 Martin Mares
            rdel++;
673
            goto rescan;
674
          }
675
      if (!n->routes)                /* Orphaned FIB entry? */
676 1a54b1c6 Martin Mares
        {
677 08e2d625 Martin Mares
          FIB_ITERATE_PUT(&fit, f);
678
          fib_delete(&tab->fib, f);
679
          ndel++;
680
          goto again;
681 1a54b1c6 Martin Mares
        }
682
    }
683 08e2d625 Martin Mares
  FIB_ITERATE_END(f);
684 2eca3b3a Martin Mares
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
685 0521e4f6 Martin Mares
#ifdef DEBUGGING
686
  fib_check(&tab->fib);
687
#endif
688 b9626ec6 Martin Mares
  tab->gc_counter = 0;
689
  tab->gc_time = now;
690 1a54b1c6 Martin Mares
}
691 0e02abfd Martin Mares
692 58740ed4 Martin Mares
/**
693
 * rt_prune_all - prune all routing tables
694
 *
695
 * This function calls rt_prune() for all known routing tables.
696
 */
697 0e02abfd Martin Mares
void
698
rt_prune_all(void)
699
{
700
  rtable *t;
701
702
  WALK_LIST(t, routing_tables)
703
    rt_prune(t);
704
}
705
706 b9626ec6 Martin Mares
struct rtable_config *
707
rt_new_table(struct symbol *s)
708
{
709
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
710
711
  cf_define_symbol(s, SYM_TABLE, c);
712
  c->name = s->name;
713
  add_tail(&new_config->tables, &c->n);
714 2eca3b3a Martin Mares
  c->gc_max_ops = 1000;
715 b9626ec6 Martin Mares
  c->gc_min_time = 5;
716
  return c;
717
}
718
719 0e02abfd Martin Mares
void
720
rt_preconfig(struct config *c)
721
{
722
  struct symbol *s = cf_find_symbol("master");
723
724
  init_list(&c->tables);
725 b9626ec6 Martin Mares
  c->master_rtc = rt_new_table(s);
726 0e02abfd Martin Mares
}
727
728 58740ed4 Martin Mares
/**
729
 * rt_lock_table - lock a routing table
730
 * @r: routing table to be locked
731
 *
732
 * Lock a routing table, because it's in use by a protocol,
733
 * preventing it from being freed when it gets undefined in a new
734
 * configuration.
735
 */
736 0e02abfd Martin Mares
void
737 50fe90ed Martin Mares
rt_lock_table(rtable *r)
738 0e02abfd Martin Mares
{
739 50fe90ed Martin Mares
  r->use_count++;
740
}
741
742 58740ed4 Martin Mares
/**
743
 * rt_unlock_table - unlock a routing table
744
 * @r: routing table to be unlocked
745
 *
746
 * Unlock a routing table formerly locked by rt_lock_table(),
747
 * that is decrease its use count and delete it if it's scheduled
748
 * for deletion by configuration changes.
749
 */
750 50fe90ed Martin Mares
void
751
rt_unlock_table(rtable *r)
752
{
753
  if (!--r->use_count && r->deleted)
754
    {
755
      struct config *conf = r->deleted;
756
      DBG("Deleting routing table %s\n", r->name);
757
      rem_node(&r->n);
758
      fib_free(&r->fib);
759
      mb_free(r);
760
      config_del_obstacle(conf);
761
    }
762
}
763
764 58740ed4 Martin Mares
/**
765
 * rt_commit - commit new routing table configuration
766
 * @new: new configuration
767
 * @old: original configuration or %NULL if it's boot time config
768
 *
769
 * Scan differences between @old and @new configuration and modify
770
 * the routing tables according to these changes. If @new defines a
771
 * previously unknown table, create it, if it omits a table existing
772
 * in @old, schedule it for deletion (it gets deleted when all protocols
773
 * disconnect from it by calling rt_unlock_table()), if it exists
774
 * in both configurations, leave it unchanged.
775
 */
776 50fe90ed Martin Mares
void
777
rt_commit(struct config *new, struct config *old)
778
{
779
  struct rtable_config *o, *r;
780 0e02abfd Martin Mares
781 50fe90ed Martin Mares
  DBG("rt_commit:\n");
782
  if (old)
783 0e02abfd Martin Mares
    {
784 50fe90ed Martin Mares
      WALK_LIST(o, old->tables)
785
        {
786
          rtable *ot = o->table;
787
          if (!ot->deleted)
788
            {
789
              struct symbol *sym = cf_find_symbol(o->name);
790 bf8558bc Martin Mares
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
791 50fe90ed Martin Mares
                {
792
                  DBG("\t%s: same\n", o->name);
793
                  r = sym->def;
794
                  r->table = ot;
795
                  ot->name = r->name;
796 b9626ec6 Martin Mares
                  ot->config = r;
797 50fe90ed Martin Mares
                }
798
              else
799
                {
800 bf8558bc Martin Mares
                  DBG("\t%s: deleted\n", o->name);
801 50fe90ed Martin Mares
                  ot->deleted = old;
802
                  config_add_obstacle(old);
803
                  rt_lock_table(ot);
804
                  rt_unlock_table(ot);
805
                }
806
            }
807
        }
808 0e02abfd Martin Mares
    }
809 50fe90ed Martin Mares
810
  WALK_LIST(r, new->tables)
811
    if (!r->table)
812
      {
813
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
814
        DBG("\t%s: created\n", r->name);
815 b9626ec6 Martin Mares
        rt_setup(rt_table_pool, t, r->name, r);
816 50fe90ed Martin Mares
        add_tail(&routing_tables, &t->n);
817
        r->table = t;
818
      }
819
  DBG("\tdone\n");
820 0e02abfd Martin Mares
}
821 730f2e2c Martin Mares
822 58740ed4 Martin Mares
/**
823
 * rt_feed_baby - advertise routes to a new protocol
824
 * @p: protocol to be fed
825
 *
826
 * This function performs one pass of advertisement of routes to a newly
827
 * initialized protocol. It's called by the protocol code as long as it
828
 * has something to do. (We avoid transferring all the routes in single
829
 * pass in order not to monopolize CPU time.)
830
 */
831 ac5d8012 Martin Mares
int
832
rt_feed_baby(struct proto *p)
833
{
834
  struct announce_hook *h;
835
  struct fib_iterator *fit;
836 76dfda9e Martin Mares
  int max_feed = 256;
837 ac5d8012 Martin Mares
838
  if (!p->feed_ahook)                        /* Need to initialize first */
839
    {
840
      if (!p->ahooks)
841
        return 1;
842
      DBG("Announcing routes to new protocol %s\n", p->name);
843
      p->feed_ahook = p->ahooks;
844
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
845
      goto next_hook;
846
    }
847
  fit = p->feed_iterator;
848
849
again:
850
  h = p->feed_ahook;
851
  FIB_ITERATE_START(&h->table->fib, fit, fn)
852
    {
853
      net *n = (net *) fn;
854
      rte *e;
855 76dfda9e Martin Mares
      if (max_feed <= 0)
856
        {
857
          FIB_ITERATE_PUT(fit, fn);
858
          return 0;
859
        }
860 ac5d8012 Martin Mares
      for(e=n->routes; e; e=e->next)
861
        {
862
          struct proto *q = e->attrs->proto;
863
          ea_list *tmpa;
864
865
          if (p->core_state != FS_FEEDING)
866
            return 1;  /* In the meantime, the protocol fell down. */
867
          rte_update_lock();
868
          tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
869
          do_rte_announce(h, n, e, NULL, tmpa, ipa_classify(n->n.prefix));
870
          rte_update_unlock();
871 76dfda9e Martin Mares
          max_feed--;
872 ac5d8012 Martin Mares
        }
873
    }
874
  FIB_ITERATE_END(fn);
875
  p->feed_ahook = h->next;
876
  if (!p->feed_ahook)
877
    {
878
      mb_free(p->feed_iterator);
879
      p->feed_iterator = NULL;
880
      return 1;
881
    }
882
883
next_hook:
884
  h = p->feed_ahook;
885
  FIB_ITERATE_INIT(fit, &h->table->fib);
886
  goto again;
887
}
888
889 58740ed4 Martin Mares
/**
890
 * rt_feed_baby_abort - abort protocol feeding
891
 * @p: protocol
892
 *
893
 * This function is called by the protocol code when the protocol
894
 * stops or ceases to exist before the last iteration of rt_feed_baby()
895
 * has finished.
896
 */
897 ac5d8012 Martin Mares
void
898
rt_feed_baby_abort(struct proto *p)
899
{
900
  if (p->feed_ahook)
901
    {
902
      /* Unlink the iterator and exit */
903
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
904
      p->feed_ahook = NULL;
905
    }
906
}
907
908 730f2e2c Martin Mares
/*
909
 *  CLI commands
910
 */
911
912
static void
913 cfd46ee4 Martin Mares
rt_format_via(rte *e, byte *via)
914 730f2e2c Martin Mares
{
915
  rta *a = e->attrs;
916
917
  switch (a->dest)
918
    {
919
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
920
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
921
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
922
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
923
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
924
    default:                bsprintf(via, "???");
925
    }
926 cfd46ee4 Martin Mares
}
927
928
static void
929 ce1da96e Martin Mares
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
930 cfd46ee4 Martin Mares
{
931 85810613 Martin Mares
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
932 cfd46ee4 Martin Mares
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
933
  rta *a = e->attrs;
934
935
  rt_format_via(e, via);
936 730f2e2c Martin Mares
  tm_format_reltime(tm, e->lastmod);
937
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
938
    bsprintf(from, " from %I", a->from);
939
  else
940
    from[0] = 0;
941 ce1da96e Martin Mares
  if (a->proto->proto->get_route_info || d->verbose)
942
    {
943
      /* Need to normalize the extended attributes */
944
      ea_list *t = tmpa;
945
      t = ea_append(t, a->eattrs);
946
      tmpa = alloca(ea_scan(t));
947
      ea_merge(t, tmpa);
948 2f711231 Martin Mares
      ea_sort(tmpa);
949 ce1da96e Martin Mares
    }
950 730f2e2c Martin Mares
  if (a->proto->proto->get_route_info)
951 ce1da96e Martin Mares
    a->proto->proto->get_route_info(e, info, tmpa);
952 730f2e2c Martin Mares
  else
953
    bsprintf(info, " (%d)", e->pref);
954
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
955
  if (d->verbose)
956 ce1da96e Martin Mares
    rta_show(c, a, tmpa);
957 730f2e2c Martin Mares
}
958
959
static void
960
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
961
{
962
  rte *e, *ee;
963
  byte ia[STD_ADDRESS_P_LENGTH+8];
964 ce1da96e Martin Mares
  int ok;
965 730f2e2c Martin Mares
966
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
967 0d307082 Martin Mares
  if (n->routes)
968
    d->net_counter++;
969 730f2e2c Martin Mares
  for(e=n->routes; e; e=e->next)
970
    {
971 ce1da96e Martin Mares
      struct ea_list *tmpa, *old_tmpa;
972
      struct proto *p0 = e->attrs->proto;
973
      struct proto *p1 = d->import_protocol;
974 23693958 Martin Mares
      d->rt_counter++;
975 730f2e2c Martin Mares
      ee = e;
976
      rte_update_lock();                /* We use the update buffer for filtering */
977 ce1da96e Martin Mares
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
978
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
979
      if (ok && d->import_mode)
980
        {
981
          int ic = (p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0);
982
          if (ic < 0)
983
            ok = 0;
984
          else if (!ic && d->import_mode > 1)
985
            {
986
              if (p1->out_filter == FILTER_REJECT ||
987
                  p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
988
                ok = 0;
989
            }
990
        }
991
      if (ok)
992 730f2e2c Martin Mares
        {
993 23693958 Martin Mares
          d->show_counter++;
994 33a368ad Martin Mares
          if (d->stats < 2)
995
            rt_show_rte(c, ia, e, d, tmpa);
996 730f2e2c Martin Mares
          ia[0] = 0;
997
        }
998
      if (e != ee)
999
        rte_free(ee);
1000
      rte_update_unlock();
1001 0117d004 Martin Mares
      if (d->primary_only)
1002 ce1da96e Martin Mares
        break;
1003 730f2e2c Martin Mares
    }
1004
}
1005
1006
static void
1007
rt_show_cont(struct cli *c)
1008
{
1009
  struct rt_show_data *d = c->rover;
1010 f098e072 Martin Mares
#ifdef DEBUGGING
1011
  unsigned max = 4;
1012
#else
1013
  unsigned max = 64;
1014
#endif
1015 730f2e2c Martin Mares
  struct fib *fib = &d->table->fib;
1016
  struct fib_iterator *it = &d->fit;
1017
1018
  FIB_ITERATE_START(fib, it, f)
1019
    {
1020
      net *n = (net *) f;
1021 ce1da96e Martin Mares
      if (d->running_on_config && d->running_on_config != config)
1022
        {
1023
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1024
          goto done;
1025
        }
1026
      if (d->import_protocol &&
1027
          d->import_protocol->core_state != FS_HAPPY &&
1028
          d->import_protocol->core_state != FS_FEEDING)
1029
        {
1030
          cli_printf(c, 8005, "Protocol is down");
1031
          goto done;
1032
        }
1033 730f2e2c Martin Mares
      if (!max--)
1034
        {
1035
          FIB_ITERATE_PUT(it, f);
1036
          return;
1037
        }
1038
      rt_show_net(c, n, d);
1039
    }
1040
  FIB_ITERATE_END(f);
1041 23693958 Martin Mares
  if (d->stats)
1042
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1043
  else
1044
    cli_printf(c, 0, "");
1045 ce1da96e Martin Mares
done:
1046 730f2e2c Martin Mares
  c->cont = c->cleanup = NULL;
1047
}
1048
1049
static void
1050
rt_show_cleanup(struct cli *c)
1051
{
1052
  struct rt_show_data *d = c->rover;
1053
1054
  /* Unlink the iterator */
1055
  fit_get(&d->table->fib, &d->fit);
1056
}
1057
1058
void
1059
rt_show(struct rt_show_data *d)
1060
{
1061
  net *n;
1062
1063
  if (d->pxlen == 256)
1064
    {
1065
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1066
      this_cli->cont = rt_show_cont;
1067
      this_cli->cleanup = rt_show_cleanup;
1068
      this_cli->rover = d;
1069
    }
1070
  else
1071
    {
1072 9449c91a Martin Mares
      if (d->show_for)
1073
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1074
      else
1075
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1076 730f2e2c Martin Mares
      if (n)
1077
        {
1078
          rt_show_net(this_cli, n, d);
1079
          cli_msg(0, "");
1080
        }
1081
      else
1082
        cli_msg(8001, "Network not in table");
1083
    }
1084
}
1085 3ce8c610 Martin Mares
1086
/*
1087
 *  Documentation for functions declared inline in route.h
1088
 */
1089
#if 0
1090

1091
/**
1092
 * net_find - find a network entry
1093
 * @tab: a routing table
1094
 * @addr: address of the network
1095
 * @len: length of the network prefix
1096
 *
1097
 * net_find() looks up the given network in routing table @tab and
1098
 * returns a pointer to its &net entry or %NULL if no such network
1099
 * exists.
1100
 */
1101
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1102
{ DUMMY; }
1103

1104
/**
1105
 * net_get - obtain a network entry
1106
 * @tab: a routing table
1107
 * @addr: address of the network
1108
 * @len: length of the network prefix
1109
 *
1110
 * net_get() looks up the given network in routing table @tab and
1111
 * returns a pointer to its &net entry. If no such entry exists, it's
1112
 * created.
1113
 */
1114
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1115
{ DUMMY; }
1116

1117
/**
1118
 * rte_cow - copy a route for writing
1119
 * @r: a route entry to be copied
1120
 *
1121
 * rte_cow() takes a &rte and prepares it for modification. The exact action
1122
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
1123
 * just returned unchanged, else a new temporary entry with the same contents
1124
 * is created.
1125
 *
1126
 * The primary use of this function is inside the filter machinery -- when
1127
 * a filter wants to modify &rte contents (to change the preference or to
1128
 * attach another set of attributes), it must ensure that the &rte is not
1129
 * shared with anyone else (and especially that it isn't stored in any routing
1130
 * table).
1131
 *
1132 2e9b2421 Martin Mares
 * Result: a pointer to the new writable &rte.
1133 3ce8c610 Martin Mares
 */
1134
static inline rte * rte_cow(rte *r)
1135
{ DUMMY; }
1136

1137
#endif