Statistics
| Branch: | Revision:

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

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

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

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

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

1140
#endif