Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 13b75bac

History | View | Annotate | Download (27.9 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

    
45
#include <alloca.h>
46

    
47
static slab *rte_slab;
48
static linpool *rte_update_pool;
49

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

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

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

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

    
64
/**
65
 * rte_find - find a route
66
 * @net: network node
67
 * @p: protocol
68
 *
69
 * The rte_find() function returns a route for destination @net
70
 * which belongs has been defined by protocol @p.
71
 */
72
rte *
73
rte_find(net *net, struct proto *p)
74
{
75
  rte *e = net->routes;
76

    
77
  while (e && e->attrs->proto != p)
78
    e = e->next;
79
  return e;
80
}
81

    
82
/**
83
 * rte_get_temp - get a temporary &rte
84
 * @a: attributes to assign to the new route (a &rta; in case it's
85
 * un-cached, rte_update() will create a cached copy automatically)
86
 *
87
 * Create a temporary &rte and bind it with the attributes @a.
88
 * Also set route preference to the default preference set for
89
 * the protocol.
90
 */
91
rte *
92
rte_get_temp(rta *a)
93
{
94
  rte *e = sl_alloc(rte_slab);
95

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

    
102
rte *
103
rte_do_cow(rte *r)
104
{
105
  rte *e = sl_alloc(rte_slab);
106

    
107
  memcpy(e, r, sizeof(rte));
108
  e->attrs = rta_clone(r->attrs);
109
  e->flags = 0;
110
  return e;
111
}
112

    
113
static int                                /* Actually better or at least as good as */
114
rte_better(rte *new, rte *old)
115
{
116
  int (*better)(rte *, rte *);
117

    
118
  if (!old)
119
    return 1;
120
  if (new->pref > old->pref)
121
    return 1;
122
  if (new->pref < old->pref)
123
    return 0;
124
  if (new->attrs->proto->proto != old->attrs->proto->proto)
125
    {
126
      /*
127
       *  If the user has configured protocol preferences, so that two different protocols
128
       *  have the same preference, try to break the tie by comparing addresses. Not too
129
       *  useful, but keeps the ordering of routes unambiguous.
130
       */
131
      return new->attrs->proto->proto > old->attrs->proto->proto;
132
    }
133
  if (better = new->attrs->proto->rte_better)
134
    return better(new, old);
135
  return 0;
136
}
137

    
138
static void
139
rte_trace(struct proto *p, rte *e, int dir, char *msg)
140
{
141
  byte via[STD_ADDRESS_P_LENGTH+32];
142

    
143
  rt_format_via(e, via);
144
  log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
145
}
146

    
147
static inline void
148
rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg)
149
{
150
  if (p->debug & flag)
151
    rte_trace(p, e, '>', msg);
152
}
153

    
154
static inline void
155
rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg)
156
{
157
  if (p->debug & flag)
158
    rte_trace(p, e, '<', msg);
159
}
160

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

    
169
  if (new)
