Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ e81b440f

History | View | Annotate | Download (34.4 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 UNUSED, net *net, rte *new, rte *old, ea_list *tmpa, int class, int refeed)
162
{
163
  struct proto *p = a->proto;
164
  struct filter *filter = p->out_filter;
165
  struct proto_stats *stats = &p->stats;
166
  rte *new0 = new;
167
  rte *old0 = old;
168
  int ok;
169

    
170
  int fast_exit_hack = 0;
171

    
172
#ifdef CONFIG_PIPE
173
  /* The secondary direction of the pipe */
174
  if (proto_is_pipe(p) && (p->table != a->table))
175
    {
176
      filter = p->in_filter;
177
      stats = pipe_get_peer_stats(p);
178
    }
179
#endif
180

    
181
  if (new)
182
    {
183
      stats->exp_updates_received++;
184

    
185
      char *drop_reason = NULL;
186
      if ((class & IADDR_SCOPE_MASK) < p->min_scope)
187
        {
188
          stats->exp_updates_rejected++;
189
          drop_reason = "out of scope";
190
          fast_exit_hack = 1;
191
        }
192
      else if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
193
        {
194
          stats->exp_updates_rejected++;
195
          drop_reason = "rejected by protocol";
196
        }
197
      else if (ok)
198
        rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
199
      else if ((filter == FILTER_REJECT) ||
200
               (filter && f_run(filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
201
        {
202
          stats->exp_updates_filtered++;
203
          drop_reason = "filtered out";
204
        }
205
      if (drop_reason)
206
        {
207
          rte_trace_out(D_FILTERS, p, new, drop_reason);
208
          if (new != new0)
209
            rte_free(new);
210
          new = NULL;
211
        }
212
    }
213
  else
214
    stats->exp_withdraws_received++;
215

    
216
  /* Hack: This is here to prevent 'spurious withdraws'
217
     for loopback addresses during reload. */
218
  if (fast_exit_hack)
219
    return;
220

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

    
241
  if (old && !refeed)
242
    {
243
      if (filter == FILTER_REJECT)
244
        old = NULL;
245
      else
246
        {
247
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
248
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
249
          if (ok < 0 || (!ok && filter && f_run(filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
250
            {
251
              if (old != old0)
252
                rte_free(old);
253
              old = NULL;
254
            }
255
        }
256
    }
257

    
258
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
259
  if (!new && !old)
260
    return;
261

    
262
  if (new)
263
    stats->exp_updates_accepted++;
264
  else
265
    stats->exp_withdraws_accepted++;
266

    
267
  /* Hack: We do not decrease exp_routes during refeed, we instead
268
     reset exp_routes at the start of refeed. */
269
  if (new)
270
    stats->exp_routes++;
271
  if (old && !refeed)
272
    stats->exp_routes--;
273

    
274
  if (p->debug & D_ROUTES)
275
    {
276
      if (new && old)
277
        rte_trace_out(D_ROUTES, p, new, "replaced");
278
      else if (new)
279
        rte_trace_out(D_ROUTES, p, new, "added");
280
      else if (old)
281
        rte_trace_out(D_ROUTES, p, old, "removed");
282
    }
283
  if (!new)
284
    p->rt_notify(p, a->table, net, NULL, old, NULL);
285
  else if (tmpa)
286
    {
287
      ea_list *t = tmpa;
288
      while (t->next)
289
        t = t->next;
290
      t->next = new->attrs->eattrs;
291
      p->rt_notify(p, a->table, net, new, old, tmpa);
292
      t->next = NULL;
293
    }
294
  else
295
    p->rt_notify(p, a->table, net, new, old, new->attrs->eattrs);
296
  if (new && new != new0)        /* Discard temporary rte's */
297
    rte_free(new);
298
  if (old && old != old0)
299
    rte_free(old);
300
}
301

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

    
337
  if (type == RA_OPTIMAL)
338
    {
339
      if (new)
340
        new->attrs->proto->stats.pref_routes++;
341
      if (old)
342
        old->attrs->proto->stats.pref_routes--;
343
    }
344

    
345
  WALK_LIST(a, tab->hooks)
346
    {
347
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
348
      if (a->proto->accept_ra_types == type)
349
        do_rte_announce(a, type, net, new, old, tmpa, class, 0);
350
    }
351
}
352

    
353
static inline int
354
rte_validate(rte *e)
355
{
356
  int c;
357
  net *n = e->net;
358

    
359
  if (ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))))
360
    {
361
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
362
          n->n.prefix, n->n.pxlen, e->sender->name);
363
      return 0;
364
    }
365
  if (n->n.pxlen)
366
    {
367
      c = ipa_classify(n->n.prefix);
368
      if (c < 0 || !(c & IADDR_HOST))
369
        {
370
          if (!ipa_nonzero(n->n.prefix))
371
            {
372
              /* Various default routes */
373
#ifdef IPV6
374
              if (n->n.pxlen == 96)
375
#else
376
              if (n->n.pxlen <= 1)
377
#endif
378
                return 1;
379
            }
380
          log(L_WARN "Ignoring bogus route %I/%d received via %s",
381
              n->n.prefix, n->n.pxlen, e->sender->name);
382
          return 0;
383
        }
384
      if ((c & IADDR_SCOPE_MASK) < e->sender->min_scope)
385
        {
386
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
387
              ip_scope_text(c & IADDR_SCOPE_MASK),
388
              n->n.prefix, n->n.pxlen, e->attrs->from, e->sender->name);
389
          return 0;
390
        }
391
    }
392
  return 1;
393
}
394

    
395
/**
396
 * rte_free - delete a &rte
397
 * @e: &rte to be deleted
398
 *
399
 * rte_free() deletes the given &rte from the routing table it's linked to.
400
 */
