Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 8a7fb885

History | View | Annotate | Download (33.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
static slab *rte_slab;
47
static linpool *rte_update_pool;
48

    
49
static pool *rt_table_pool;
50
static list routing_tables;
51

    
52
static void rt_format_via(rte *e, byte *via);
53

    
54
static void
55
rte_init(struct fib_node *N)
56
{
57
  net *n = (net *) N;
58

    
59
  N->flags = 0;
60
  n->routes = NULL;
61
}
62

    
63
/**
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
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
/**
82
 * rte_get_temp - get a temporary &rte
83
 * @a: attributes to assign to the new route (a &rta; in case it's
84
 * un-cached, rte_update() will create a cached copy automatically)
85
 *
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
rte *
91
rte_get_temp(rta *a)
92
{
93
  rte *e = sl_alloc(rte_slab);
94

    
95
  e->attrs = a;
96
  e->flags = 0;
97
  e->pref = a->proto->preference;
98
  return e;
99
}
100

    
101
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
static int                                /* Actually better or at least as good as */
113
rte_better(rte *new, rte *old)
114
{
115
  int (*better)(rte *, rte *);
116

    
117
  if (!old)
118
    return 1;
119
  if (new->pref > old->pref)
120
    return 1;
121
  if (new->pref < old->pref)
122
    return 0;
123
  if (new->attrs->proto->proto != old->attrs->proto->proto)
124
    {
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
  if (better = new->attrs->proto->rte_better)
133
    return better(new, old);
134
  return 0;
135
}
136

    
137
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
    rte_trace(p, e, '>', msg);
151
}
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
    rte_trace(p, e, '<', msg);
158
}
159

    
160
static inline void
161
do_rte_announce(struct announce_hook *a, int type, net *net, rte *new, rte *old, ea_list *tmpa, int class, int refeed)
162
{
163
  struct proto *p = a->proto;
164
  rte *new0 = new;
165
  rte *old0 = old;
166
  int ok;
167

    
168
  int fast_exit_hack = 0;
169

    
170
  if (new)
171
    {
172
      p->stats.exp_updates_received++;
173

    
174
      char *drop_reason = NULL;
175
      if ((class & IADDR_SCOPE_MASK) < p->min_scope)
176
        {
177
          p->stats.exp_updates_rejected++;
178
          drop_reason = "out of scope";
179
          fast_exit_hack = 1;
180
        }
181
      else if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
182
        {
183
          p->stats.exp_updates_rejected++;
184
          drop_reason = "rejected by protocol";
185
        }
186
      else if (ok)
187
        rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
188
      else if (p->out_filter == FILTER_REJECT ||
189
               p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
190
        {
191
          p->stats.exp_updates_filtered++;
192
          drop_reason = "filtered out";
193
        }
194
      if (drop_reason)
195
        {
196
          rte_trace_out(D_FILTERS, p, new, drop_reason);
197
          if (new != new0)
198
            rte_free(new);
199
          new = NULL;
200
        }
201
    }
202
  else
203
    p->stats.exp_withdraws_received++;
204

    
205
  /* Hack: This is here to prevent 'spurious withdraws'
206
     for loopback addresses during reload. */
207
  if (fast_exit_hack)
208
    return;
209

    
210
  /*
211
   * This is a tricky part - we don't know whether route 'old' was
212
   * exported to protocol 'p' or was filtered by the export filter.
213
   * We try tu run the export filter to know this to have a correct
214
   * value in 'old' argument of rt_update (and proper filter value)
215
   *
216
   * FIXME - this is broken because 'configure soft' may change
217
   * filters but keep routes. Refeed is expected to be called after
218
   * change of the filters and with old == new, therefore we do not
219
   * even try to run the filter on an old route, This may lead to 
220
   * 'spurious withdraws' but ensure that there are no 'missing
221
   * withdraws'.
222
   *
223
   * This is not completely safe as there is a window between
224
   * reconfiguration and the end of refeed - if a newly filtered
225
   * route disappears during this period, proper withdraw is not
226
   * sent (because old would be also filtered) and the route is
227
   * not refeeded (because it disappeared before that).
228
   */
229

    
230
  if (old && !refeed)
231
    {
232
      if (p->out_filter == FILTER_REJECT)
233
        old = NULL;
234
      else
235
        {
236
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
237
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
238
          if (ok < 0 || (!ok && p->out_filter && f_run(p->out_filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
239
            {
240
              if (old != old0)
241
                rte_free(old);
242
              old = NULL;
243
            }
244
        }
245
    }
246

    
247
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
248
  if (!new && !old)
249
    return;
250

    
251
  if (new)
252
    p->stats.exp_updates_accepted++;
253
  else
254
    p->stats.exp_withdraws_accepted++;
255

    
256
  /* Hack: We do not decrease exp_routes during refeed, we instead
257
     reset exp_routes at the start of refeed. */
258
  if (new)
259
    p->stats.exp_routes++;
260
  if (old && !refeed)
261
    p->stats.exp_routes--;
262

    
263
  if (p->debug & D_ROUTES)
264
    {
265
      if (new && old)
266
        rte_trace_out(D_ROUTES, p, new, "replaced");
267
      else if (new)
268
        rte_trace_out(D_ROUTES, p, new, "added");
269
      else if (old)
270
        rte_trace_out(D_ROUTES, p, old, "removed");
271
    }
272
  if (!new)
273
    p->rt_notify(p, net, NULL, old, NULL);
274
  else if (tmpa)
275
    {
276
      ea_list *t = tmpa;
277
      while (t->next)
278
        t = t->next;
279
      t->next = new->attrs->eattrs;
280
      p->rt_notify(p, net, new, old, tmpa);
281
      t->next = NULL;
282
    }
283
  else
284
    p->rt_notify(p, net, new, old, new->attrs->eattrs);
285
  if (new && new != new0)        /* Discard temporary rte's */
286
    rte_free(new);
287
  if (old && old != old0)
288
    rte_free(old);
289
}
290

    
291
/**
292
 * rte_announce - announce a routing table change
293
 * @tab: table the route has been added to
294
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
295
 * @net: network in question
296
 * @new: the new route to be announced
297
 * @old: the previous route for the same network
298
 * @tmpa: a list of temporary attributes belonging to the new route
299
 *
300
 * This function gets a routing table update and announces it
301
 * to all protocols that acccepts given type of route announcement
302
 * and are connected to the same table by their announcement hooks.
303
 *
304
 * Route announcement of type RA_OPTIMAL si generated when optimal
305
 * route (in routing table @tab) changes. In that case @old stores the
306
 * old optimal route.
307
 *
308
 * Route announcement of type RA_ANY si generated when any route (in
309
 * routing table @tab) changes In that case @old stores the old route
310
 * from the same protocol.
311
 *
312
 * For each appropriate protocol, we first call its import_control()
313
 * hook which performs basic checks on the route (each protocol has a
314
 * right to veto or force accept of the route before any filter is
315
 * asked) and adds default values of attributes specific to the new
316
 * protocol (metrics, tags etc.).  Then it consults the protocol's
317
 * export filter and if it accepts the route, the rt_notify() hook of
318
 * the protocol gets called.
319
 */
320
static void
321
rte_announce(rtable *tab, int type, net *net, rte *new, rte *old, ea_list *tmpa)
322
{
323
  struct announce_hook *a;
324
  int class = ipa_classify(net->n.prefix);
325

    
326
  if (type == RA_OPTIMAL)
327
    {
328
      if (new)
329
        new->attrs->proto->stats.pref_routes++;
330
      if (old)
331
        old->attrs->proto->stats.pref_routes--;
332
    }
333

    
334
  WALK_LIST(a, tab->hooks)
335
    {
336
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
337
      if (a->proto->accept_ra_types == type)
338
        do_rte_announce(a, type, net, new, old, tmpa, class, 0);
339
    }
340
}
341

    
342
static inline int
343
rte_validate(rte *e)
344
{
345
  int c;
346
  net *n = e->net;
347

    
348
  if (ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))))
349
    {
350
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
351
          n->n.prefix, n->n.pxlen, e->sender->name);
352
      return 0;
353
    }
354
  if (n->n.pxlen)
355
    {
356
      c = ipa_classify(n->n.prefix);
357
      if (c < 0 || !(c & IADDR_HOST))
358
        {
359
          if (!ipa_nonzero(n->n.prefix))
360
            {
361
              /* Various default routes */
362
#ifdef IPV6
363
              if (n->n.pxlen == 96)
364
#else
365
              if (n->n.pxlen <= 1)
366
#endif
367
                return 1;
368
            }
369
          log(L_WARN "Ignoring bogus route %I/%d received via %s",
370
              n->n.prefix, n->n.pxlen, e->sender->name);
371
          return 0;
372
        }
373
      if ((c & IADDR_SCOPE_MASK) < e->sender->min_scope)
374
        {
375
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
376
              ip_scope_text(c & IADDR_SCOPE_MASK),
377
              n->n.prefix, n->n.pxlen, e->attrs->from, e->sender->name);
378
          return 0;
379
        }
380
    }