170
    {
171
      char *drop_reason = NULL;
172
      if ((class & IADDR_SCOPE_MASK) < p->min_scope)
173
        drop_reason = "out of scope";
174
      else if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
175
        drop_reason = "rejected by protocol";
176
      else if (ok)
177
        rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
178
      else if (p->out_filter == FILTER_REJECT ||
179
               p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
180
        drop_reason = "filtered out";
181
      if (drop_reason)
182
        {
183
          rte_trace_out(D_FILTERS, p, new, drop_reason);
184
          if (new != new0)
185
            rte_free(new);
186
          new = NULL;
187
        }
188
    }
189
  if (old && p->out_filter)
190
    {
191
      if (p->out_filter == FILTER_REJECT)
192
        old = NULL;
193
      else
194
        {
195
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
196
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
197
          if (ok < 0 || (!ok && f_run(p->out_filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
198
            {
199
              if (old != old0)
200
                rte_free(old);
201
              old = NULL;
202
            }
203
        }
204
    }
205
  if (p->debug & D_ROUTES)
206
    {
207
      if (new && old)
208
        rte_trace_out(D_ROUTES, p, new, "replaced");
209
      else if (new)
210
        rte_trace_out(D_ROUTES, p, new, "added");
211
      else if (old)
212
        rte_trace_out(D_ROUTES, p, old, "removed");
213
    }
214
  if (!new && !old)
215
    return;
216
  if (!new)
217
    p->rt_notify(p, net, NULL, old, NULL);
218
  else if (tmpa)
219
    {
220
      ea_list *t = tmpa;
221
      while (t->next)
222
        t = t->next;
223
      t->next = new->attrs->eattrs;
224
      p->rt_notify(p, net, new, old, tmpa);
225
      t->next = NULL;
226
    }
227
  else
228
    p->rt_notify(p, net, new, old, new->attrs->eattrs);
229
  if (new && new != new0)        /* Discard temporary rte's */
230
    rte_free(new);
231
  if (old && old != old0)
232
    rte_free(old);
233
}
234

    
235
/**
236
 * rte_announce - announce a routing table change
237
 * @tab: table the route has been added to
238
 * @net: network in question
239
 * @new: the new route to be announced
240
 * @old: previous optimal route for the same network
241
 * @tmpa: a list of temporary attributes belonging to the new route
242
 *
243
 * This function gets a routing table update and announces it
244
 * to all protocols connected to the same table by their announcement hooks.
245
 *
246
 * For each such protocol, we first call its import_control() hook which
247
 * performs basic checks on the route (each protocol has a right to veto
248
 * or force accept of the route before any filter is asked) and adds default
249
 * values of attributes specific to the new protocol (metrics, tags etc.).
250
 * Then it consults the protocol's export filter and if it accepts the
251
 * route, the rt_notify() hook of the protocol gets called.
252
 */
253
static void
254
rte_announce(rtable *tab, net *net, rte *new, rte *old, ea_list *tmpa)
255
{
256
  struct announce_hook *a;
257
  int class = ipa_classify(net->n.prefix);
258

    
259
  WALK_LIST(a, tab->hooks)
260
    {
261
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
262
      do_rte_announce(a, net, new, old, tmpa, class);
263
    }
264
}
265

    
266
static inline int
267
rte_validate(rte *e)
268
{
269
  int c;
270
  net *n = e->net;
271

    
272
  if (ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))))
273
    {
274
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
275
          n->n.prefix, n->n.pxlen, e->attrs->proto->name);
276
      return 0;
277
    }
278
  if (n->n.pxlen)
279
    {
280
      c = ipa_classify(n->n.prefix);
281
      if (c < 0 || !(c & IADDR_HOST))
282
        {
283
          if (!ipa_nonzero(n->n.prefix))
284
            {
285
              /* Various default routes */
286
#ifdef IPV6
287
              if (n->n.pxlen == 96)
288
#else
289
              if (n->n.pxlen <= 1)
290
#endif
291
                return 1;
292
            }
293
          log(L_WARN "Ignoring bogus route %I/%d received via %s",
294
              n->n.prefix, n->n.pxlen, e->attrs->proto->name);
295
          return 0;
296
        }
297
      if ((c & IADDR_SCOPE_MASK) < e->attrs->proto->min_scope)
298
        {
299
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
300
              ip_scope_text(c & IADDR_SCOPE_MASK),
301
              n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
302
          return 0;
303
        }
304
    }
305
  return 1;
306
}
307

    
308
/**
309
 * rte_free - delete a &rte
310
 * @e: &rte to be deleted
311
 *
312
 * rte_free() deletes the given &rte from the routing table it's linked to.
313
 */