401
void
402
rte_free(rte *e)
403
{
404
  if (e->attrs->aflags & RTAF_CACHED)
405
    rta_free(e->attrs);
406
  sl_free(rte_slab, e);
407
}
408

    
409
static inline void
410
rte_free_quick(rte *e)
411
{
412
  rta_free(e->attrs);
413
  sl_free(rte_slab, e);
414
}
415

    
416
static int
417
rte_same(rte *x, rte *y)
418
{
419
  return
420
    x->attrs == y->attrs &&
421
    x->flags == y->flags &&
422
    x->pflags == y->pflags &&
423
    x->pref == y->pref &&
424
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
425
}
426

    
427
static void
428
rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
429
{
430
  struct proto_stats *stats = &p->stats;
431
  rte *old_best = net->routes;
432
  rte *old = NULL;
433
  rte **k, *r, *s;
434

    
435
#ifdef CONFIG_PIPE
436
  if (proto_is_pipe(p) && (p->table == table))
437
    stats = pipe_get_peer_stats(p);
438
#endif
439

    
440
  k = &net->routes;                        /* Find and remove original route from the same protocol */
441
  while (old = *k)
442
    {
443
      if (old->attrs->proto == src)
444
        {
445
          /* If there is the same route in the routing table but from
446
           * a different sender, then there are two paths from the
447
           * source protocol to this routing table through transparent
448
           * pipes, which is not allowed.
449
           *
450
           * We log that and ignore the route. If it is withdraw, we
451
           * ignore it completely (there might be 'spurious withdraws',
452
           * see FIXME in do_rte_announce())
453
           */
454
          if (old->sender != p)
455
            {
456
              if (new)
457
                {
458
                  log(L_ERR "Pipe collision detected when sending %I/%d to table %s",
459
                      net->n.prefix, net->n.pxlen, table->name);
460
                  rte_free_quick(new);
461
                }
462
              return;
463
            }
464

    
465
          if (new && rte_same(old, new))
466
            {
467
              /* No changes, ignore the new route */
468
              stats->imp_updates_ignored++;
469
              rte_trace_in(D_ROUTES, p, new, "ignored");
470
              rte_free_quick(new);
471
              old->lastmod = now;
472
              return;
473
            }
474
          *k = old->next;
475
          break;
476
        }
477
      k = &old->next;
478
    }
479

    
480
  if (!old && !new)
481
    {
482
      stats->imp_withdraws_ignored++;
483
      return;
484
    }
485

    
486
  if (new)
487
    stats->imp_updates_accepted++;
488
  else
489
    stats->imp_withdraws_accepted++;
490

    
491
  if (new)
492
    stats->imp_routes++;
493
  if (old)
494
    stats->imp_routes--;
495

    
496
  rte_announce(table, RA_ANY, net, new, old, tmpa);
497

    
498
  
499
  if (new && rte_better(new, old_best))
500
    {
501
      /* The first case - the new route is cleary optimal, we link it
502
         at the first position and announce it */
503

    
504
      rte_trace_in(D_ROUTES, p, new, "added [best]");
505
      rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
506
      new->next = net->routes;
507
      net->routes = new;
508
    }
509
  else if (old == old_best)
510
    {
511
      /* The second case - the old best route disappeared, we add the
512
         new route (if we have any) to the list (we don't care about
513
         position) and then we elect the new optimal route and relink
514
         that route at the first position and announce it. New optimal
515
         route might be NULL if there is no more routes */
516

    
517
      /* Add the new route to the list */
518
      if (new)
519
        {
520
          rte_trace_in(D_ROUTES, p, new, "added");
521
          new->next = net->routes;
522
          net->routes = new;
523
        }
524

    
525
      /* Find new optimal route */
526
      r = NULL;
527
      for (s=net->routes; s; s=s->next)
528
        if (rte_better(s, r))
529
          r = s;
530

    
531
      /* Announce optimal route */
532
      rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
533

    
534
      /* And relink it (if there is any) */
535
      if (r)
536
        {
537
          k = &net->routes;
538
          while (s = *k)
539
            {
540
              if (s == r)
541
                {
542
                  *k = r->next;
543
                  break;
544
                }
545
              k = &s->next;
546
            }
547
          r->next = net->routes;
548
          net->routes = r;
549
        }
550
      else if (table->gc_counter++ >= table->config->gc_max_ops &&
551
               table->gc_time + table->config->gc_min_time <= now)
552
        ev_schedule(table->gc_event);
553
    }
554
  else if (new)
555
    {
556
      /* The third case - the new route is not better than the old
557
         best route (therefore old_best != NULL) and the old best
558
         route was not removed (therefore old_best == net->routes).
559
         We just link the new route after the old best route. */
560

    
561
      ASSERT(net->routes != NULL);
562
      new->next = net->routes->next;
563
      net->routes->next = new;
564
      rte_trace_in(D_ROUTES, p, new, "added");
565
    }
566

    
567
  /* Log the route removal */
568
  if (!new && old && (p->debug & D_ROUTES))
569
    {
570
      if (old != old_best)
571
        rte_trace_in(D_ROUTES, p, old, "removed");
572
      else if (net->routes)
573
        rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
574
      else
575
        rte_trace_in(D_ROUTES, p, old, "removed [sole]");
576
    }
577

    
578
  if (old)
579
    {
580
      if (p->rte_remove)
581
        p->rte_remove(net, old);
582
      rte_free_quick(old);
583
    }
584
  if (new)
585
    {
586
      new->lastmod = now;
587
      if (p->rte_insert)
588
        p->rte_insert(net, new);
589
    }
590
}
591

    
592
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
593

    
594
static inline void
595
rte_update_lock(void)
596
{
597
  rte_update_nest_cnt++;
598
}
599

    
600
static inline void
601
rte_update_unlock(void)
602
{
603
  if (!--rte_update_nest_cnt)
604
    lp_flush(rte_update_pool);
605
}
606

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

    
648
void
649
rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
650
{
651
  ea_list *tmpa = NULL;
652
  struct proto_stats *stats = &p->stats;
653

    
654
#ifdef CONFIG_PIPE
655
  if (proto_is_pipe(p) && (p->table == table))
656
    stats = pipe_get_peer_stats(p);
657
#endif
658

    
659
  rte_update_lock();
660
  if (new)
661
    {
662
      new->sender = p;
663
      struct filter *filter = p->in_filter;
664

    
665
      /* Do not filter routes going through the pipe, 
666
         they are filtered in the export filter only. */
667
#ifdef CONFIG_PIPE
668
      if (proto_is_pipe(p))
669
        filter = FILTER_ACCEPT;
670
#endif
671

    
672
      stats->imp_updates_received++;
673
      if (!rte_validate(new))
674
        {
675
          rte_trace_in(D_FILTERS, p, new, "invalid");
676
          stats->imp_updates_invalid++;
677
          goto drop;
678
        }
679
      if (filter == FILTER_REJECT)
680
        {
681
          stats->imp_updates_filtered++;
682
          rte_trace_in(D_FILTERS, p, new, "filtered out");
683
          goto drop;
684
        }
685
      if (src->make_tmp_attrs)
686
        tmpa = src->make_tmp_attrs(new, rte_update_pool);
687
      if (filter)
688
        {
689
          ea_list *old_tmpa = tmpa;
690
          int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
691
          if (fr > F_ACCEPT)
692
            {
693
              stats->imp_updates_filtered++;
694
              rte_trace_in(D_FILTERS, p, new, "filtered out");
695
              goto drop;
696
            }
697
          if (tmpa != old_tmpa && src->store_tmp_attrs)
698
            src->store_tmp_attrs(new, tmpa);
699
        }
700
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
701
        new->attrs = rta_lookup(new->attrs);
702
      new->flags |= REF_COW;
703
    }
704
  else
705
    stats->imp_withdraws_received++;
706

    
707
  rte_recalculate(table, net, p, src, new, tmpa);
708
  rte_update_unlock();
709
  return;
710

    
711
drop:
712
  rte_free(new);
713
  rte_recalculate(table, net, p, src, NULL, NULL);
714
  rte_update_unlock();
715
}
716

    
717
void
718
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
719
{
720
  rte_update_lock();
721
  rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
722
  rte_update_unlock();
723
}
724

    
725
/**
726
 * rte_dump - dump a route
727
 * @e: &rte to be dumped
728
 *
729
 * This functions dumps contents of a &rte to debug output.
730
 */
