Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (32.3 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)
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
  /* This is a tricky part - we don't know whether route 'old' was
203
     exported to protocol 'p' or was filtered by the export filter.
204
     We try tu run the export filter to know this to have a correct
205
     value in 'old' argument of rt_update (and proper filter value)
206

207
     FIXME - this is broken because 'configure soft' may change
208
     filters but keep routes */
209

    
210
  if (old)
211
    {
212
      if (p->out_filter == FILTER_REJECT)
213
        old = NULL;
214
      else
215
        {
216
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
217
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
218
          if (ok < 0 || (!ok && p->out_filter && f_run(p->out_filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
219
            {
220
              if (old != old0)
221
                rte_free(old);
222
              old = NULL;
223
            }
224
        }
225
    }
226

    
227
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
228
  if (!new && !old)
229
    return;
230

    
231
  if (new)
232
    p->stats.exp_updates_accepted++;
233
  else
234
    p->stats.exp_withdraws_accepted++;
235

    
236
  if (new)
237
    p->stats.exp_routes++;
238
  if (old)
239
    p->stats.exp_routes--;
240

    
241
  if (p->debug & D_ROUTES)
242
    {
243
      if (new && old)
244
        rte_trace_out(D_ROUTES, p, new, "replaced");
245
      else if (new)
246
        rte_trace_out(D_ROUTES, p, new, "added");
247
      else if (old)
248
        rte_trace_out(D_ROUTES, p, old, "removed");
249
    }
250
  if (!new)
251
    p->rt_notify(p, net, NULL, old, NULL);
252
  else if (tmpa)
253
    {
254
      ea_list *t = tmpa;
255
      while (t->next)
256
        t = t->next;
257
      t->next = new->attrs->eattrs;
258
      p->rt_notify(p, net, new, old, tmpa);
259
      t->next = NULL;
260
    }
261
  else
262
    p->rt_notify(p, net, new, old, new->attrs->eattrs);
263
  if (new && new != new0)        /* Discard temporary rte's */
264
    rte_free(new);
265
  if (old && old != old0)
266
    rte_free(old);
267
}
268

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

    
304
  if (type == RA_OPTIMAL)
305
    {
306
      if (new)
307
        new->attrs->proto->stats.pref_routes++;
308
      if (old)
309
        old->attrs->proto->stats.pref_routes--;
310
    }
311

    
312
  WALK_LIST(a, tab->hooks)
313
    {
314
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
315
      if (a->proto->accept_ra_types == type)
316
        do_rte_announce(a, type, net, new, old, tmpa, class);
317
    }
318
}
319

    
320
static inline int
321
rte_validate(rte *e)
322
{
323
  int c;
324
  net *n = e->net;
325

    
326
  if (ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))))
327
    {
328
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
329
          n->n.prefix, n->n.pxlen, e->sender->name);
330
      return 0;
331
    }
332
  if (n->n.pxlen)
333
    {
334
      c = ipa_classify(n->n.prefix);
335
      if (c < 0 || !(c & IADDR_HOST))
336
        {
337
          if (!ipa_nonzero(n->n.prefix))
338
            {
339
              /* Various default routes */
340
#ifdef IPV6
341
              if (n->n.pxlen == 96)
342
#else
343
              if (n->n.pxlen <= 1)
344
#endif
345
                return 1;
346
            }
347
          log(L_WARN "Ignoring bogus route %I/%d received via %s",
348
              n->n.prefix, n->n.pxlen, e->sender->name);
349
          return 0;
350
        }
351
      if ((c & IADDR_SCOPE_MASK) < e->sender->min_scope)
352
        {
353
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
354
              ip_scope_text(c & IADDR_SCOPE_MASK),
355
              n->n.prefix, n->n.pxlen, e->attrs->from, e->sender->name);
356
          return 0;
357
        }
358
    }
359
  return 1;
360
}
361

    
362
/**
363
 * rte_free - delete a &rte
364
 * @e: &rte to be deleted
365
 *
366
 * rte_free() deletes the given &rte from the routing table it's linked to.
367
 */