381
  return 1;
382
}
383

    
384
/**
385
 * rte_free - delete a &rte
386
 * @e: &rte to be deleted
387
 *
388
 * rte_free() deletes the given &rte from the routing table it's linked to.
389
 */
390
void
391
rte_free(rte *e)
392
{
393
  if (e->attrs->aflags & RTAF_CACHED)
394
    rta_free(e->attrs);
395
  sl_free(rte_slab, e);
396
}
397

    
398
static inline void
399
rte_free_quick(rte *e)
400
{
401
  rta_free(e->attrs);
402
  sl_free(rte_slab, e);
403
}
404

    
405
static int
406
rte_same(rte *x, rte *y)
407
{
408
  return
409
    x->attrs == y->attrs &&
410
    x->flags == y->flags &&
411
    x->pflags == y->pflags &&
412
    x->pref == y->pref &&
413
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
414
}
415

    
416
static void
417
rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
418
{
419
  rte *old_best = net->routes;
420
  rte *old = NULL;
421
  rte **k, *r, *s;
422

    
423
  k = &net->routes;                        /* Find and remove original route from the same protocol */
424
  while (old = *k)
425
    {
426
      if (old->attrs->proto == src)
427
        {
428
          /* If there is the same route in the routing table but from
429
           * a different sender, then there are two paths from the
430
           * source protocol to this routing table through transparent
431
           * pipes, which is not allowed.
432
           *
433
           * We log that and ignore the route. If it is withdraw, we
434
           * ignore it completely (there might be 'spurious withdraws',
435
           * see FIXME in do_rte_announce())
436
           */
437
          if (old->sender != p)
438
            {
439
              if (new)
440
                {
441
                  log(L_ERR "Pipe collision detected when sending %I/%d to table %s",
442
                      net->n.prefix, net->n.pxlen, table->name);
443
                  rte_free_quick(new);
444
                }
445
              return;
446
            }
447

    
448
          if (new && rte_same(old, new))
449
            {
450
              /* No changes, ignore the new route */
451
              p->stats.imp_updates_ignored++;
452
              rte_trace_in(D_ROUTES, p, new, "ignored");
453
              rte_free_quick(new);
454
              old->lastmod = now;
455
              return;
456
            }
457
          *k = old->next;
458
          break;
459
        }
460
      k = &old->next;
461
    }
462

    
463
  if (!old && !new)
464
    {
465
      p->stats.imp_withdraws_ignored++;
466
      return;
467
    }
468

    
469
  if (new)
470
    p->stats.imp_updates_accepted++;
471
  else
472
    p->stats.imp_withdraws_accepted++;
473

    
474
  if (new)
475
    p->stats.imp_routes++;
476
  if (old)
477
    p->stats.imp_routes--;
478

    
479
  rte_announce(table, RA_ANY, net, new, old, tmpa);
480

    
481
  
482
  if (new && rte_better(new, old_best))
483
    {
484
      /* The first case - the new route is cleary optimal, we link it
485
         at the first position and announce it */
486

    
487
      rte_trace_in(D_ROUTES, p, new, "added [best]");
488
      rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
489
      new->next = net->routes;
490
      net->routes = new;
491
    }
492
  else if (old == old_best)
493
    {
494
      /* The second case - the old best route disappeared, we add the
495
         new route (if we have any) to the list (we don't care about
496
         position) and then we elect the new optimal route and relink
497
         that route at the first position and announce it. New optimal
498
         route might be NULL if there is no more routes */
499

    
500
      /* Add the new route to the list */
501
      if (new)
502
        {
503
          rte_trace_in(D_ROUTES, p, new, "added");
504
          new->next = net->routes;
505
          net->routes = new;
506
        }
507

    
508
      /* Find new optimal route */
509
      r = NULL;
510
      for (s=net->routes; s; s=s->next)
511
        if (rte_better(s, r))
512
          r = s;
513

    
514
      /* Announce optimal route */
515
      rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
516

    
517
      /* And relink it (if there is any) */
518
      if (r)
519
        {
520
          k = &net->routes;
521
          while (s = *k)
522
            {
523
              if (s == r)
524
                {
525
                  *k = r->next;
526
                  break;
527
                }
528
              k = &s->next;
529
            }
530
          r->next = net->routes;
531
          net->routes = r;
532
        }
533
      else if (table->gc_counter++ >= table->config->gc_max_ops &&
534
               table->gc_time + table->config->gc_min_time <= now)
535
        ev_schedule(table->gc_event);
536
    }
537
  else if (new)
538
    {
539
      /* The third case - the new route is not better than the old
540
         best route (therefore old_best != NULL) and the old best
541
         route was not removed (therefore old_best == net->routes).
542
         We just link the new route after the old best route. */
543

    
544
      ASSERT(net->routes != NULL);
545
      new->next = net->routes->next;
546
      net->routes->next = new;
547
      rte_trace_in(D_ROUTES, p, new, "added");
548
    }
549

    
550
  /* Log the route removal */
551
  if (!new && old && (p->debug & D_ROUTES))
552
    {
553
      if (old != old_best)
554
        rte_trace_in(D_ROUTES, p, old, "removed");
555
      else if (net->routes)
556
        rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
557
      else
558
        rte_trace_in(D_ROUTES, p, old, "removed [sole]");
559
    }
560

    
561
  if (old)
562
    {
563
      if (p->rte_remove)
564
        p->rte_remove(net, old);
565
      rte_free_quick(old);
566
    }
567
  if (new)
568
    {
569
      new->lastmod = now;
570
      if (p->rte_insert)
571
        p->rte_insert(net, new);
572
    }
573
}
574

    
575
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
576

    
577
static inline void
578
rte_update_lock(void)
579
{
580
  rte_update_nest_cnt++;
581
}
582

    
583
static inline void
584
rte_update_unlock(void)
585
{
586
  if (!--rte_update_nest_cnt)
587
    lp_flush(rte_update_pool);
588
}
589

    
590
/**
591
 * rte_update - enter a new update to a routing table
592
 * @table: table to be updated
593
 * @net: network node
594
 * @p: protocol submitting the update
595
 * @src: protocol originating the update
596
 * @new: a &rte representing the new route or %NULL for route removal.
597
 *
598
 * This function is called by the routing protocols whenever they discover
599
 * a new route or wish to update/remove an existing route. The right announcement
600
 * sequence is to build route attributes first (either un-cached with @aflags set
601
 * to zero or a cached one using rta_lookup(); in this case please note that
602
 * you need to increase the use count of the attributes yourself by calling
603
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
604
 * the appropriate data and finally submit the new &rte by calling rte_update().
605
 *
606
 * @src specifies the protocol that originally created the route and the meaning
607
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
608
 * same value as @new->attrs->proto. @p specifies the protocol that called
609
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
610
 * stores @p in @new->sender;
611
 *
612
 * When rte_update() gets any route, it automatically validates it (checks,
613
 * whether the network and next hop address are valid IP addresses and also
614
 * whether a normal routing protocol doesn't try to smuggle a host or link
615
 * scope route to the table), converts all protocol dependent attributes stored
616
 * in the &rte to temporary extended attributes, consults import filters of the
617
 * protocol to see if the route should be accepted and/or its attributes modified,
618
 * stores the temporary attributes back to the &rte.
619
 *
620
 * Now, having a "public" version of the route, we
621
 * automatically find any old route defined by the protocol @src
622
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
623
 * recalculate the optimal route for this destination and finally broadcast
624
 * the change (if any) to all routing protocols by calling rte_announce().
625
 *
626
 * All memory used for attribute lists and other temporary allocations is taken
627
 * from a special linear pool @rte_update_pool and freed when rte_update()
628
 * finishes.
629
 */