314
void
315
rte_free(rte *e)
316
{
317
  if (e->attrs->aflags & RTAF_CACHED)
318
    rta_free(e->attrs);
319
  sl_free(rte_slab, e);
320
}
321

    
322
static inline void
323
rte_free_quick(rte *e)
324
{
325
  rta_free(e->attrs);
326
  sl_free(rte_slab, e);
327
}
328

    
329
static int
330
rte_same(rte *x, rte *y)
331
{
332
  return
333
    x->attrs == y->attrs &&
334
    x->flags == y->flags &&
335
    x->pflags == y->pflags &&
336
    x->pref == y->pref &&
337
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
338
}
339

    
340
static void
341
rte_recalculate(rtable *table, net *net, struct proto *p, rte *new, ea_list *tmpa)
342
{
343
  rte *old_best = net->routes;
344
  rte *old = NULL;
345
  rte **k, *r, *s;
346

    
347
  k = &net->routes;                        /* Find and remove original route from the same protocol */
348
  while (old = *k)
349
    {
350
      if (old->attrs->proto == p)
351
        {
352
          if (new && rte_same(old, new))
353
            {
354
              /* No changes, ignore the new route */
355
              rte_trace_in(D_ROUTES, p, new, "ignored");
356
              rte_free_quick(new);
357
              old->lastmod = now;
358
              return;
359
            }
360
          *k = old->next;
361
          break;
362
        }
363
      k = &old->next;
364
    }
365

    
366
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
367
    {
368
      rte_trace_in(D_ROUTES, p, new, "added [best]");
369
      rte_announce(table, net, new, old_best, tmpa);
370
      new->next = net->routes;
371
      net->routes = new;
372
    }
373
  else
374
    {
375
      if (old == old_best)                /* It has _replaced_ the old optimal route */
376
        {
377
          r = new;                        /* Find new optimal route and announce it */
378
          for(s=net->routes; s; s=s->next)
379
            if (rte_better(s, r))
380
              r = s;
381
          rte_announce(table, net, r, old_best, tmpa);
382
          if (r)                        /* Re-link the new optimal route */
383
            {
384
              k = &net->routes;
385
              while (s = *k)
386
                {
387
                  if (s == r)
388
                    {
389
                      *k = r->next;
390
                      break;
391
                    }
392
                  k = &s->next;
393
                }
394
              r->next = net->routes;
395
              net->routes = r;
396
            }
397
          else if (table->gc_counter++ >= table->config->gc_max_ops &&
398
                   table->gc_time + table->config->gc_min_time <= now)
399
            ev_schedule(table->gc_event);
400
        }
401
      if (new)                                /* Link in the new non-optimal route */
402
        {
403
          new->next = old_best->next;
404
          old_best->next = new;
405
          rte_trace_in(D_ROUTES, p, new, "added");
406
        }
407
      else if (old && (p->debug & D_ROUTES))
408
        {
409
          if (old != old_best)
410
            rte_trace_in(D_ROUTES, p, old, "removed");
411
          else if (net->routes)
412
            rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
413
          else
414
            rte_trace_in(D_ROUTES, p, old, "removed [sole]");
415
        }
416
    }
417
  if (old)
418
    {
419
      if (p->rte_remove)
420
        p->rte_remove(net, old);
421
      rte_free_quick(old);
422
    }
423
  if (new)
424
    {
425
      new->lastmod = now;
426
      if (p->rte_insert)
427
        p->rte_insert(net, new);
428
    }
429
}
430

    
431
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
432

    
433
static inline void
434
rte_update_lock(void)
435
{
436
  rte_update_nest_cnt++;
437
}
438

    
439
static inline void
440
rte_update_unlock(void)
441
{
442
  if (!--rte_update_nest_cnt)
443
    lp_flush(rte_update_pool);
444
}
445

    
446
/**
447
 * rte_update - enter a new update to a routing table
448
 * @table: table to be updated
449
 * @net: network node
450
 * @p: protocol submitting the update
451
 * @new: a &rte representing the new route or %NULL for route removal.
452
 *
453
 * This function is called by the routing protocols whenever they discover
454
 * a new route or wish to update/remove an existing route. The right announcement
455
 * sequence is to build route attributes first (either un-cached with @aflags set
456
 * to zero or a cached one using rta_lookup(); in this case please note that
457
 * you need to increase the use count of the attributes yourself by calling
458
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
459
 * the appropriate data and finally submit the new &rte by calling rte_update().
460
 *
461
 * When rte_update() gets any route, it automatically validates it (checks,
462
 * whether the network and next hop address are valid IP addresses and also
463
 * whether a normal routing protocol doesn't try to smuggle a host or link
464
 * scope route to the table), converts all protocol dependent attributes stored
465
 * in the &rte to temporary extended attributes, consults import filters of the
466
 * protocol to see if the route should be accepted and/or its attributes modified,
467
 * stores the temporary attributes back to the &rte.
468
 *
469
 * Now, having a "public" version of the route, we
470
 * automatically find any old route defined by the protocol @p
471
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
472
 * recalculate the optimal route for this destination and finally broadcast
473
 * the change (if any) to all routing protocols by calling rte_announce().
474
 *
475
 * All memory used for attribute lists and other temporary allocations is taken
476
 * from a special linear pool @rte_update_pool and freed when rte_update()
477
 * finishes.
478
 */
