Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 11361a10

History | View | Annotate | Download (33.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, 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
  if (new)
169
    {
170
      p->stats.exp_updates_received++;
171

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

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

    
222
  if (old && !refeed)
223
    {
224
      if (p->out_filter == FILTER_REJECT)
225
        old = NULL;
226
      else
227
        {
228
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
229
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
230
          if (ok < 0 || (!ok && p->out_filter && f_run(p->out_filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
231
            {
232
              if (old != old0)
233
                rte_free(old);
234
              old = NULL;
235
            }
236
        }
237
    }
238

    
239
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
240
  if (!new && !old)
241
    return;
242

    
243
  if (new)
244
    p->stats.exp_updates_accepted++;
245
  else
246
    p->stats.exp_withdraws_accepted++;
247

    
248
  if (new)
249
    p->stats.exp_routes++;
250
  if (old)
251
    p->stats.exp_routes--;
252

    
253
  if (p->debug & D_ROUTES)
254
    {
255
      if (new && old)
256
        rte_trace_out(D_ROUTES, p, new, "replaced");
257
      else if (new)
258
        rte_trace_out(D_ROUTES, p, new, "added");
259
      else if (old)
260
        rte_trace_out(D_ROUTES, p, old, "removed");
261
    }
262
  if (!new)
263
    p->rt_notify(p, net, NULL, old, NULL);
264
  else if (tmpa)
265
    {
266
      ea_list *t = tmpa;
267
      while (t->next)
268
        t = t->next;
269
      t->next = new->attrs->eattrs;
270
      p->rt_notify(p, net, new, old, tmpa);
271
      t->next = NULL;
272
    }
273
  else
274
    p->rt_notify(p, net, new, old, new->attrs->eattrs);
275
  if (new && new != new0)        /* Discard temporary rte's */
276
    rte_free(new);
277
  if (old && old != old0)
278
    rte_free(old);
279
}
280

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

    
316
  if (type == RA_OPTIMAL)
317
    {
318
      if (new)
319
        new->attrs->proto->stats.pref_routes++;
320
      if (old)
321
        old->attrs->proto->stats.pref_routes--;
322
    }
323

    
324
  WALK_LIST(a, tab->hooks)
325
    {
326
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
327
      if (a->proto->accept_ra_types == type)
328
        do_rte_announce(a, type, net, new, old, tmpa, class, 0);
329
    }
330
}
331

    
332
static inline int
333
rte_validate(rte *e)
334
{
335
  int c;
336
  net *n = e->net;
337

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

    
374
/**
375
 * rte_free - delete a &rte
376
 * @e: &rte to be deleted
377
 *
378
 * rte_free() deletes the given &rte from the routing table it's linked to.
379
 */
380
void
381
rte_free(rte *e)
382
{
383
  if (e->attrs->aflags & RTAF_CACHED)
384
    rta_free(e->attrs);
385
  sl_free(rte_slab, e);
386
}
387

    
388
static inline void
389
rte_free_quick(rte *e)
390
{
391
  rta_free(e->attrs);
392
  sl_free(rte_slab, e);
393
}
394

    
395
static int
396
rte_same(rte *x, rte *y)
397
{
398
  return
399
    x->attrs == y->attrs &&
400
    x->flags == y->flags &&
401
    x->pflags == y->pflags &&
402
    x->pref == y->pref &&
403
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
404
}
405

    
406
static void
407
rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
408
{
409
  rte *old_best = net->routes;
410
  rte *old = NULL;
411
  rte **k, *r, *s;
412

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

    
438
          if (new && rte_same(old, new))
439
            {
440
              /* No changes, ignore the new route */
441
              p->stats.imp_updates_ignored++;
442
              rte_trace_in(D_ROUTES, p, new, "ignored");
443
              rte_free_quick(new);
444
              old->lastmod = now;
445
              return;
446
            }
447
          *k = old->next;
448
          break;
449
        }
450
      k = &old->next;
451
    }
452

    
453
  if (!old && !new)
454
    {
455
      p->stats.imp_withdraws_ignored++;
456
      return;
457
    }
458

    
459
  if (new)
460
    p->stats.imp_updates_accepted++;
461
  else
462
    p->stats.imp_withdraws_accepted++;
463

    
464
  if (new)
465
    p->stats.imp_routes++;
466
  if (old)
467
    p->stats.imp_routes--;
468

    
469
  rte_announce(table, RA_ANY, net, new, old, tmpa);
470

    
471
  
472
  if (new && rte_better(new, old_best))
473
    {
474
      /* The first case - the new route is cleary optimal, we link it
475
         at the first position and announce it */
476

    
477
      rte_trace_in(D_ROUTES, p, new, "added [best]");
478
      rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
479
      new->next = net->routes;
480
      net->routes = new;
481
    }
482
  else if (old == old_best)
483
    {
484
      /* The second case - the old best route disappeared, we add the
485
         new route (if we have any) to the list (we don't care about
486
         position) and then we elect the new optimal route and relink
487
         that route at the first position and announce it. New optimal
488
         route might be NULL if there is no more routes */
489

    
490
      /* Add the new route to the list */
491
      if (new)
492
        {
493
          rte_trace_in(D_ROUTES, p, new, "added");
494
          new->next = net->routes;
495
          net->routes = new;
496
        }
497

    
498
      /* Find new optimal route */
499
      r = NULL;
500
      for (s=net->routes; s; s=s->next)
501
        if (rte_better(s, r))
502
          r = s;
503

    
504
      /* Announce optimal route */
505
      rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
506

    
507
      /* And relink it (if there is any) */
508
      if (r)
509
        {
510
          k = &net->routes;
511
          while (s = *k)
512
            {
513
              if (s == r)
514
                {
515
                  *k = r->next;
516
                  break;
517
                }
518
              k = &s->next;
519
            }
520
          r->next = net->routes;
521
          net->routes = r;
522
        }
523
      else if (table->gc_counter++ >= table->config->gc_max_ops &&
524
               table->gc_time + table->config->gc_min_time <= now)
525
        ev_schedule(table->gc_event);
526
    }
527
  else if (new)
528
    {
529
      /* The third case - the new route is not better than the old
530
         best route (therefore old_best != NULL) and the old best
531
         route was not removed (therefore old_best == net->routes).
532
         We just link the new route after the old best route. */
533

    
534
      ASSERT(net->routes != NULL);
535
      new->next = net->routes->next;
536
      net->routes->next = new;
537
      rte_trace_in(D_ROUTES, p, new, "added");
538
    }
539

    
540
  /* Log the route removal */
541
  if (!new && old && (p->debug & D_ROUTES))
542
    {
543
      if (old != old_best)
544
        rte_trace_in(D_ROUTES, p, old, "removed");
545
      else if (net->routes)
546
        rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
547
      else
548
        rte_trace_in(D_ROUTES, p, old, "removed [sole]");
549
    }
550

    
551
  if (old)
552
    {
553
      if (p->rte_remove)
554
        p->rte_remove(net, old);
555
      rte_free_quick(old);
556
    }
557
  if (new)
558
    {
559
      new->lastmod = now;
560
      if (p->rte_insert)
561
        p->rte_insert(net, new);
562
    }
563
}
564

    
565
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
566

    
567
static inline void
568
rte_update_lock(void)
569
{
570
  rte_update_nest_cnt++;
571
}
572

    
573
static inline void
574
rte_update_unlock(void)
575
{
576
  if (!--rte_update_nest_cnt)
577
    lp_flush(rte_update_pool);
578
}
579

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

    
621
void
622
rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
623
{
624
  ea_list *tmpa = NULL;
625

    
626
  rte_update_lock();
627
  if (new)
628
    {
629
      new->sender = p;
630
      struct filter *filter = p->in_filter;
631

    
632
      /* Do not filter routes going through the pipe, 
633
         they are filtered in the export filter only. */
634
#ifdef CONFIG_PIPE
635
      if (p->proto == &proto_pipe)
636
        filter = FILTER_ACCEPT;
637
#endif
638

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

    
674
  rte_recalculate(table, net, p, src, new, tmpa);
675
  rte_update_unlock();
676
  return;
677

    
678
drop:
679
  rte_free(new);
680
  rte_recalculate(table, net, p, src, NULL, NULL);
681
  rte_update_unlock();
682
}
683

    
684
void
685
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
686
{
687
  rte_update_lock();
688
  rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
689
  rte_update_unlock();
690
}
691

    
692
/**
693
 * rte_dump - dump a route
694
 * @e: &rte to be dumped
695
 *
696
 * This functions dumps contents of a &rte to debug output.
697
 */
698
void
699
rte_dump(rte *e)
700
{
701
  net *n = e->net;
702
  if (n)
703
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
704
  else
705
    debug("??? ");
706
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
707
  rta_dump(e->attrs);
708
  if (e->attrs->proto->proto->dump_attrs)
709
    e->attrs->proto->proto->dump_attrs(e);
710
  debug("\n");
711
}
712

    
713
/**
714
 * rt_dump - dump a routing table
715
 * @t: routing table to be dumped
716
 *
717
 * This function dumps contents of a given routing table to debug output.
718
 */
719
void
720
rt_dump(rtable *t)
721
{
722
  rte *e;
723
  net *n;
724
  struct announce_hook *a;
725

    
726
  debug("Dump of routing table <%s>\n", t->name);
727
#ifdef DEBUGGING
728
  fib_check(&t->fib);
729
#endif
730
  FIB_WALK(&t->fib, fn)
731
    {
732
      n = (net *) fn;
733
      for(e=n->routes; e; e=e->next)
734
        rte_dump(e);
735
    }
736
  FIB_WALK_END;
737
  WALK_LIST(a, t->hooks)
738
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
739
  debug("\n");
740
}
741

    
742
/**
743
 * rt_dump_all - dump all routing tables
744
 *
745
 * This function dumps contents of all routing tables to debug output.
746
 */
747
void
748
rt_dump_all(void)
749
{
750
  rtable *t;
751

    
752
  WALK_LIST(t, routing_tables)
753
    rt_dump(t);
754
}
755

    
756
static void
757
rt_gc(void *tab)
758
{
759
  rtable *t = tab;
760

    
761
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
762
      t->name, (int)(now - t->gc_time), t->gc_counter);
763
  rt_prune(t);
764
}
765

    
766
void
767
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
768
{
769
  bzero(t, sizeof(*t));
770
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
771
  t->name = name;
772
  t->config = cf;
773
  init_list(&t->hooks);
774
  if (cf)
775
    {
776
      t->gc_event = ev_new(p);
777
      t->gc_event->hook = rt_gc;
778
      t->gc_event->data = t;
779
      t->gc_time = now;
780
    }
781
}
782

    
783
/**
784
 * rt_init - initialize routing tables
785
 *
786
 * This function is called during BIRD startup. It initializes the
787
 * routing table module.
788
 */
789
void
790
rt_init(void)
791
{
792
  rta_init();
793
  rt_table_pool = rp_new(&root_pool, "Routing tables");
794
  rte_update_pool = lp_new(rt_table_pool, 4080);
795
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
796
  init_list(&routing_tables);
797
}
798

    
799
/**
800
 * rt_prune - prune a routing table
801
 * @tab: routing table to be pruned
802
 *
803
 * This function is called whenever a protocol shuts down. It scans
804
 * the routing table and removes all routes belonging to inactive
805
 * protocols and also stale network entries.
806
 */
807
void
808
rt_prune(rtable *tab)
809
{
810
  struct fib_iterator fit;
811
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
812

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

    
850
/**
851
 * rt_prune_all - prune all routing tables
852
 *
853
 * This function calls rt_prune() for all known routing tables.
854
 */
855
void
856
rt_prune_all(void)
857
{
858
  rtable *t;
859

    
860
  WALK_LIST(t, routing_tables)
861
    rt_prune(t);
862
}
863

    
864
struct rtable_config *
865
rt_new_table(struct symbol *s)
866
{
867
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
868

    
869
  cf_define_symbol(s, SYM_TABLE, c);
870
  c->name = s->name;
871
  add_tail(&new_config->tables, &c->n);
872
  c->gc_max_ops = 1000;
873
  c->gc_min_time = 5;
874
  return c;
875
}
876

    
877
void
878
rt_preconfig(struct config *c)
879
{
880
  struct symbol *s = cf_find_symbol("master");
881

    
882
  init_list(&c->tables);
883
  c->master_rtc = rt_new_table(s);
884
}
885

    
886
/**
887
 * rt_lock_table - lock a routing table
888
 * @r: routing table to be locked
889
 *
890
 * Lock a routing table, because it's in use by a protocol,
891
 * preventing it from being freed when it gets undefined in a new
892
 * configuration.
893
 */
894
void
895
rt_lock_table(rtable *r)
896
{
897
  r->use_count++;
898
}
899

    
900
/**
901
 * rt_unlock_table - unlock a routing table
902
 * @r: routing table to be unlocked
903
 *
904
 * Unlock a routing table formerly locked by rt_lock_table(),
905
 * that is decrease its use count and delete it if it's scheduled
906
 * for deletion by configuration changes.
907
 */
908
void
909
rt_unlock_table(rtable *r)
910
{
911
  if (!--r->use_count && r->deleted)
912
    {
913
      struct config *conf = r->deleted;
914
      DBG("Deleting routing table %s\n", r->name);
915
      rem_node(&r->n);
916
      fib_free(&r->fib);
917
      mb_free(r);
918
      config_del_obstacle(conf);
919
    }
920
}
921

    
922
/**
923
 * rt_commit - commit new routing table configuration
924
 * @new: new configuration
925
 * @old: original configuration or %NULL if it's boot time config
926
 *
927
 * Scan differences between @old and @new configuration and modify
928
 * the routing tables according to these changes. If @new defines a
929
 * previously unknown table, create it, if it omits a table existing
930
 * in @old, schedule it for deletion (it gets deleted when all protocols
931
 * disconnect from it by calling rt_unlock_table()), if it exists
932
 * in both configurations, leave it unchanged.
933
 */
934
void
935
rt_commit(struct config *new, struct config *old)
936
{
937
  struct rtable_config *o, *r;
938

    
939
  DBG("rt_commit:\n");
940
  if (old)
941
    {
942
      WALK_LIST(o, old->tables)
943
        {
944
          rtable *ot = o->table;
945
          if (!ot->deleted)
946
            {
947
              struct symbol *sym = cf_find_symbol(o->name);
948
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
949
                {
950
                  DBG("\t%s: same\n", o->name);
951
                  r = sym->def;
952
                  r->table = ot;
953
                  ot->name = r->name;
954
                  ot->config = r;
955
                }
956
              else
957
                {
958
                  DBG("\t%s: deleted\n", o->name);
959
                  ot->deleted = old;
960
                  config_add_obstacle(old);
961
                  rt_lock_table(ot);
962
                  rt_unlock_table(ot);
963
                }
964
            }
965
        }
966
    }
967

    
968
  WALK_LIST(r, new->tables)
969
    if (!r->table)
970
      {
971
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
972
        DBG("\t%s: created\n", r->name);
973
        rt_setup(rt_table_pool, t, r->name, r);
974
        add_tail(&routing_tables, &t->n);
975
        r->table = t;
976
      }
977
  DBG("\tdone\n");
978
}
979

    
980
static inline void
981
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
982
{
983
  struct proto *q = e->attrs->proto;
984
  ea_list *tmpa;
985

    
986
  rte_update_lock();
987
  tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
988
  do_rte_announce(h, type, n, e, p->refeeding ? e : NULL, tmpa, ipa_classify(n->n.prefix), p->refeeding);
989
  rte_update_unlock();
990
}
991

    
992
/**
993
 * rt_feed_baby - advertise routes to a new protocol
994
 * @p: protocol to be fed
995
 *
996
 * This function performs one pass of advertisement of routes to a newly
997
 * initialized protocol. It's called by the protocol code as long as it
998
 * has something to do. (We avoid transferring all the routes in single
999
 * pass in order not to monopolize CPU time.)
1000
 */
1001
int
1002
rt_feed_baby(struct proto *p)
1003
{
1004
  struct announce_hook *h;
1005
  struct fib_iterator *fit;
1006
  int max_feed = 256;
1007

    
1008
  if (!p->feed_ahook)                        /* Need to initialize first */
1009
    {
1010
      if (!p->ahooks)
1011
        return 1;
1012
      DBG("Announcing routes to new protocol %s\n", p->name);
1013
      p->feed_ahook = p->ahooks;
1014
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1015
      goto next_hook;
1016
    }
1017
  fit = p->feed_iterator;
1018

    
1019
again:
1020
  h = p->feed_ahook;
1021
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1022
    {
1023
      net *n = (net *) fn;
1024
      rte *e = n->routes;
1025
      if (max_feed <= 0)
1026
        {
1027
          FIB_ITERATE_PUT(fit, fn);
1028
          return 0;
1029
        }
1030

    
1031
      if (p->accept_ra_types == RA_OPTIMAL)
1032
        if (e)
1033
          {
1034
            if (p->core_state != FS_FEEDING)
1035
              return 1;  /* In the meantime, the protocol fell down. */
1036
            do_feed_baby(p, RA_OPTIMAL, h, n, e);
1037
            max_feed--;
1038
          }
1039

    
1040
      if (p->accept_ra_types == RA_ANY)
1041
        for(e = n->routes; e != NULL; e = e->next)
1042
          {
1043
            if (p->core_state != FS_FEEDING)
1044
              return 1;  /* In the meantime, the protocol fell down. */
1045
            do_feed_baby(p, RA_ANY, h, n, e);
1046
            max_feed--;
1047
          }
1048
    }
1049
  FIB_ITERATE_END(fn);
1050
  p->feed_ahook = h->next;
1051
  if (!p->feed_ahook)
1052
    {
1053
      mb_free(p->feed_iterator);
1054
      p->feed_iterator = NULL;
1055
      return 1;
1056
    }
1057

    
1058
next_hook:
1059
  h = p->feed_ahook;
1060
  FIB_ITERATE_INIT(fit, &h->table->fib);
1061
  goto again;
1062
}
1063

    
1064
/**
1065
 * rt_feed_baby_abort - abort protocol feeding
1066
 * @p: protocol
1067
 *
1068
 * This function is called by the protocol code when the protocol
1069
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1070
 * has finished.
1071
 */
1072
void
1073
rt_feed_baby_abort(struct proto *p)
1074
{
1075
  if (p->feed_ahook)
1076
    {
1077
      /* Unlink the iterator and exit */
1078
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1079
      p->feed_ahook = NULL;
1080
    }
1081
}
1082

    
1083
/*
1084
 *  CLI commands
1085
 */
1086

    
1087
static void
1088
rt_format_via(rte *e, byte *via)
1089
{
1090
  rta *a = e->attrs;
1091

    
1092
  switch (a->dest)
1093
    {
1094
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
1095
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
1096
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
1097
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
1098
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
1099
    default:                bsprintf(via, "???");
1100
    }
1101
}
1102

    
1103
static void
1104
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1105
{
1106
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
1107
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
1108
  rta *a = e->attrs;
1109

    
1110
  rt_format_via(e, via);
1111
  tm_format_reltime(tm, e->lastmod);
1112
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
1113
    bsprintf(from, " from %I", a->from);
1114
  else
1115
    from[0] = 0;
1116
  if (a->proto->proto->get_route_info || d->verbose)
1117
    {
1118
      /* Need to normalize the extended attributes */
1119
      ea_list *t = tmpa;
1120
      t = ea_append(t, a->eattrs);
1121
      tmpa = alloca(ea_scan(t));
1122
      ea_merge(t, tmpa);
1123
      ea_sort(tmpa);
1124
    }
1125
  if (a->proto->proto->get_route_info)
1126
    a->proto->proto->get_route_info(e, info, tmpa);
1127
  else
1128
    bsprintf(info, " (%d)", e->pref);
1129
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
1130
  if (d->verbose)
1131
    rta_show(c, a, tmpa);
1132
}
1133

    
1134
static void
1135
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
1136
{
1137
  rte *e, *ee;
1138
  byte ia[STD_ADDRESS_P_LENGTH+8];
1139
  int ok;
1140

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

    
1171
              if (p1->out_filter == FILTER_REJECT ||
1172
                  p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
1173
                ok = 0;
1174
            }
1175
        }
1176
      if (ok)
1177
        {
1178
          d->show_counter++;
1179
          if (d->stats < 2)
1180
            rt_show_rte(c, ia, e, d, tmpa);
1181
          ia[0] = 0;
1182
        }
1183
      if (e != ee)
1184
        rte_free(ee);
1185
      rte_update_unlock();
1186
      if (d->primary_only)
1187
        break;
1188
    }
1189
}
1190

    
1191
static void
1192
rt_show_cont(struct cli *c)
1193
{
1194
  struct rt_show_data *d = c->rover;
1195
#ifdef DEBUGGING
1196
  unsigned max = 4;
1197
#else
1198
  unsigned max = 64;
1199
#endif
1200
  struct fib *fib = &d->table->fib;
1201
  struct fib_iterator *it = &d->fit;
1202

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

    
1234
static void
1235
rt_show_cleanup(struct cli *c)
1236
{
1237
  struct rt_show_data *d = c->rover;
1238

    
1239
  /* Unlink the iterator */
1240
  fit_get(&d->table->fib, &d->fit);
1241
}
1242

    
1243
void
1244
rt_show(struct rt_show_data *d)
1245
{
1246
  net *n;
1247

    
1248
  if (d->pxlen == 256)
1249
    {
1250
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1251
      this_cli->cont = rt_show_cont;
1252
      this_cli->cleanup = rt_show_cleanup;
1253
      this_cli->rover = d;
1254
    }
1255
  else
1256
    {
1257
      if (d->show_for)
1258
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1259
      else
1260
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1261
      if (n)
1262
        {
1263
          rt_show_net(this_cli, n, d);
1264
          cli_msg(0, "");
1265
        }
1266
      else
1267
        cli_msg(8001, "Network not in table");
1268
    }
1269
}
1270

    
1271
/*
1272
 *  Documentation for functions declared inline in route.h
1273
 */
1274
#if 0
1275

1276
/**
1277
 * net_find - find a network entry
1278
 * @tab: a routing table
1279
 * @addr: address of the network
1280
 * @len: length of the network prefix
1281
 *
1282
 * net_find() looks up the given network in routing table @tab and
1283
 * returns a pointer to its &net entry or %NULL if no such network
1284
 * exists.
1285
 */
1286
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1287
{ DUMMY; }
1288

1289
/**
1290
 * net_get - obtain a network entry
1291
 * @tab: a routing table
1292
 * @addr: address of the network
1293
 * @len: length of the network prefix
1294
 *
1295
 * net_get() looks up the given network in routing table @tab and
1296
 * returns a pointer to its &net entry. If no such entry exists, it's
1297
 * created.
1298
 */
1299
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1300
{ DUMMY; }
1301

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

1322
#endif