630

    
631
void
632
rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
633
{
634
  ea_list *tmpa = NULL;
635

    
636
  rte_update_lock();
637
  if (new)
638
    {
639
      new->sender = p;
640
      struct filter *filter = p->in_filter;
641

    
642
      /* Do not filter routes going through the pipe, 
643
         they are filtered in the export filter only. */
644
#ifdef CONFIG_PIPE
645
      if (p->proto == &proto_pipe)
646
        filter = FILTER_ACCEPT;
647
#endif
648

    
649
      p->stats.imp_updates_received++;
650
      if (!rte_validate(new))
651
        {
652
          rte_trace_in(D_FILTERS, p, new, "invalid");
653
          p->stats.imp_updates_invalid++;
654
          goto drop;
655
        }
656
      if (filter == FILTER_REJECT)
657
        {
658
          p->stats.imp_updates_filtered++;
659
          rte_trace_in(D_FILTERS, p, new, "filtered out");
660
          goto drop;
661
        }
662
      if (src->make_tmp_attrs)
663
        tmpa = src->make_tmp_attrs(new, rte_update_pool);
664
      if (filter)
665
        {
666
          ea_list *old_tmpa = tmpa;
667
          int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
668
          if (fr > F_ACCEPT)
669
            {
670
              p->stats.imp_updates_filtered++;
671
              rte_trace_in(D_FILTERS, p, new, "filtered out");
672
              goto drop;
673
            }
674
          if (tmpa != old_tmpa && src->store_tmp_attrs)
675
            src->store_tmp_attrs(new, tmpa);
676
        }
677
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
678
        new->attrs = rta_lookup(new->attrs);
679
      new->flags |= REF_COW;
680
    }
681
  else
682
    p->stats.imp_withdraws_received++;
683

    
684
  rte_recalculate(table, net, p, src, new, tmpa);
685
  rte_update_unlock();
686
  return;
687

    
688
drop:
689
  rte_free(new);
690
  rte_recalculate(table, net, p, src, NULL, NULL);
691
  rte_update_unlock();
692
}
693

    
694
void
695
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
696
{
697
  rte_update_lock();
698
  rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
699
  rte_update_unlock();
700
}
701

    
702
/**
703
 * rte_dump - dump a route
704
 * @e: &rte to be dumped
705
 *
706
 * This functions dumps contents of a &rte to debug output.
707
 */