368
void
369
rte_free(rte *e)
370
{
371
  if (e->attrs->aflags & RTAF_CACHED)
372
    rta_free(e->attrs);
373
  sl_free(rte_slab, e);
374
}
375

    
376
static inline void
377
rte_free_quick(rte *e)
378
{
379
  rta_free(e->attrs);
380
  sl_free(rte_slab, e);
381
}
382

    
383
static int
384
rte_same(rte *x, rte *y)
385
{
386
  return
387
    x->attrs == y->attrs &&
388
    x->flags == y->flags &&
389
    x->pflags == y->pflags &&
390
    x->pref == y->pref &&
391
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
392
}
393

    
394
static void
395
rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
396
{
397
  rte *old_best = net->routes;
398
  rte *old = NULL;
399
  rte **k, *r, *s;
400

    
401
  k = &net->routes;                        /* Find and remove original route from the same protocol */
402
  while (old = *k)
403
    {
404
      if (old->attrs->proto == src)
405
        {
406
          if (new && rte_same(old, new))
407
            {
408
              /* No changes, ignore the new route */
409
              p->stats.imp_updates_ignored++;
410
              rte_trace_in(D_ROUTES, p, new, "ignored");
411
              rte_free_quick(new);
412
              old->lastmod = now;
413
              return;
414
            }
415
          *k = old->next;
416
          break;
417
        }
418
      k = &old->next;
419
    }
420

    
421
  if (!old && !new)
422
    {
423
      p->stats.imp_withdraws_ignored++;
424
      return;
425
    }
426

    
427
  if (new)
428
    p->stats.imp_updates_accepted++;
429
  else
430
    p->stats.imp_withdraws_accepted++;
431

    
432
  if (new)
433
    p->stats.imp_routes++;
434
  if (old)
435
    p->stats.imp_routes--;
436

    
437
  rte_announce(table, RA_ANY, net, new, old, tmpa);
438

    
439
  
440
  if (new && rte_better(new, old_best))
441
    {
442
      /* The first case - the new route is cleary optimal, we link it
443
         at the first position and announce it */
444

    
445
      rte_trace_in(D_ROUTES, p, new, "added [best]");
446
      rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
447
      new->next = net->routes;
448
      net->routes = new;
449
    }
450
  else if (old == old_best)
451
    {
452
      /* The second case - the old best route disappeared, we add the
453
         new route (if we have any) to the list (we don't care about
454
         position) and then we elect the new optimal route and relink
455
         that route at the first position and announce it. New optimal
456
         route might be NULL if there is no more routes */
457

    
458
      /* Add the new route to the list */
459
      if (new)
460
        {
461
          rte_trace_in(D_ROUTES, p, new, "added");
462
          new->next = net->routes;
463
          net->routes = new;
464
        }
465

    
466
      /* Find new optimal route */
467
      r = NULL;
468
      for (s=net->routes; s; s=s->next)
469
        if (rte_better(s, r))
470
          r = s;
471

    
472
      /* Announce optimal route */
473
      rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
474

    
475
      /* And relink it (if there is any) */
476
      if (r)
477
        {
478
          k = &net->routes;
479
          while (s = *k)
480
            {
481
              if (s == r)
482
                {
483
                  *k = r->next;
484
                  break;
485
                }
486
              k = &s->next;
487
            }
488
          r->next = net->routes;
489
          net->routes = r;
490
        }
491
      else if (table->gc_counter++ >= table->config->gc_max_ops &&
492
               table->gc_time + table->config->gc_min_time <= now)
493
        ev_schedule(table->gc_event);
494
    }
495
  else if (new)
496
    {
497
      /* The third case - the new route is not better than the old
498
         best route (therefore old_best != NULL) and the old best
499
         route was not removed (therefore old_best == net->routes).
500
         We just link the new route after the old best route. */
501

    
502
      ASSERT(net->routes != NULL);
503
      new->next = net->routes->next;
504
      net->routes->next = new;
505
      rte_trace_in(D_ROUTES, p, new, "added");
506
    }
507
  else if (old && (p->debug & D_ROUTES))
508
    {
509
      /* Not really a case - the list of routes is correct, we just
510
         log the route removal */
511

    
512
      if (old != old_best)
513
        rte_trace_in(D_ROUTES, p, old, "removed");
514
      else if (net->routes)
515
        rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
516
      else
517
        rte_trace_in(D_ROUTES, p, old, "removed [sole]");
518
    }
519

    
520
  if (old)
521
    {
522
      if (p->rte_remove)
523
        p->rte_remove(net, old);
524
      rte_free_quick(old);
525
    }
526
  if (new)
527
    {
528
      new->lastmod = now;
529
      if (p->rte_insert)
530
        p->rte_insert(net, new);
531
    }
532
}
533

    
534
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
535

    
536
static inline void
537
rte_update_lock(void)
538
{
539
  rte_update_nest_cnt++;
540
}
541

    
542
static inline void
543
rte_update_unlock(void)
544
{
545
  if (!--rte_update_nest_cnt)
546
    lp_flush(rte_update_pool);
547
}
548

    
549
/**
550
 * rte_update - enter a new update to a routing table
551
 * @table: table to be updated
552
 * @net: network node
553
 * @p: protocol submitting the update
554
 * @src: protocol originating the update
555
 * @new: a &rte representing the new route or %NULL for route removal.
556
 *
557
 * This function is called by the routing protocols whenever they discover
558
 * a new route or wish to update/remove an existing route. The right announcement
559
 * sequence is to build route attributes first (either un-cached with @aflags set
560
 * to zero or a cached one using rta_lookup(); in this case please note that
561
 * you need to increase the use count of the attributes yourself by calling
562
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
563
 * the appropriate data and finally submit the new &rte by calling rte_update().
564
 *
565
 * @src specifies the protocol that originally created the route and the meaning
566
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
567
 * same value as @new->attrs->proto. @p specifies the protocol that called
568
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
569
 * stores @p in @new->sender;
570
 *
571
 * When rte_update() gets any route, it automatically validates it (checks,
572
 * whether the network and next hop address are valid IP addresses and also
573
 * whether a normal routing protocol doesn't try to smuggle a host or link
574
 * scope route to the table), converts all protocol dependent attributes stored
575
 * in the &rte to temporary extended attributes, consults import filters of the
576
 * protocol to see if the route should be accepted and/or its attributes modified,
577
 * stores the temporary attributes back to the &rte.
578
 *
579
 * Now, having a "public" version of the route, we
580
 * automatically find any old route defined by the protocol @src
581
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
582
 * recalculate the optimal route for this destination and finally broadcast
583
 * the change (if any) to all routing protocols by calling rte_announce().
584
 *
585
 * All memory used for attribute lists and other temporary allocations is taken
586
 * from a special linear pool @rte_update_pool and freed when rte_update()
587
 * finishes.
588
 */