479
void
480
rte_update(rtable *table, net *net, struct proto *p, rte *new)
481
{
482
  ea_list *tmpa = NULL;
483

    
484
  rte_update_lock();
485
  if (new)
486
    {
487
      if (!rte_validate(new))
488
        {
489
          rte_trace_in(D_FILTERS, p, new, "invalid");
490
          goto drop;
491
        }
492
      if (p->in_filter == FILTER_REJECT)
493
        {
494
          rte_trace_in(D_FILTERS, p, new, "filtered out");
495
          goto drop;
496
        }
497
      if (p->make_tmp_attrs)
498
        tmpa = p->make_tmp_attrs(new, rte_update_pool);
499
      if (p->in_filter)
500
        {
501
          ea_list *old_tmpa = tmpa;
502
          int fr = f_run(p->in_filter, &new, &tmpa, rte_update_pool, 0);
503
          if (fr > F_ACCEPT)
504
            {
505
              rte_trace_in(D_FILTERS, p, new, "filtered out");
506
              goto drop;
507
            }
508
          if (tmpa != old_tmpa && p->store_tmp_attrs)
509
            p->store_tmp_attrs(new, tmpa);
510
        }
511
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
512
        new->attrs = rta_lookup(new->attrs);
513
      new->flags |= REF_COW;
514
    }
515
  rte_recalculate(table, net, p, new, tmpa);
516
  rte_update_unlock();
517
  return;
518

    
519
drop:
520
  rte_free(new);
521
  rte_update_unlock();
522
}
523

    
524
void
525
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
526
{
527
  net *n = old->net;
528
  struct proto *p = old->attrs->proto;
529

    
530
  rte_update_lock();
531
  rte_recalculate(t, n, p, NULL, NULL);
532
  rte_update_unlock();
533
}
534

    
535
/**
536
 * rte_dump - dump a route
537
 * @e: &rte to be dumped
538
 *
539
 * This functions dumps contents of a &rte to debug output.
540
 */
541
void
542
rte_dump(rte *e)
543
{
544
  net *n = e->net;
545
  if (n)
546
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
547
  else
548
    debug("??? ");
549
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
550
  rta_dump(e->attrs);
551
  if (e->attrs->proto->proto->dump_attrs)
552
    e->attrs->proto->proto->dump_attrs(e);
553
  debug("\n");
554
}
555

    
556
/**
557
 * rt_dump - dump a routing table
558
 * @t: routing table to be dumped
559
 *
560
 * This function dumps contents of a given routing table to debug output.
561
 */