708
void
709
rte_dump(rte *e)
710
{
711
  net *n = e->net;
712
  if (n)
713
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
714
  else
715
    debug("??? ");
716
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
717
  rta_dump(e->attrs);
718
  if (e->attrs->proto->proto->dump_attrs)
719
    e->attrs->proto->proto->dump_attrs(e);
720
  debug("\n");
721
}
722

    
723
/**
724
 * rt_dump - dump a routing table
725
 * @t: routing table to be dumped
726
 *
727
 * This function dumps contents of a given routing table to debug output.
728
 */
729
void
730
rt_dump(rtable *t)
731
{
732
  rte *e;
733
  net *n;
734
  struct announce_hook *a;
735

    
736
  debug("Dump of routing table <%s>\n", t->name);
737
#ifdef DEBUGGING
738
  fib_check(&t->fib);
739
#endif
740
  FIB_WALK(&t->fib, fn)
741
    {
742
      n = (net *) fn;
743
      for(e=n->routes; e; e=e->next)
744
        rte_dump(e);
745
    }
746
  FIB_WALK_END;
747
  WALK_LIST(a, t->hooks)
748
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
749
  debug("\n");
750
}
751

    
752
/**
753
 * rt_dump_all - dump all routing tables
754
 *
755
 * This function dumps contents of all routing tables to debug output.
756
 */
