Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 725270cb

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

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

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

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

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

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

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

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

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

    
100
rte *
101
rte_do_cow(rte *r)
102
{
103
  rte *e = sl_alloc(rte_slab);
104

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

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

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

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

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

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

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

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

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

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

    
254
  WALK_LIST(a, tab->hooks)
255
    {
256
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
257
      do_rte_announce(a, net, new, old, tmpa, class);
258
    }
259
}
260

    
261
static inline int
262
rte_validate(rte *e)
263
{
264
  int c;
265
  net *n = e->net;
266

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

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

    
317
static inline void
318
rte_free_quick(rte *e)
319
{
320
  rta_free(e->attrs);
321
  sl_free(rte_slab, e);
322
}
323

    
324
static int
325
rte_same(rte *x, rte *y)
326
{
327
  return
328
    x->attrs == y->attrs &&
329
    x->flags == y->flags &&
330
    x->pflags == y->pflags &&
331
    x->pref == y->pref &&
332
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
333
}
334

    
335
static void
336
rte_recalculate(rtable *table, net *net, struct proto *p, rte *new, ea_list *tmpa)
337
{
338
  rte *old_best = net->routes;
339
  rte *old = NULL;
340
  rte **k, *r, *s;
341

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

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

    
426
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
427

    
428
static inline void
429
rte_update_lock(void)
430
{
431
  rte_update_nest_cnt++;
432
}
433

    
434
static inline void
435
rte_update_unlock(void)
436
{
437
  if (!--rte_update_nest_cnt)
438
    lp_flush(rte_update_pool);
439
}
440

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

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

    
514
drop:
515
  rte_free(new);
516
  rte_update_unlock();
517
}
518

    
519
void
520
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
521
{
522
  net *n = old->net;
523
  struct proto *p = old->attrs->proto;
524

    
525
  rte_update_lock();
526
  rte_recalculate(t, n, p, NULL, NULL);
527
  rte_update_unlock();
528
}
529

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

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

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

    
580
/**
581
 * rt_dump_all - dump all routing tables
582
 *
583
 * This function dumps contents of all routing tables to debug output.
584
 */
585
void
586
rt_dump_all(void)
587
{
588
  rtable *t;
589

    
590
  WALK_LIST(t, routing_tables)
591
    rt_dump(t);
592
}
593

    
594
static void
595
rt_gc(void *tab)
596
{
597
  rtable *t = tab;
598

    
599
  DBG("Entered routing table garbage collector for %s after %d seconds and %d deletes\n",
600
      t->name, (int)(now - t->gc_time), t->gc_counter);
601
  rt_prune(t);
602
}
603

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

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

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

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

    
688
/**
689
 * rt_prune_all - prune all routing tables
690
 *
691
 * This function calls rt_prune() for all known routing tables.
692
 */
693
void
694
rt_prune_all(void)
695
{
696
  rtable *t;
697

    
698
  WALK_LIST(t, routing_tables)
699
    rt_prune(t);
700
}
701

    
702
struct rtable_config *
703
rt_new_table(struct symbol *s)
704
{
705
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
706

    
707
  cf_define_symbol(s, SYM_TABLE, c);
708
  c->name = s->name;
709
  add_tail(&new_config->tables, &c->n);
710
  c->gc_max_ops = 1000;
711
  c->gc_min_time = 5;
712
  return c;
713
}
714

    
715
void
716
rt_preconfig(struct config *c)
717
{
718
  struct symbol *s = cf_find_symbol("master");
719

    
720
  init_list(&c->tables);
721
  c->master_rtc = rt_new_table(s);
722
}
723

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

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

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

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

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

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

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

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

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

    
879
next_hook:
880
  h = p->feed_ahook;
881
  FIB_ITERATE_INIT(fit, &h->table->fib);
882
  goto again;
883
}
884

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

    
904
/*
905
 *  CLI commands
906
 */
907

    
908
static void
909
rt_format_via(rte *e, byte *via)
910
{
911
  rta *a = e->attrs;
912

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

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

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

    
955
static void
956
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
957
{
958
  rte *e, *ee;
959
  byte ia[STD_ADDRESS_P_LENGTH+8];
960
  int ok;
961

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

    
1002
static void
1003
rt_show_cont(struct cli *c)
1004
{
1005
  struct rt_show_data *d = c->rover;
1006
#ifdef DEBUGGING
1007
  unsigned max = 4;
1008
#else
1009
  unsigned max = 64;
1010
#endif
1011
  struct fib *fib = &d->table->fib;
1012
  struct fib_iterator *it = &d->fit;
1013

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

    
1045
static void
1046
rt_show_cleanup(struct cli *c)
1047
{
1048
  struct rt_show_data *d = c->rover;
1049

    
1050
  /* Unlink the iterator */
1051
  fit_get(&d->table->fib, &d->fit);
1052
}
1053

    
1054
void
1055
rt_show(struct rt_show_data *d)
1056
{
1057
  net *n;
1058

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

    
1082
/*
1083
 *  Documentation for functions declared inline in route.h
1084
 */
1085
#if 0
1086

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

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

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

1133
#endif