589

    
590
void
591
rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
592
{
593
  ea_list *tmpa = NULL;
594

    
595
  rte_update_lock();
596
  if (new)
597
    {
598
      new->sender = p;
599
      struct filter *filter = p->in_filter;
600

    
601
        /* Do not filter routes going to the secondary side of the pipe, 
602
           that should only go through export filter.
603
           FIXME Make a better check whether p is really a pipe. */
604
      if (p->table != table)
605
        filter = FILTER_ACCEPT;
606

    
607
      p->stats.imp_updates_received++;
608
      if (!rte_validate(new))
609
        {
610
          rte_trace_in(D_FILTERS, p, new, "invalid");
611
          p->stats.imp_updates_invalid++;
612
          goto drop;
613
        }
614
      if (filter == FILTER_REJECT)
615
        {
616
          p->stats.imp_updates_filtered++;
617
          rte_trace_in(D_FILTERS, p, new, "filtered out");
618
          goto drop;
619
        }
620
      if (src->make_tmp_attrs)
621
        tmpa = src->make_tmp_attrs(new, rte_update_pool);
622
      if (filter)
623
        {
624
          ea_list *old_tmpa = tmpa;
625
          int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
626
          if (fr > F_ACCEPT)
627
            {
628
              p->stats.imp_updates_filtered++;
629
              rte_trace_in(D_FILTERS, p, new, "filtered out");
630
              goto drop;
631
            }
632
          if (tmpa != old_tmpa && src->store_tmp_attrs)
633
            src->store_tmp_attrs(new, tmpa);
634
        }
635
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
636
        new->attrs = rta_lookup(new->attrs);
637
      new->flags |= REF_COW;
638
    }
639
  else
640
    p->stats.imp_withdraws_received++;
641

    
642
  rte_recalculate(table, net, p, src, new, tmpa);
643
  rte_update_unlock();
644
  return;
645

    
646
drop:
647
  rte_free(new);
648
  rte_recalculate(table, net, p, src, NULL, NULL);
649
  rte_update_unlock();
650
}
651

    
652
void
653
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
654
{
655
  rte_update_lock();
656
  rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
657
  rte_update_unlock();
658
}
659

    
660
/**
661
 * rte_dump - dump a route
662
 * @e: &rte to be dumped
663
 *
664
 * This functions dumps contents of a &rte to debug output.
665
 */