757
void
758
rt_dump_all(void)
759
{
760
  rtable *t;
761

    
762
  WALK_LIST(t, routing_tables)
763
    rt_dump(t);
764
}
765

    
766
static void
767
rt_gc(void *tab)
768
{
769
  rtable *t = tab;
770

    
771
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
772
      t->name, (int)(now - t->gc_time), t->gc_counter);
773
  rt_prune(t);
774
}
775

    
776
void
777
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
778
{
779
  bzero(t, sizeof(*t));
780
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
781
  t->name = name;
782
  t->config = cf;
783
  init_list(&t->hooks);
784
  if (cf)
785
    {
786
      t->gc_event = ev_new(p);
787
      t->gc_event->hook = rt_gc;
788
      t->gc_event->data = t;
789
      t->gc_time = now;
790
    }
791
}
792

    
793
/**
794
 * rt_init - initialize routing tables
795
 *
796
 * This function is called during BIRD startup. It initializes the
797
 * routing table module.
798
 */
799
void
800
rt_init(void)
801
{
802
  rta_init();
803
  rt_table_pool = rp_new(&root_pool, "Routing tables");
804
  rte_update_pool = lp_new(rt_table_pool, 4080);
805
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
806
  init_list(&routing_tables);
807
}
808

    
809
/**
810
 * rt_prune - prune a routing table
811
 * @tab: routing table to be pruned
812
 *
813
 * This function is called whenever a protocol shuts down. It scans
814
 * the routing table and removes all routes belonging to inactive
815
 * protocols and also stale network entries.
816
 */
817
void
818
rt_prune(rtable *tab)
819
{
820
  struct fib_iterator fit;
821
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
822

    
823
  DBG("Pruning route table %s\n", tab->name);
824
#ifdef DEBUGGING
825
  fib_check(&tab->fib);
826
#endif
827
  FIB_ITERATE_INIT(&fit, &tab->fib);
828
again:
829
  FIB_ITERATE_START(&tab->fib, &fit, f)
830
    {
831
      net *n = (net *) f;
832
      rte *e;
833
      ncnt++;
834
    rescan:
835
      for (e=n->routes; e; e=e->next, rcnt++)
836
        if (e->sender->core_state != FS_HAPPY &&
837
            e->sender->core_state != FS_FEEDING)
838
          {
839
            rte_discard(tab, e);
840
            rdel++;
841
            goto rescan;
842
          }
843
      if (!n->routes)                /* Orphaned FIB entry? */
844
        {
845
          FIB_ITERATE_PUT(&fit, f);
846
          fib_delete(&tab->fib, f);
847
          ndel++;
848
          goto again;
849
        }
850
    }
851
  FIB_ITERATE_END(f);
852
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
853
#ifdef DEBUGGING
854
  fib_check(&tab->fib);
855
#endif
856
  tab->gc_counter = 0;
857
  tab->gc_time = now;
858
}
859

    
860
/**
861
 * rt_prune_all - prune all routing tables
862
 *
863
 * This function calls rt_prune() for all known routing tables.
864
 */