562
void
563
rt_dump(rtable *t)
564
{
565
  rte *e;
566
  net *n;
567
  struct announce_hook *a;
568

    
569
  debug("Dump of routing table <%s>\n", t->name);
570
#ifdef DEBUGGING
571
  fib_check(&t->fib);
572
#endif
573
  FIB_WALK(&t->fib, fn)
574
    {
575
      n = (net *) fn;
576
      for(e=n->routes; e; e=e->next)
577
        rte_dump(e);
578
    }
579
  FIB_WALK_END;
580
  WALK_LIST(a, t->hooks)
581
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
582
  debug("\n");
583
}
584

    
585
/**
586
 * rt_dump_all - dump all routing tables
587
 *
588
 * This function dumps contents of all routing tables to debug output.
589
 */
590
void
591
rt_dump_all(void)
592
{
593
  rtable *t;
594

    
595
  WALK_LIST(t, routing_tables)
596
    rt_dump(t);
597
}
598

    
599
static void
600
rt_gc(void *tab)
601
{
602
  rtable *t = tab;
603

    
604
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
605
      t->name, (int)(now - t->gc_time), t->gc_counter);
606
  rt_prune(t);
607
}
608

    
609
void
610
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
611
{
612
  bzero(t, sizeof(*t));
613
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
614
  t->name = name;
615
  t->config = cf;
616
  init_list(&t->hooks);
617
  if (cf)
618
    {
619
      t->gc_event = ev_new(p);
620
      t->gc_event->hook = rt_gc;
621
      t->gc_event->data = t;
622
      t->gc_time = now;
623
    }
624
}
625

    
626
/**
627
 * rt_init - initialize routing tables
628
 *
629
 * This function is called during BIRD startup. It initializes the
630
 * routing table module.
631
 */
632
void
633
rt_init(void)
634
{
635
  rta_init();
636
  rt_table_pool = rp_new(&root_pool, "Routing tables");
637
  rte_update_pool = lp_new(rt_table_pool, 4080);
638
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
639
  init_list(&routing_tables);
640
}
641

    
642
/**
643
 * rt_prune - prune a routing table
644
 * @tab: routing table to be pruned
645
 *
646
 * This function is called whenever a protocol shuts down. It scans
647
 * the routing table and removes all routes belonging to inactive
648
 * protocols and also stale network entries.
649
 */
650
void
651
rt_prune(rtable *tab)
652
{
653
  struct fib_iterator fit;
654
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
655

    
656
  DBG("Pruning route table %s\n", tab->name);
657
#ifdef DEBUGGING
658
  fib_check(&tab->fib);
659
#endif
660
  FIB_ITERATE_INIT(&fit, &tab->fib);
661
again:
662
  FIB_ITERATE_START(&tab->fib, &fit, f)
663
    {
664
      net *n = (net *) f;
665
      rte *e;
666
      ncnt++;
667
    rescan:
668
      for (e=n->routes; e; e=e->next, rcnt++)
669
        if (e->attrs->proto->core_state != FS_HAPPY &&
670
            e->attrs->proto->core_state != FS_FEEDING)
671
          {
672
            rte_discard(tab, e);
673
            rdel++;
674
            goto rescan;
675
          }
676
      if (!n->routes)                /* Orphaned FIB entry? */
677
        {
678
          FIB_ITERATE_PUT(&fit, f);
679
          fib_delete(&tab->fib, f);
680
          ndel++;
681
          goto again;
682
        }
683
    }
684
  FIB_ITERATE_END(f);
685
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
686
#ifdef DEBUGGING
687
  fib_check(&tab->fib);
688
#endif
689
  tab->gc_counter = 0;
690
  tab->gc_time = now;
691
}
692

    
693
/**
694
 * rt_prune_all - prune all routing tables
695
 *
696
 * This function calls rt_prune() for all known routing tables.
697
 */