731
void
732
rte_dump(rte *e)
733
{
734
  net *n = e->net;
735
  if (n)
736
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
737
  else
738
    debug("??? ");
739
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
740
  rta_dump(e->attrs);
741
  if (e->attrs->proto->proto->dump_attrs)
742
    e->attrs->proto->proto->dump_attrs(e);
743
  debug("\n");
744
}
745

    
746
/**
747
 * rt_dump - dump a routing table
748
 * @t: routing table to be dumped
749
 *
750
 * This function dumps contents of a given routing table to debug output.
751
 */
752
void
753
rt_dump(rtable *t)
754
{
755
  rte *e;
756
  net *n;
757
  struct announce_hook *a;
758

    
759
  debug("Dump of routing table <%s>\n", t->name);
760
#ifdef DEBUGGING
761
  fib_check(&t->fib);
762
#endif
763
  FIB_WALK(&t->fib, fn)
764
    {
765
      n = (net *) fn;
766
      for(e=n->routes; e; e=e->next)
767
        rte_dump(e);
768
    }
769
  FIB_WALK_END;
770
  WALK_LIST(a, t->hooks)
771
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
772
  debug("\n");
773
}
774

    
775
/**
776
 * rt_dump_all - dump all routing tables
777
 *
778
 * This function dumps contents of all routing tables to debug output.
779
 */