865
void
866
rt_prune_all(void)
867
{
868
  rtable *t;
869

    
870
  WALK_LIST(t, routing_tables)
871
    rt_prune(t);
872
}
873

    
874
struct rtable_config *
875
rt_new_table(struct symbol *s)
876
{
877
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
878

    
879
  cf_define_symbol(s, SYM_TABLE, c);
880
  c->name = s->name;
881
  add_tail(&new_config->tables, &c->n);
882
  c->gc_max_ops = 1000;
883
  c->gc_min_time = 5;
884
  return c;
885
}
886

    
887
void
888
rt_preconfig(struct config *c)
889
{
890
  struct symbol *s = cf_find_symbol("master");
891

    
892
  init_list(&c->tables);
893
  c->master_rtc = rt_new_table(s);
894
}
895

    
896
/**
897
 * rt_lock_table - lock a routing table
898
 * @r: routing table to be locked
899
 *
900
 * Lock a routing table, because it's in use by a protocol,
901
 * preventing it from being freed when it gets undefined in a new
902
 * configuration.
903
 */
904
void
905
rt_lock_table(rtable *r)
906
{
907
  r->use_count++;
908
}
909

    
910
/**
911
 * rt_unlock_table - unlock a routing table
912
 * @r: routing table to be unlocked
913
 *
914
 * Unlock a routing table formerly locked by rt_lock_table(),
915
 * that is decrease its use count and delete it if it's scheduled
916
 * for deletion by configuration changes.
917
 */
918
void
919
rt_unlock_table(rtable *r)
920
{
921
  if (!--r->use_count && r->deleted)
922
    {
923
      struct config *conf = r->deleted;
924
      DBG("Deleting routing table %s\n", r->name);
925
      rem_node(&r->n);
926
      fib_free(&r->fib);
927
      mb_free(r);
928
      config_del_obstacle(conf);
929
    }
930
}
931

    
932
/**
933
 * rt_commit - commit new routing table configuration
934
 * @new: new configuration
935
 * @old: original configuration or %NULL if it's boot time config
936
 *
937
 * Scan differences between @old and @new configuration and modify
938
 * the routing tables according to these changes. If @new defines a
939
 * previously unknown table, create it, if it omits a table existing
940
 * in @old, schedule it for deletion (it gets deleted when all protocols
941
 * disconnect from it by calling rt_unlock_table()), if it exists
942
 * in both configurations, leave it unchanged.
943
 */
944
void
945
rt_commit(struct config *new, struct config *old)
946
{
947
  struct rtable_config *o, *r;
948

    
949
  DBG("rt_commit:\n");
950
  if (old)
951
    {
952
      WALK_LIST(o, old->tables)
953
        {
954
          rtable *ot = o->table;
955
          if (!ot->deleted)
956
            {
957
              struct symbol *sym = cf_find_symbol(o->name);
958
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
959
                {
960
                  DBG("\t%s: same\n", o->name);
961
                  r = sym->def;
962
                  r->table = ot;
963
                  ot->name = r->name;
964
                  ot->config = r;
965
                }
966
              else
967
                {
968
                  DBG("\t%s: deleted\n", o->name);
969
                  ot->deleted = old;
970
                  config_add_obstacle(old);
971
                  rt_lock_table(ot);
972
                  rt_unlock_table(ot);
973
                }
974
            }
975
        }
976
    }
977

    
978
  WALK_LIST(r, new->tables)
979
    if (!r->table)
980
      {
981
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
982
        DBG("\t%s: created\n", r->name);
983
        rt_setup(rt_table_pool, t, r->name, r);
984
        add_tail(&routing_tables, &t->n);
985
        r->table = t;
986
      }
987
  DBG("\tdone\n");
988
}
989

    
990
static inline void
991
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
992
{
993
  struct proto *q = e->attrs->proto;
994
  ea_list *tmpa;
995

    
996
  rte_update_lock();
997
  tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
998
  do_rte_announce(h, type, n, e, p->refeeding ? e : NULL, tmpa, ipa_classify(n->n.prefix), p->refeeding);
999
  rte_update_unlock();
1000
}
1001

    
1002
/**
1003
 * rt_feed_baby - advertise routes to a new protocol
1004
 * @p: protocol to be fed
1005
 *
1006
 * This function performs one pass of advertisement of routes to a newly
1007
 * initialized protocol. It's called by the protocol code as long as it
1008
 * has something to do. (We avoid transferring all the routes in single
1009
 * pass in order not to monopolize CPU time.)
1010
 */