666
void
667
rte_dump(rte *e)
668
{
669
  net *n = e->net;
670
  if (n)
671
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
672
  else
673
    debug("??? ");
674
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
675
  rta_dump(e->attrs);
676
  if (e->attrs->proto->proto->dump_attrs)
677
    e->attrs->proto->proto->dump_attrs(e);
678
  debug("\n");
679
}
680

    
681
/**
682
 * rt_dump - dump a routing table
683
 * @t: routing table to be dumped
684
 *
685
 * This function dumps contents of a given routing table to debug output.
686
 */
687
void
688
rt_dump(rtable *t)
689
{
690
  rte *e;
691
  net *n;
692
  struct announce_hook *a;
693

    
694
  debug("Dump of routing table <%s>\n", t->name);
695
#ifdef DEBUGGING
696
  fib_check(&t->fib);
697
#endif
698
  FIB_WALK(&t->fib, fn)
699
    {
700
      n = (net *) fn;
701
      for(e=n->routes; e; e=e->next)
702
        rte_dump(e);
703
    }
704
  FIB_WALK_END;
705
  WALK_LIST(a, t->hooks)
706
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
707
  debug("\n");
708
}
709

    
710
/**
711
 * rt_dump_all - dump all routing tables
712
 *
713
 * This function dumps contents of all routing tables to debug output.
714
 */
715
void
716
rt_dump_all(void)
717
{
718
  rtable *t;
719

    
720
  WALK_LIST(t, routing_tables)
721
    rt_dump(t);
722
}
723

    
724
static void
725
rt_gc(void *tab)
726
{
727
  rtable *t = tab;
728

    
729
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
730
      t->name, (int)(now - t->gc_time), t->gc_counter);
731
  rt_prune(t);
732
}
733

    
734
void
735
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
736
{
737
  bzero(t, sizeof(*t));
738
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
739
  t->name = name;
740
  t->config = cf;
741
  init_list(&t->hooks);
742
  if (cf)
743
    {
744
      t->gc_event = ev_new(p);
745
      t->gc_event->hook = rt_gc;
746
      t->gc_event->data = t;
747
      t->gc_time = now;
748
    }
749
}
750

    
751
/**
752
 * rt_init - initialize routing tables
753
 *
754
 * This function is called during BIRD startup. It initializes the
755
 * routing table module.
756
 */
757
void
758
rt_init(void)
759
{
760
  rta_init();
761
  rt_table_pool = rp_new(&root_pool, "Routing tables");
762
  rte_update_pool = lp_new(rt_table_pool, 4080);
763
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
764
  init_list(&routing_tables);
765
}
766

    
767
/**
768
 * rt_prune - prune a routing table
769
 * @tab: routing table to be pruned
770
 *
771
 * This function is called whenever a protocol shuts down. It scans
772
 * the routing table and removes all routes belonging to inactive
773
 * protocols and also stale network entries.
774
 */