780
void
781
rt_dump_all(void)
782
{
783
  rtable *t;
784

    
785
  WALK_LIST(t, routing_tables)
786
    rt_dump(t);
787
}
788

    
789
static void
790
rt_gc(void *tab)
791
{
792
  rtable *t = tab;
793

    
794
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
795
      t->name, (int)(now - t->gc_time), t->gc_counter);
796
  rt_prune(t);
797
}
798

    
799
void
800
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
801
{
802
  bzero(t, sizeof(*t));
803
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
804
  t->name = name;
805
  t->config = cf;
806
  init_list(&t->hooks);
807
  if (cf)
808
    {
809
      t->gc_event = ev_new(p);
810
      t->gc_event->hook = rt_gc;
811
      t->gc_event->data = t;
812
      t->gc_time = now;
813
    }
814
}
815

    
816
/**
817
 * rt_init - initialize routing tables
818
 *
819
 * This function is called during BIRD startup. It initializes the
820
 * routing table module.
821
 */
822
void
823
rt_init(void)
824
{
825
  rta_init();
826
  rt_table_pool = rp_new(&root_pool, "Routing tables");
827
  rte_update_pool = lp_new(rt_table_pool, 4080);
828
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
829
  init_list(&routing_tables);
830
}
831

    
832
/**
833
 * rt_prune - prune a routing table
834
 * @tab: routing table to be pruned
835
 *
836
 * This function is called whenever a protocol shuts down. It scans
837
 * the routing table and removes all routes belonging to inactive
838
 * protocols and also stale network entries.
839
 */