1011
int
1012
rt_feed_baby(struct proto *p)
1013
{
1014
  struct announce_hook *h;
1015
  struct fib_iterator *fit;
1016
  int max_feed = 256;
1017

    
1018
  if (!p->feed_ahook)                        /* Need to initialize first */
1019
    {
1020
      if (!p->ahooks)
1021
        return 1;
1022
      DBG("Announcing routes to new protocol %s\n", p->name);
1023
      p->feed_ahook = p->ahooks;
1024
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1025
      goto next_hook;
1026
    }
1027
  fit = p->feed_iterator;
1028

    
1029
again:
1030
  h = p->feed_ahook;
1031
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1032
    {
1033
      net *n = (net *) fn;
1034
      rte *e = n->routes;
1035
      if (max_feed <= 0)
1036
        {
1037
          FIB_ITERATE_PUT(fit, fn);
1038
          return 0;
1039
        }
1040

    
1041
      if (p->accept_ra_types == RA_OPTIMAL)
1042
        if (e)
1043
          {
1044
            if (p->core_state != FS_FEEDING)
1045
              return 1;  /* In the meantime, the protocol fell down. */
1046
            do_feed_baby(p, RA_OPTIMAL, h, n, e);
1047
            max_feed--;
1048
          }
1049

    
1050
      if (p->accept_ra_types == RA_ANY)
1051
        for(e = n->routes; e != NULL; e = e->next)
1052
          {
1053
            if (p->core_state != FS_FEEDING)
1054
              return 1;  /* In the meantime, the protocol fell down. */
1055
            do_feed_baby(p, RA_ANY, h, n, e);
1056
            max_feed--;
1057
          }
1058
    }
1059
  FIB_ITERATE_END(fn);
1060
  p->feed_ahook = h->next;
1061
  if (!p->feed_ahook)
1062
    {
1063
      mb_free(p->feed_iterator);
1064
      p->feed_iterator = NULL;
1065
      return 1;
1066
    }
1067

    
1068
next_hook:
1069
  h = p->feed_ahook;
1070
  FIB_ITERATE_INIT(fit, &h->table->fib);
1071
  goto again;
1072
}
1073

    
1074
/**
1075
 * rt_feed_baby_abort - abort protocol feeding
1076
 * @p: protocol
1077
 *
1078
 * This function is called by the protocol code when the protocol
1079
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1080
 * has finished.
1081
 */
1082
void
1083
rt_feed_baby_abort(struct proto *p)
1084
{
1085
  if (p->feed_ahook)
1086
    {
1087
      /* Unlink the iterator and exit */
1088
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1089
      p->feed_ahook = NULL;
1090
    }
1091
}
1092

    
1093
/*
1094
 *  CLI commands
1095
 */