775
void
776
rt_prune(rtable *tab)
777
{
778
  struct fib_iterator fit;
779
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
780

    
781
  DBG("Pruning route table %s\n", tab->name);
782
#ifdef DEBUGGING
783
  fib_check(&tab->fib);
784
#endif
785
  FIB_ITERATE_INIT(&fit, &tab->fib);
786
again:
787
  FIB_ITERATE_START(&tab->fib, &fit, f)
788
    {
789
      net *n = (net *) f;
790
      rte *e;
791
      ncnt++;
792
    rescan:
793
      for (e=n->routes; e; e=e->next, rcnt++)
794
        if (e->sender->core_state != FS_HAPPY &&
795
            e->sender->core_state != FS_FEEDING)
796
          {
797
            rte_discard(tab, e);
798
            rdel++;
799
            goto rescan;
800
          }
801
      if (!n->routes)                /* Orphaned FIB entry? */
802
        {
803
          FIB_ITERATE_PUT(&fit, f);
804
          fib_delete(&tab->fib, f);
805
          ndel++;
806
          goto again;
807
        }
808
    }
809
  FIB_ITERATE_END(f);
810
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
811
#ifdef DEBUGGING
812
  fib_check(&tab->fib);
813
#endif
814
  tab->gc_counter = 0;
815
  tab->gc_time = now;
816
}
817

    
818
/**
819
 * rt_prune_all - prune all routing tables
820
 *
821
 * This function calls rt_prune() for all known routing tables.
822
 */
823
void
824
rt_prune_all(void)
825
{
826
  rtable *t;
827

    
828
  WALK_LIST(t, routing_tables)
829
    rt_prune(t);
830
}
831

    
832
struct rtable_config *
833
rt_new_table(struct symbol *s)
834
{
835
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
836

    
837
  cf_define_symbol(s, SYM_TABLE, c);
838
  c->name = s->name;
839
  add_tail(&new_config->tables, &c->n);
840
  c->gc_max_ops = 1000;
841
  c->gc_min_time = 5;
842
  return c;
843
}
844

    
845
void
846
rt_preconfig(struct config *c)
847
{
848
  struct symbol *s = cf_find_symbol("master");
849

    
850
  init_list(&c->tables);
851
  c->master_rtc = rt_new_table(s);
852
}
853

    
854
/**
855
 * rt_lock_table - lock a routing table
856
 * @r: routing table to be locked
857
 *
858
 * Lock a routing table, because it's in use by a protocol,
859
 * preventing it from being freed when it gets undefined in a new
860
 * configuration.
861
 */
862
void
863
rt_lock_table(rtable *r)
864
{
865
  r->use_count++;
866
}
867

    
868
/**
869
 * rt_unlock_table - unlock a routing table
870
 * @r: routing table to be unlocked
871
 *
872
 * Unlock a routing table formerly locked by rt_lock_table(),
873
 * that is decrease its use count and delete it if it's scheduled
874
 * for deletion by configuration changes.
875
 */
876
void
877
rt_unlock_table(rtable *r)
878
{
879
  if (!--r->use_count && r->deleted)
880
    {
881
      struct config *conf = r->deleted;
882
      DBG("Deleting routing table %s\n", r->name);
883
      rem_node(&r->n);
884
      fib_free(&r->fib);
885
      mb_free(r);
886
      config_del_obstacle(conf);
887
    }
888
}
889

    
890
/**
891
 * rt_commit - commit new routing table configuration
892
 * @new: new configuration
893
 * @old: original configuration or %NULL if it's boot time config
894
 *
895
 * Scan differences between @old and @new configuration and modify
896
 * the routing tables according to these changes. If @new defines a
897
 * previously unknown table, create it, if it omits a table existing
898
 * in @old, schedule it for deletion (it gets deleted when all protocols
899
 * disconnect from it by calling rt_unlock_table()), if it exists
900
 * in both configurations, leave it unchanged.
901
 */