840
void
841
rt_prune(rtable *tab)
842
{
843
  struct fib_iterator fit;
844
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
845

    
846
  DBG("Pruning route table %s\n", tab->name);
847
#ifdef DEBUGGING
848
  fib_check(&tab->fib);
849
#endif
850
  FIB_ITERATE_INIT(&fit, &tab->fib);
851
again:
852
  FIB_ITERATE_START(&tab->fib, &fit, f)
853
    {
854
      net *n = (net *) f;
855
      rte *e;
856
      ncnt++;
857
    rescan:
858
      for (e=n->routes; e; e=e->next, rcnt++)
859
        if (e->sender->core_state != FS_HAPPY &&
860
            e->sender->core_state != FS_FEEDING)
861
          {
862
            rte_discard(tab, e);
863
            rdel++;
864
            goto rescan;
865
          }
866
      if (!n->routes)                /* Orphaned FIB entry? */
867
        {
868
          FIB_ITERATE_PUT(&fit, f);
869
          fib_delete(&tab->fib, f);
870
          ndel++;
871
          goto again;
872
        }
873
    }
874
  FIB_ITERATE_END(f);
875
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
876
#ifdef DEBUGGING
877
  fib_check(&tab->fib);
878
#endif
879
  tab->gc_counter = 0;
880
  tab->gc_time = now;
881
}
882

    
883
/**
884
 * rt_prune_all - prune all routing tables
885
 *
886
 * This function calls rt_prune() for all known routing tables.
887
 */
888
void
889
rt_prune_all(void)
890
{
891
  rtable *t;
892

    
893
  WALK_LIST(t, routing_tables)
894
    rt_prune(t);
895
}
896

    
897
struct rtable_config *
898
rt_new_table(struct symbol *s)
899
{
900
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
901

    
902
  cf_define_symbol(s, SYM_TABLE, c);
903
  c->name = s->name;
904
  add_tail(&new_config->tables, &c->n);
905
  c->gc_max_ops = 1000;
906
  c->gc_min_time = 5;
907
  return c;
908
}
909

    
910
void
911
rt_preconfig(struct config *c)
912
{
913
  struct symbol *s = cf_find_symbol("master");
914

    
915
  init_list(&c->tables);
916
  c->master_rtc = rt_new_table(s);
917
}
918

    
919
/**
920
 * rt_lock_table - lock a routing table
921
 * @r: routing table to be locked
922
 *
923
 * Lock a routing table, because it's in use by a protocol,
924
 * preventing it from being freed when it gets undefined in a new
925
 * configuration.
926
 */
927
void
928
rt_lock_table(rtable *r)
929
{
930
  r->use_count++;
931
}
932

    
933
/**
934
 * rt_unlock_table - unlock a routing table
935
 * @r: routing table to be unlocked
936
 *
937
 * Unlock a routing table formerly locked by rt_lock_table(),
938
 * that is decrease its use count and delete it if it's scheduled
939
 * for deletion by configuration changes.
940
 */
941
void
942
rt_unlock_table(rtable *r)
943
{
944
  if (!--r->use_count && r->deleted)
945
    {
946
      struct config *conf = r->deleted;
947
      DBG("Deleting routing table %s\n", r->name);
948
      rem_node(&r->n);
949
      fib_free(&r->fib);
950
      mb_free(r);
951
      config_del_obstacle(conf);
952
    }
953
}
954

    
955
/**
956
 * rt_commit - commit new routing table configuration
957
 * @new: new configuration
958
 * @old: original configuration or %NULL if it's boot time config
959
 *
960
 * Scan differences between @old and @new configuration and modify
961
 * the routing tables according to these changes. If @new defines a
962
 * previously unknown table, create it, if it omits a table existing
963
 * in @old, schedule it for deletion (it gets deleted when all protocols
964
 * disconnect from it by calling rt_unlock_table()), if it exists
965
 * in both configurations, leave it unchanged.
966
 */