698
void
699
rt_prune_all(void)
700
{
701
  rtable *t;
702

    
703
  WALK_LIST(t, routing_tables)
704
    rt_prune(t);
705
}
706

    
707
struct rtable_config *
708
rt_new_table(struct symbol *s)
709
{
710
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
711

    
712
  cf_define_symbol(s, SYM_TABLE, c);
713
  c->name = s->name;
714
  add_tail(&new_config->tables, &c->n);
715
  c->gc_max_ops = 1000;
716
  c->gc_min_time = 5;
717
  return c;
718
}
719

    
720
void
721
rt_preconfig(struct config *c)
722
{
723
  struct symbol *s = cf_find_symbol("master");
724

    
725
  init_list(&c->tables);
726
  c->master_rtc = rt_new_table(s);
727
}
728

    
729
/**
730
 * rt_lock_table - lock a routing table
731
 * @r: routing table to be locked
732
 *
733
 * Lock a routing table, because it's in use by a protocol,
734
 * preventing it from being freed when it gets undefined in a new
735
 * configuration.
736
 */
737
void
738
rt_lock_table(rtable *r)
739
{
740
  r->use_count++;
741
}
742

    
743
/**
744
 * rt_unlock_table - unlock a routing table
745
 * @r: routing table to be unlocked
746
 *
747
 * Unlock a routing table formerly locked by rt_lock_table(),
748
 * that is decrease its use count and delete it if it's scheduled
749
 * for deletion by configuration changes.
750
 */
751
void
752
rt_unlock_table(rtable *r)
753
{
754
  if (!--r->use_count && r->deleted)
755
    {
756
      struct config *conf = r->deleted;
757
      DBG("Deleting routing table %s\n", r->name);
758
      rem_node(&r->n);
759
      fib_free(&r->fib);
760
      mb_free(r);
761
      config_del_obstacle(conf);
762
    }
763
}
764

    
765
/**
766
 * rt_commit - commit new routing table configuration
767
 * @new: new configuration
768
 * @old: original configuration or %NULL if it's boot time config
769
 *
770
 * Scan differences between @old and @new configuration and modify
771
 * the routing tables according to these changes. If @new defines a
772
 * previously unknown table, create it, if it omits a table existing
773
 * in @old, schedule it for deletion (it gets deleted when all protocols
774
 * disconnect from it by calling rt_unlock_table()), if it exists
775
 * in both configurations, leave it unchanged.
776
 */
777
void
778
rt_commit(struct config *new, struct config *old)
779
{
780
  struct rtable_config *o, *r;
781

    
782
  DBG("rt_commit:\n");
783
  if (old)
784
    {
785
      WALK_LIST(o, old->tables)
786
        {
787
          rtable *ot = o->table;
788
          if (!ot->deleted)
789
            {
790
              struct symbol *sym = cf_find_symbol(o->name);
791
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
792
                {
793
                  DBG("\t%s: same\n", o->name);
794
                  r = sym->def;
795
                  r->table = ot;
796
                  ot->name = r->name;
797
                  ot->config = r;
798
                }
799
              else
800
                {
801
                  DBG("\t%s: deleted\n", o->name);
802
                  ot->deleted = old;
803
                  config_add_obstacle(old);
804
                  rt_lock_table(ot);
805
                  rt_unlock_table(ot);
806
                }
807
            }
808
        }
809
    }
810

    
811
  WALK_LIST(r, new->tables)
812
    if (!r->table)
813
      {
814
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
815
        DBG("\t%s: created\n", r->name);
816
        rt_setup(rt_table_pool, t, r->name, r);
817
        add_tail(&routing_tables, &t->n);
818
        r->table = t;
819
      }
820
  DBG("\tdone\n");
821
}
822

    
823
/**
824
 * rt_feed_baby - advertise routes to a new protocol
825
 * @p: protocol to be fed
826
 *
827
 * This function performs one pass of advertisement of routes to a newly
828
 * initialized protocol. It's called by the protocol code as long as it
829
 * has something to do. (We avoid transferring all the routes in single
830
 * pass in order not to monopolize CPU time.)
831
 */