1096

    
1097
static void
1098
rt_format_via(rte *e, byte *via)
1099
{
1100
  rta *a = e->attrs;
1101

    
1102
  switch (a->dest)
1103
    {
1104
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
1105
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
1106
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
1107
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
1108
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
1109
    default:                bsprintf(via, "???");
1110
    }
1111
}
1112

    
1113
static void
1114
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1115
{
1116
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
1117
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
1118
  rta *a = e->attrs;
1119

    
1120
  rt_format_via(e, via);
1121
  tm_format_reltime(tm, e->lastmod);
1122
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
1123
    bsprintf(from, " from %I", a->from);
1124
  else
1125
    from[0] = 0;
1126
  if (a->proto->proto->get_route_info || d->verbose)
1127
    {
1128
      /* Need to normalize the extended attributes */
1129
      ea_list *t = tmpa;
1130
      t = ea_append(t, a->eattrs);
1131
      tmpa = alloca(ea_scan(t));
1132
      ea_merge(t, tmpa);
1133
      ea_sort(tmpa);
1134
    }
1135
  if (a->proto->proto->get_route_info)
1136
    a->proto->proto->get_route_info(e, info, tmpa);
1137
  else
1138
    bsprintf(info, " (%d)", e->pref);
1139
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
1140
  if (d->verbose)
1141
    rta_show(c, a, tmpa);
1142
}
1143

    
1144
static void
1145
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
1146
{
1147
  rte *e, *ee;
1148
  byte ia[STD_ADDRESS_P_LENGTH+8];
1149
  int ok;
1150

    
1151
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
1152
  if (n->routes)
1153
    d->net_counter++;
1154
  for(e=n->routes; e; e=e->next)
1155
    {
1156
      struct ea_list *tmpa, *old_tmpa;
1157
      struct proto *p0 = e->attrs->proto;
1158
      struct proto *p1 = d->export_protocol;
1159
      struct proto *p2 = d->show_protocol;
1160
      d->rt_counter++;
1161
      ee = e;
1162
      rte_update_lock();                /* We use the update buffer for filtering */
1163
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
1164
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1165
      if (p2 && p2 != p0) ok = 0;
1166
      if (ok && d->export_mode)
1167
        {
1168
          int class = ipa_classify(n->n.prefix);
1169
          int ic;
1170
          if ((class & IADDR_SCOPE_MASK) < p1->min_scope)
1171
            ok = 0;
1172
          else if ((ic = p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0) < 0)
1173
            ok = 0;
1174
          else if (!ic && d->export_mode > 1)
1175
            {
1176
              /* FIXME - this shows what should be exported according
1177
                 to current filters, but not what was really exported.
1178
                 'configure soft' command may change the export filter
1179
                 and do not update routes */
1180

    
1181
              if (p1->out_filter == FILTER_REJECT ||
1182
                  p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
1183
                ok = 0;
1184
            }
1185
        }
1186
      if (ok)
1187
        {
1188
          d->show_counter++;
1189
          if (d->stats < 2)
1190
            rt_show_rte(c, ia, e, d, tmpa);
1191
          ia[0] = 0;
1192
        }
1193
      if (e != ee)
1194
        rte_free(ee);
1195
      rte_update_unlock();
1196
      if (d->primary_only)
1197
        break;
1198
    }
1199
}
1200

    
1201
static void
1202
rt_show_cont(struct cli *c)
1203
{
1204
  struct rt_show_data *d = c->rover;
1205
#ifdef DEBUGGING
1206
  unsigned max = 4;
1207
#else
1208
  unsigned max = 64;
1209
#endif
1210
  struct fib *fib = &d->table->fib;
1211
  struct fib_iterator *it = &d->fit;
1212

    
1213
  FIB_ITERATE_START(fib, it, f)
1214
    {
1215
      net *n = (net *) f;
1216
      if (d->running_on_config && d->running_on_config != config)
1217
        {
1218
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1219
          goto done;
1220
        }
1221
      if (d->export_protocol &&
1222
          d->export_protocol->core_state != FS_HAPPY &&
1223
          d->export_protocol->core_state != FS_FEEDING)
1224
        {
1225
          cli_printf(c, 8005, "Protocol is down");
1226
          goto done;
1227
        }
1228
      if (!max--)
1229
        {
1230
          FIB_ITERATE_PUT(it, f);
1231
          return;
1232
        }
1233
      rt_show_net(c, n, d);
1234
    }
1235
  FIB_ITERATE_END(f);
1236
  if (d->stats)
1237
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1238
  else
1239
    cli_printf(c, 0, "");
1240
done:
1241
  c->cont = c->cleanup = NULL;
1242
}
1243

    
1244
static void
1245
rt_show_cleanup(struct cli *c)
1246
{
1247
  struct rt_show_data *d = c->rover;
1248

    
1249
  /* Unlink the iterator */
1250
  fit_get(&d->table->fib, &d->fit);
1251
}
1252

    
1253
void
1254
rt_show(struct rt_show_data *d)
1255
{
1256
  net *n;
1257

    
1258
  if (d->pxlen == 256)
1259
    {
1260
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1261
      this_cli->cont = rt_show_cont;
1262
      this_cli->cleanup = rt_show_cleanup;
1263
      this_cli->rover = d;
1264
    }
1265
  else
1266
    {
1267
      if (d->show_for)
1268
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1269
      else
1270
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1271
      if (n)
1272
        {
1273
          rt_show_net(this_cli, n, d);
1274
          cli_msg(0, "");
1275
        }
1276
      else
1277
        cli_msg(8001, "Network not in table");
1278
    }
1279
}
1280

    
1281
/*
1282
 *  Documentation for functions declared inline in route.h
1283
 */
1284
#if 0
1285

1286
/**
1287
 * net_find - find a network entry
1288
 * @tab: a routing table
1289
 * @addr: address of the network
1290
 * @len: length of the network prefix
1291
 *
1292
 * net_find() looks up the given network in routing table @tab and
1293
 * returns a pointer to its &net entry or %NULL if no such network
1294
 * exists.
1295
 */
1296
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1297
{ DUMMY; }
1298

1299
/**
1300
 * net_get - obtain a network entry
1301
 * @tab: a routing table
1302
 * @addr: address of the network
1303
 * @len: length of the network prefix
1304
 *
1305
 * net_get() looks up the given network in routing table @tab and
1306
 * returns a pointer to its &net entry. If no such entry exists, it's
1307
 * created.
1308
 */
1309
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1310
{ DUMMY; }
1311

1312
/**
1313
 * rte_cow - copy a route for writing
1314
 * @r: a route entry to be copied
1315
 *
1316
 * rte_cow() takes a &rte and prepares it for modification. The exact action
1317
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
1318
 * just returned unchanged, else a new temporary entry with the same contents
1319
 * is created.
1320
 *
1321
 * The primary use of this function is inside the filter machinery -- when
1322
 * a filter wants to modify &rte contents (to change the preference or to
1323
 * attach another set of attributes), it must ensure that the &rte is not
1324
 * shared with anyone else (and especially that it isn't stored in any routing
1325
 * table).
1326
 *
1327
 * Result: a pointer to the new writable &rte.
1328
 */
1329
static inline rte * rte_cow(rte *r)
1330
{ DUMMY; }
1331

1332
#endif