967
void
968
rt_commit(struct config *new, struct config *old)
969
{
970
  struct rtable_config *o, *r;
971

    
972
  DBG("rt_commit:\n");
973
  if (old)
974
    {
975
      WALK_LIST(o, old->tables)
976
        {
977
          rtable *ot = o->table;
978
          if (!ot->deleted)
979
            {
980
              struct symbol *sym = cf_find_symbol(o->name);
981
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
982
                {
983
                  DBG("\t%s: same\n", o->name);
984
                  r = sym->def;
985
                  r->table = ot;
986
                  ot->name = r->name;
987
                  ot->config = r;
988
                }
989
              else
990
                {
991
                  DBG("\t%s: deleted\n", o->name);
992
                  ot->deleted = old;
993
                  config_add_obstacle(old);
994
                  rt_lock_table(ot);
995
                  rt_unlock_table(ot);
996
                }
997
            }
998
        }
999
    }
1000

    
1001
  WALK_LIST(r, new->tables)
1002
    if (!r->table)
1003
      {
1004
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
1005
        DBG("\t%s: created\n", r->name);
1006
        rt_setup(rt_table_pool, t, r->name, r);
1007
        add_tail(&routing_tables, &t->n);
1008
        r->table = t;
1009
      }
1010
  DBG("\tdone\n");
1011
}
1012

    
1013
static inline void
1014
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
1015
{
1016
  struct proto *q = e->attrs->proto;
1017
  ea_list *tmpa;
1018

    
1019
  rte_update_lock();
1020
  tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
1021
  do_rte_announce(h, type, n, e, p->refeeding ? e : NULL, tmpa, ipa_classify(n->n.prefix), p->refeeding);
1022
  rte_update_unlock();
1023
}
1024

    
1025
/**
1026
 * rt_feed_baby - advertise routes to a new protocol
1027
 * @p: protocol to be fed
1028
 *
1029
 * This function performs one pass of advertisement of routes to a newly
1030
 * initialized protocol. It's called by the protocol code as long as it
1031
 * has something to do. (We avoid transferring all the routes in single
1032
 * pass in order not to monopolize CPU time.)
1033
 */
1034
int
1035
rt_feed_baby(struct proto *p)
1036
{
1037
  struct announce_hook *h;
1038
  struct fib_iterator *fit;
1039
  int max_feed = 256;
1040

    
1041
  if (!p->feed_ahook)                        /* Need to initialize first */
1042
    {
1043
      if (!p->ahooks)
1044
        return 1;
1045
      DBG("Announcing routes to new protocol %s\n", p->name);
1046
      p->feed_ahook = p->ahooks;
1047
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1048
      goto next_hook;
1049
    }
1050
  fit = p->feed_iterator;
1051

    
1052
again:
1053
  h = p->feed_ahook;
1054
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1055
    {
1056
      net *n = (net *) fn;
1057
      rte *e = n->routes;
1058
      if (max_feed <= 0)
1059
        {
1060
          FIB_ITERATE_PUT(fit, fn);
1061
          return 0;
1062
        }
1063

    
1064
      if (p->accept_ra_types == RA_OPTIMAL)
1065
        if (e)
1066
          {
1067
            if (p->core_state != FS_FEEDING)
1068
              return 1;  /* In the meantime, the protocol fell down. */
1069
            do_feed_baby(p, RA_OPTIMAL, h, n, e);
1070
            max_feed--;
1071
          }
1072

    
1073
      if (p->accept_ra_types == RA_ANY)
1074
        for(e = n->routes; e != NULL; e = e->next)
1075
          {
1076
            if (p->core_state != FS_FEEDING)
1077
              return 1;  /* In the meantime, the protocol fell down. */
1078
            do_feed_baby(p, RA_ANY, h, n, e);
1079
            max_feed--;
1080
          }
1081
    }
1082
  FIB_ITERATE_END(fn);
1083
  p->feed_ahook = h->next;
1084
  if (!p->feed_ahook)
1085
    {
1086
      mb_free(p->feed_iterator);
1087
      p->feed_iterator = NULL;
1088
      return 1;
1089
    }
1090

    
1091
next_hook:
1092
  h = p->feed_ahook;
1093
  FIB_ITERATE_INIT(fit, &h->table->fib);
1094
  goto again;
1095
}
1096

    
1097
/**
1098
 * rt_feed_baby_abort - abort protocol feeding
1099
 * @p: protocol
1100
 *
1101
 * This function is called by the protocol code when the protocol
1102
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1103
 * has finished.
1104
 */