832
int
833
rt_feed_baby(struct proto *p)
834
{
835
  struct announce_hook *h;
836
  struct fib_iterator *fit;
837
  int max_feed = 256;
838

    
839
  if (!p->feed_ahook)                        /* Need to initialize first */
840
    {
841
      if (!p->ahooks)
842
        return 1;
843
      DBG("Announcing routes to new protocol %s\n", p->name);
844
      p->feed_ahook = p->ahooks;
845
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
846
      goto next_hook;
847
    }
848
  fit = p->feed_iterator;
849

    
850
again:
851
  h = p->feed_ahook;
852
  FIB_ITERATE_START(&h->table->fib, fit, fn)
853
    {
854
      net *n = (net *) fn;
855
      rte *e;
856
      if (max_feed <= 0)
857
        {
858
          FIB_ITERATE_PUT(fit, fn);
859
          return 0;
860
        }
861
      for(e=n->routes; e; e=e->next)
862
        {
863
          struct proto *q = e->attrs->proto;
864
          ea_list *tmpa;
865

    
866
          if (p->core_state != FS_FEEDING)
867
            return 1;  /* In the meantime, the protocol fell down. */
868
          rte_update_lock();
869
          tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
870
          do_rte_announce(h, n, e, NULL, tmpa, ipa_classify(n->n.prefix));
871
          rte_update_unlock();
872
          max_feed--;
873
        }
874
    }
875
  FIB_ITERATE_END(fn);
876
  p->feed_ahook = h->next;
877
  if (!p->feed_ahook)
878
    {
879
      mb_free(p->feed_iterator);
880
      p->feed_iterator = NULL;
881
      return 1;
882
    }
883

    
884
next_hook:
885
  h = p->feed_ahook;
886
  FIB_ITERATE_INIT(fit, &h->table->fib);
887
  goto again;
888
}
889

    
890
/**
891
 * rt_feed_baby_abort - abort protocol feeding
892
 * @p: protocol
893
 *
894
 * This function is called by the protocol code when the protocol
895
 * stops or ceases to exist before the last iteration of rt_feed_baby()
896
 * has finished.
897
 */
898
void
899
rt_feed_baby_abort(struct proto *p)
900
{
901
  if (p->feed_ahook)
902
    {
903
      /* Unlink the iterator and exit */
904
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
905
      p->feed_ahook = NULL;
906
    }
907
}
908

    
909
/*
910
 *  CLI commands
911
 */