902
void
903
rt_commit(struct config *new, struct config *old)
904
{
905
  struct rtable_config *o, *r;
906

    
907
  DBG("rt_commit:\n");
908
  if (old)
909
    {
910
      WALK_LIST(o, old->tables)
911
        {
912
          rtable *ot = o->table;
913
          if (!ot->deleted)
914
            {
915
              struct symbol *sym = cf_find_symbol(o->name);
916
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
917
                {
918
                  DBG("\t%s: same\n", o->name);
919
                  r = sym->def;
920
                  r->table = ot;
921
                  ot->name = r->name;
922
                  ot->config = r;
923
                }
924
              else
925
                {
926
                  DBG("\t%s: deleted\n", o->name);
927
                  ot->deleted = old;
928
                  config_add_obstacle(old);
929
                  rt_lock_table(ot);
930
                  rt_unlock_table(ot);
931
                }
932
            }
933
        }
934
    }
935

    
936
  WALK_LIST(r, new->tables)
937
    if (!r->table)
938
      {
939
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
940
        DBG("\t%s: created\n", r->name);
941
        rt_setup(rt_table_pool, t, r->name, r);
942
        add_tail(&routing_tables, &t->n);
943
        r->table = t;
944
      }
945
  DBG("\tdone\n");
946
}
947

    
948
static inline void
949
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
950
{
951
  struct proto *q = e->attrs->proto;
952
  ea_list *tmpa;
953

    
954
  rte_update_lock();
955
  tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
956
  do_rte_announce(h, type, n, e, NULL, tmpa, ipa_classify(n->n.prefix));
957
  rte_update_unlock();
958
}
959

    
960
/**
961
 * rt_feed_baby - advertise routes to a new protocol
962
 * @p: protocol to be fed
963
 *
964
 * This function performs one pass of advertisement of routes to a newly
965
 * initialized protocol. It's called by the protocol code as long as it
966
 * has something to do. (We avoid transferring all the routes in single
967
 * pass in order not to monopolize CPU time.)
968
 */
969
int
970
rt_feed_baby(struct proto *p)
971
{
972
  struct announce_hook *h;
973
  struct fib_iterator *fit;
974
  int max_feed = 256;
975

    
976
  if (!p->feed_ahook)                        /* Need to initialize first */
977
    {
978
      if (!p->ahooks)
979
        return 1;
980
      DBG("Announcing routes to new protocol %s\n", p->name);
981
      p->feed_ahook = p->ahooks;
982
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
983
      goto next_hook;
984
    }
985
  fit = p->feed_iterator;
986

    
987
again:
988
  h = p->feed_ahook;
989
  FIB_ITERATE_START(&h->table->fib, fit, fn)
990
    {
991
      net *n = (net *) fn;
992
      rte *e = n->routes;
993
      if (max_feed <= 0)
994
        {
995
          FIB_ITERATE_PUT(fit, fn);
996
          return 0;
997
        }
998

    
999
      if (p->accept_ra_types == RA_OPTIMAL)
1000
        if (e)
1001
          {
1002
            if (p->core_state != FS_FEEDING)
1003
              return 1;  /* In the meantime, the protocol fell down. */
1004
            do_feed_baby(p, RA_OPTIMAL, h, n, e);
1005
            max_feed--;
1006
          }
1007

    
1008
      if (p->accept_ra_types == RA_ANY)
1009
        for(e = n->routes; e != NULL; e = e->next)
1010
          {
1011
            if (p->core_state != FS_FEEDING)
1012
              return 1;  /* In the meantime, the protocol fell down. */
1013
            do_feed_baby(p, RA_ANY, h, n, e);
1014
            max_feed--;
1015
          }
1016
    }
1017
  FIB_ITERATE_END(fn);
1018
  p->feed_ahook = h->next;
1019
  if (!p->feed_ahook)
1020
    {
1021
      mb_free(p->feed_iterator);
1022
      p->feed_iterator = NULL;
1023
      return 1;
1024
    }
1025

    
1026
next_hook:
1027
  h = p->feed_ahook;
1028
  FIB_ITERATE_INIT(fit, &h->table->fib);
1029
  goto again;
1030
}
1031

    
1032
/**
1033
 * rt_feed_baby_abort - abort protocol feeding
1034
 * @p: protocol
1035
 *
1036
 * This function is called by the protocol code when the protocol
1037
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1038
 * has finished.
1039
 */