1105
void
1106
rt_feed_baby_abort(struct proto *p)
1107
{
1108
  if (p->feed_ahook)
1109
    {
1110
      /* Unlink the iterator and exit */
1111
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1112
      p->feed_ahook = NULL;
1113
    }
1114
}
1115

    
1116
/*
1117
 *  CLI commands
1118
 */
1119

    
1120
static void
1121
rt_format_via(rte *e, byte *via)
1122
{
1123
  rta *a = e->attrs;
1124

    
1125
  switch (a->dest)
1126
    {
1127
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
1128
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
1129
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
1130
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
1131
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
1132
    default:                bsprintf(via, "???");
1133
    }
1134
}
1135

    
1136
static void
1137
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1138
{
1139
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
1140
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
1141
  rta *a = e->attrs;
1142
  int primary = (e->net->routes == e);
1143

    
1144
  rt_format_via(e, via);
1145
  tm_format_datetime(tm, &config->tf_route, e->lastmod);
1146
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
1147
    bsprintf(from, " from %I", a->from);
1148
  else
1149
    from[0] = 0;
1150
  if (a->proto->proto->get_route_info || d->verbose)
1151
    {
1152
      /* Need to normalize the extended attributes */
1153
      ea_list *t = tmpa;
1154
      t = ea_append(t, a->eattrs);
1155
      tmpa = alloca(ea_scan(t));
1156
      ea_merge(t, tmpa);
1157
      ea_sort(tmpa);
1158
    }
1159
  if (a->proto->proto->get_route_info)
1160
    a->proto->proto->get_route_info(e, info, tmpa);
1161
  else
1162
    bsprintf(info, " (%d)", e->pref);
1163
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->proto->name,
1164
             tm, from, primary ? " *" : "", info);
1165
  if (d->verbose)
1166
    rta_show(c, a, tmpa);