912

    
913
static void
914
rt_format_via(rte *e, byte *via)
915
{
916
  rta *a = e->attrs;
917

    
918
  switch (a->dest)
919
    {
920
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
921
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
922
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
923
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
924
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
925
    default:                bsprintf(via, "???");
926
    }
927
}
928

    
929
static void
930
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
931
{
932
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
933
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
934
  rta *a = e->attrs;
935

    
936
  rt_format_via(e, via);
937
  tm_format_reltime(tm, e->lastmod);
938
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
939
    bsprintf(from, " from %I", a->from);
940
  else
941
    from[0] = 0;
942
  if (a->proto->proto->get_route_info || d->verbose)
943
    {
944
      /* Need to normalize the extended attributes */
945
      ea_list *t = tmpa;
946
      t = ea_append(t, a->eattrs);
947
      tmpa = alloca(ea_scan(t));
948
      ea_merge(t, tmpa);
949
      ea_sort(tmpa);
950
    }
951
  if (a->proto->proto->get_route_info)
952
    a->proto->proto->get_route_info(e, info, tmpa);
953
  else
954
    bsprintf(info, " (%d)", e->pref);
955
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
956
  if (d->verbose)
957
    rta_show(c, a, tmpa);
958
}
959

    
960
static void
961
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
962
{
963
  rte *e, *ee;
964
  byte ia[STD_ADDRESS_P_LENGTH+8];
965
  int ok;
966

    
967
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
968
  if (n->routes)
969
    d->net_counter++;
970
  for(e=n->routes; e; e=e->next)
971
    {
972
      struct ea_list *tmpa, *old_tmpa;
973
      struct proto *p0 = e->attrs->proto;
974
      struct proto *p1 = d->import_protocol;
975
      d->rt_counter++;
976
      ee = e;
977
      rte_update_lock();                /* We use the update buffer for filtering */
978
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
979
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
980
      if (ok && d->import_mode)
981
        {
982
          int ic = (p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0);
983
          if (ic < 0)
984
            ok = 0;
985
          else if (!ic && d->import_mode > 1)
986
            {
987
              if (p1->out_filter == FILTER_REJECT ||
988
                  p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
989
                ok = 0;
990
            }
991
        }
992
      if (ok)
993
        {
994
          d->show_counter++;
995
          if (d->stats < 2)
996
            rt_show_rte(c, ia, e, d, tmpa);
997
          ia[0] = 0;
998
        }
999
      if (e != ee)
1000
        rte_free(ee);
1001
      rte_update_unlock();
1002
      if (d->primary_only)
1003
        break;
1004
    }
1005
}
1006

    
1007
static void
1008
rt_show_cont(struct cli *c)
1009
{
1010
  struct rt_show_data *d = c->rover;
1011
#ifdef DEBUGGING
1012
  unsigned max = 4;
1013
#else
1014
  unsigned max = 64;
1015
#endif
1016
  struct fib *fib = &d->table->fib;
1017
  struct fib_iterator *it = &d->fit;
1018

    
1019
  FIB_ITERATE_START(fib, it, f)
1020
    {
1021
      net *n = (net *) f;
1022
      if (d->running_on_config && d->running_on_config != config)
1023
        {
1024
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1025
          goto done;
1026
        }
1027
      if (d->import_protocol &&
1028
          d->import_protocol->core_state != FS_HAPPY &&
1029
          d->import_protocol->core_state != FS_FEEDING)
1030
        {
1031
          cli_printf(c, 8005, "Protocol is down");
1032
          goto done;
1033
        }
1034
      if (!max--)
1035
        {
1036
          FIB_ITERATE_PUT(it, f);
1037
          return;
1038
        }
1039
      rt_show_net(c, n, d);
1040
    }
1041
  FIB_ITERATE_END(f);
1042
  if (d->stats)
1043
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1044
  else
1045
    cli_printf(c, 0, "");
1046
done:
1047
  c->cont = c->cleanup = NULL;
1048
}
1049

    
1050
static void
1051
rt_show_cleanup(struct cli *c)
1052
{
1053
  struct rt_show_data *d = c->rover;
1054

    
1055
  /* Unlink the iterator */
1056
  fit_get(&d->table->fib, &d->fit);
1057
}
1058

    
1059
void
1060
rt_show(struct rt_show_data *d)
1061
{
1062
  net *n;
1063

    
1064
  if (d->pxlen == 256)
1065
    {
1066
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1067
      this_cli->cont = rt_show_cont;
1068
      this_cli->cleanup = rt_show_cleanup;
1069
      this_cli->rover = d;
1070
    }
1071
  else
1072
    {
1073
      if (d->show_for)
1074
        n = fib_route(&d->table->fib, d->prefix, d->pxlen);
1075
      else
1076
        n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
1077
      if (n)
1078
        {
1079
          rt_show_net(this_cli, n, d);
1080
          cli_msg(0, "");
1081
        }
1082
      else
1083
        cli_msg(8001, "Network not in table");
1084
    }
1085
}
1086

    
1087
/*
1088
 *  Documentation for functions declared inline in route.h
1089
 */
1090
#if 0
1091

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

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

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

1138
#endif