1040
void
1041
rt_feed_baby_abort(struct proto *p)
1042
{
1043
  if (p->feed_ahook)
1044
    {
1045
      /* Unlink the iterator and exit */
1046
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1047
      p->feed_ahook = NULL;
1048
    }
1049
}
1050

    
1051
/*
1052
 *  CLI commands
1053
 */
1054

    
1055
static void
1056
rt_format_via(rte *e, byte *via)
1057
{
1058
  rta *a = e->attrs;
1059

    
1060
  switch (a->dest)
1061
    {
1062
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
1063
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
1064
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
1065
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
1066
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
1067
    default:                bsprintf(via, "???");
1068
    }
1069
}
1070

    
1071
static void
1072
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1073
{
1074
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
1075
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
1076
  rta *a = e->attrs;
1077

    
1078
  rt_format_via(e, via);
1079
  tm_format_reltime(tm, e->lastmod);
1080
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
1081
    bsprintf(from, " from %I", a->from);
1082
  else
1083
    from[0] = 0;
1084
  if (a->proto->proto->get_route_info || d->verbose)
1085
    {
1086
      /* Need to normalize the extended attributes */
1087
      ea_list *t = tmpa;
1088
      t = ea_append(t, a->eattrs);
1089
      tmpa = alloca(ea_scan(t));
1090
      ea_merge(t, tmpa);
1091
      ea_sort(tmpa);
1092
    }
1093
  if (a->proto->proto->get_route_info)
1094
    a->proto->proto->get_route_info(e, info, tmpa);
1095
  else
1096
    bsprintf(info, " (%d)", e->pref);
1097
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
1098
  if (d->verbose)
1099
    rta_show(c, a, tmpa);
1100
}
1101

    
1102
static void
1103
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
1104
{
1105
  rte *e, *ee;
1106
  byte ia[STD_ADDRESS_P_LENGTH+8];
1107
  int ok;
1108

    
1109
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
1110
  if (n->routes)
1111
    d->net_counter++;
1112
  for(e=n->routes; e; e=e->next)
1113
    {
1114
      struct ea_list *tmpa, *old_tmpa;
1115
      struct proto *p0 = e->attrs->proto;
1116
      struct proto *p1 = d->export_protocol;
1117
      struct proto *p2 = d->show_protocol;
1118
      d->rt_counter++;
1119
      ee = e;
1120
      rte_update_lock();                /* We use the update buffer for filtering */
1121
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
1122
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1123
      if (p2 && p2 != p0) ok = 0;
1124
      if (ok && d->export_mode)
1125
        {
1126
          int class = ipa_classify(n->n.prefix);
1127
          int ic;
1128
          if ((class & IADDR_SCOPE_MASK) < p1->min_scope)
1129
            ok = 0;
1130
          else if ((ic = p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0) < 0)
1131
            ok = 0;
1132
          else if (!ic && d->export_mode > 1)
1133
            {
1134
              /* FIXME - this shows what should be exported according
1135
                 to current filters, but not what was really exported.
1136
                 'configure soft' command may change the export filter
1137
                 and do not update routes */
1138

    
1139
              if (p1->out_filter == FILTER_REJECT ||
1140
                  p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
1141
                ok = 0;
1142
            }
1143
        }
1144
      if (ok)
1145
        {
1146
          d->show_counter++;
1147
          if (d->stats < 2)
1148
            rt_show_rte(c, ia, e, d, tmpa);
1149
          ia[0] = 0;
1150
        }
1151
      if (e != ee)
1152
        rte_free(ee);
1153
      rte_update_unlock();
1154
      if (d->primary_only)
1155
        break;
1156
    }
1157
}
1158

    
1159
static void
1160
rt_show_cont(struct cli *c)
1161
{
1162
  struct rt_show_data *d = c->rover;
1163
#ifdef DEBUGGING
1164
  unsigned max = 4;
1165
#else
1166
  unsigned max = 64;
1167
#endif
1168
  struct fib *fib = &d->table->fib;
1169
  struct fib_iterator *it = &d->fit;
1170

    
1171
  FIB_ITERATE_START(fib, it, f)
1172
    {
1173
      net *n = (net *) f;
1174
      if (d->running_on_config && d->running_on_config != config)
1175
        {
1176
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1177
          goto done;
1178
        }
1179
      if (d->export_protocol &&
1180
          d->export_protocol->core_state != FS_HAPPY &&
1181
          d->export_protocol->core_state != FS_FEEDING)
1182
        {
1183
          cli_printf(c, 8005, "Protocol is down");
1184
          goto done;
1185
        }
1186
      if (!max--)
1187
        {
1188
          FIB_ITERATE_PUT(it, f);
1189
          return;
1190
        }
1191
      rt_show_net(c, n, d);
1192
    }
1193
  FIB_ITERATE_END(f);
1194
  if (d->stats)
1195
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1196
  else
1197
    cli_printf(c, 0, "");
1198
done:
1199
  c->cont = c->cleanup = NULL;
1200
}
1201

    
1202
static void
1203
rt_show_cleanup(struct cli *c)
1204
{
1205
  struct rt_show_data *d = c->rover;
1206

    
1207
  /* Unlink the iterator */
1208
  fit_get(&d->table->fib, &d->fit);
1209
}
1210

    
1211
void
1212
rt_show(struct rt_show_data *d)
1213
{
1214
  net *n;
1215

    
1216
  if (d->pxlen == 256)
1217
    {
1218
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1219
      this_cli->cont = rt_show_cont;
1220
      this_cli->cleanup = rt_show_cleanup;
1221
      this_cli->rover = d;
1222
    }
1223
  else
1224
    {
1225
      if (d->show_for)
1226
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1227
      else
1228
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1229
      if (n)
1230
        {
1231
          rt_show_net(this_cli, n, d);
1232
          cli_msg(0, "");
1233
        }
1234
      else
1235
        cli_msg(8001, "Network not in table");
1236
    }
1237
}
1238

    
1239
/*
1240
 *  Documentation for functions declared inline in route.h
1241
 */
1242
#if 0
1243

1244
/**
1245
 * net_find - find a network entry
1246
 * @tab: a routing table
1247
 * @addr: address of the network
1248
 * @len: length of the network prefix
1249
 *
1250
 * net_find() looks up the given network in routing table @tab and
1251
 * returns a pointer to its &net entry or %NULL if no such network
1252
 * exists.
1253
 */
1254
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1255
{ DUMMY; }
1256

1257
/**
1258
 * net_get - obtain a network entry
1259
 * @tab: a routing table
1260
 * @addr: address of the network
1261
 * @len: length of the network prefix
1262
 *
1263
 * net_get() looks up the given network in routing table @tab and
1264
 * returns a pointer to its &net entry. If no such entry exists, it's
1265
 * created.
1266
 */
1267
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1268
{ DUMMY; }
1269

1270
/**
1271
 * rte_cow - copy a route for writing
1272
 * @r: a route entry to be copied
1273
 *
1274
 * rte_cow() takes a &rte and prepares it for modification. The exact action
1275
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
1276
 * just returned unchanged, else a new temporary entry with the same contents
1277
 * is created.
1278
 *
1279
 * The primary use of this function is inside the filter machinery -- when
1280
 * a filter wants to modify &rte contents (to change the preference or to
1281
 * attach another set of attributes), it must ensure that the &rte is not
1282
 * shared with anyone else (and especially that it isn't stored in any routing
1283
 * table).
1284
 *
1285
 * Result: a pointer to the new writable &rte.
1286
 */
1287
static inline rte * rte_cow(rte *r)
1288
{ DUMMY; }
1289

1290
#endif