1167
}
1168

    
1169
static void
1170
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
1171
{
1172
  rte *e, *ee;
1173
  byte ia[STD_ADDRESS_P_LENGTH+8];
1174
  int ok;
1175

    
1176
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
1177
  if (n->routes)
1178
    d->net_counter++;
1179
  for(e=n->routes; e; e=e->next)
1180
    {
1181
      struct ea_list *tmpa, *old_tmpa;
1182
      struct proto *p0 = e->attrs->proto;
1183
      struct proto *p1 = d->export_protocol;
1184
      struct proto *p2 = d->show_protocol;
1185
      d->rt_counter++;
1186
      ee = e;
1187
      rte_update_lock();                /* We use the update buffer for filtering */
1188
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
1189
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1190
      if (p2 && p2 != p0) ok = 0;
1191
      if (ok && d->export_mode)
1192
        {
1193
          int class = ipa_classify(n->n.prefix);
1194
          int ic;
1195
          if ((class & IADDR_SCOPE_MASK) < p1->min_scope)
1196
            ok = 0;
1197
          else if ((ic = p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0) < 0)
1198
            ok = 0;
1199
          else if (!ic && d->export_mode > 1)
1200
            {
1201
              /* FIXME - this shows what should be exported according
1202
                 to current filters, but not what was really exported.
1203
                 'configure soft' command may change the export filter
1204
                 and do not update routes */
1205

    
1206
              if ((p1->out_filter == FILTER_REJECT) ||
1207
                  (p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
1208
                ok = 0;
1209
            }
1210
        }
1211
      if (ok)
1212
        {
1213
          d->show_counter++;
1214
          if (d->stats < 2)
1215
            rt_show_rte(c, ia, e, d, tmpa);
1216
          ia[0] = 0;
1217
        }
1218
      if (e != ee)
1219
        rte_free(ee);
1220
      rte_update_unlock();
1221
      if (d->primary_only)
1222
        break;
1223
    }
1224
}
1225

    
1226
static void
1227
rt_show_cont(struct cli *c)
1228
{
1229
  struct rt_show_data *d = c->rover;
1230
#ifdef DEBUGGING
1231
  unsigned max = 4;
1232
#else
1233
  unsigned max = 64;
1234
#endif
1235
  struct fib *fib = &d->table->fib;
1236
  struct fib_iterator *it = &d->fit;
1237

    
1238
  FIB_ITERATE_START(fib, it, f)
1239
    {
1240
      net *n = (net *) f;
1241
      if (d->running_on_config && d->running_on_config != config)
1242
        {
1243
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1244
          goto done;
1245
        }
1246
      if (d->export_protocol &&
1247
          d->export_protocol->core_state != FS_HAPPY &&
1248
          d->export_protocol->core_state != FS_FEEDING)
1249
        {
1250
          cli_printf(c, 8005, "Protocol is down");
1251
          goto done;
1252
        }
1253
      if (!max--)
1254
        {
1255
          FIB_ITERATE_PUT(it, f);
1256
          return;
1257
        }
1258
      rt_show_net(c, n, d);
1259
    }
1260
  FIB_ITERATE_END(f);
1261
  if (d->stats)
1262
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1263
  else
1264
    cli_printf(c, 0, "");
1265
done:
1266
  c->cont = c->cleanup = NULL;
1267
}
1268

    
1269
static void
1270
rt_show_cleanup(struct cli *c)
1271
{
1272
  struct rt_show_data *d = c->rover;
1273

    
1274
  /* Unlink the iterator */
1275
  fit_get(&d->table->fib, &d->fit);
1276
}
1277

    
1278
void
1279
rt_show(struct rt_show_data *d)
1280
{
1281
  net *n;
1282

    
1283
  if (d->pxlen == 256)
1284
    {
1285
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1286
      this_cli->cont = rt_show_cont;
1287
      this_cli->cleanup = rt_show_cleanup;
1288
      this_cli->rover = d;
1289
    }
1290
  else
1291
    {
1292
      if (d->show_for)
1293
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1294
      else
1295
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1296
      if (n)
1297
        {
1298
          rt_show_net(this_cli, n, d);
1299
          cli_msg(0, "");
1300
        }
1301
      else
1302
        cli_msg(8001, "Network not in table");
1303
    }
1304
}
1305

    
1306
/*
1307
 *  Documentation for functions declared inline in route.h
1308
 */
1309
#if 0
1310

1311
/**
1312
 * net_find - find a network entry
1313
 * @tab: a routing table
1314
 * @addr: address of the network
1315
 * @len: length of the network prefix
1316
 *
1317
 * net_find() looks up the given network in routing table @tab and
1318
 * returns a pointer to its &net entry or %NULL if no such network
1319
 * exists.
1320
 */
1321
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1322
{ DUMMY; }
1323

1324
/**
1325
 * net_get - obtain a network entry
1326
 * @tab: a routing table
1327
 * @addr: address of the network
1328
 * @len: length of the network prefix
1329
 *
1330
 * net_get() looks up the given network in routing table @tab and
1331
 * returns a pointer to its &net entry. If no such entry exists, it's
1332
 * created.
1333
 */
1334
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1335
{ DUMMY; }
1336

1337
/**
1338
 * rte_cow - copy a route for writing
1339
 * @r: a route entry to be copied
1340
 *
1341
 * rte_cow() takes a &rte and prepares it for modification. The exact action
1342
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
1343
 * just returned unchanged, else a new temporary entry with the same contents
1344
 * is created.
1345
 *
1346
 * The primary use of this function is inside the filter machinery -- when
1347
 * a filter wants to modify &rte contents (to change the preference or to
1348
 * attach another set of attributes), it must ensure that the &rte is not
1349
 * shared with anyone else (and especially that it isn't stored in any routing
1350
 * table).
1351
 *
1352
 * Result: a pointer to the new writable &rte.
1353
 */
1354
static inline rte * rte_cow(rte *r)
1355
{ DUMMY; }
1356

1357
#endif