Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (13 KB)

1
/*
2
 *        BIRD -- Routing Table
3
 *
4
 *        (c) 1998--1999 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#include <string.h>
10

    
11
#define LOCAL_DEBUG
12

    
13
#include "nest/bird.h"
14
#include "nest/route.h"
15
#include "nest/protocol.h"
16
#include "nest/cli.h"
17
#include "nest/iface.h"
18
#include "lib/resource.h"
19
#include "lib/event.h"
20
#include "lib/string.h"
21
#include "conf/conf.h"
22
#include "filter/filter.h"
23

    
24
static slab *rte_slab;
25
static linpool *rte_update_pool;
26

    
27
#define RT_GC_MIN_TIME 5                /* FIXME: Make configurable */
28
#define RT_GC_MIN_COUNT 100
29

    
30
static pool *rt_table_pool;
31
static list routing_tables;
32
static event *rt_gc_event;
33
static bird_clock_t rt_last_gc;
34
static int rt_gc_counter;
35

    
36
static void
37
rte_init(struct fib_node *N)
38
{
39
  net *n = (net *) N;
40

    
41
  N->flags = 0;
42
  n->routes = NULL;
43
}
44

    
45
void
46
rt_setup(pool *p, rtable *t, char *name)
47
{
48
  bzero(t, sizeof(*t));
49
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
50
  t->name = name;
51
  init_list(&t->hooks);
52
}
53

    
54
rte *
55
rte_find(net *net, struct proto *p)
56
{
57
  rte *e = net->routes;
58

    
59
  while (e && e->attrs->proto != p)
60
    e = e->next;
61
  return e;
62
}
63

    
64
rte *
65
rte_get_temp(rta *a)
66
{
67
  rte *e = sl_alloc(rte_slab);
68

    
69
  e->attrs = a;
70
  e->flags = 0;
71
  e->pref = a->proto->preference;
72
  return e;
73
}
74

    
75
rte *
76
rte_do_cow(rte *r)
77
{
78
  rte *e = sl_alloc(rte_slab);
79

    
80
  memcpy(e, r, sizeof(rte));
81
  e->attrs = rta_clone(r->attrs);
82
  e->flags = 0;
83
  return e;
84
}
85

    
86
static int                                /* Actually better or at least as good as */
87
rte_better(rte *new, rte *old)
88
{
89
  int (*better)(rte *, rte *);
90

    
91
  if (!old)
92
    return 1;
93
  if (new->pref > old->pref)
94
    return 1;
95
  if (new->pref < old->pref)
96
    return 0;
97
  if (new->attrs->proto->proto != old->attrs->proto->proto)
98
    bug("Different protocols, but identical preferences => oops");        /* FIXME */
99
  if (better = new->attrs->proto->rte_better)
100
    return better(new, old);
101
  return 0;
102
}
103

    
104
static inline void
105
do_rte_announce(struct announce_hook *a, net *net, rte *new, rte *old, ea_list *tmpa, int class)
106
{
107
  struct proto *p = a->proto;
108
  rte *new0 = new;
109
  rte *old0 = old;
110

    
111
  if (new)
112
    {
113
      int ok;
114
      if ((class & IADDR_SCOPE_MASK) < p->min_scope ||
115
          (ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0 ||
116
          (!ok && (p->out_filter == FILTER_REJECT ||
117
                   p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool) > F_ACCEPT)
118
          )
119
         )
120
        new = NULL;
121
    }
122
  if (old && p->out_filter)
123
    {
124
      /* FIXME: Do we really need to filter old routes? */
125
      if (p->out_filter == FILTER_REJECT)
126
        old = NULL;
127
      else
128
        {
129
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
130
          if (f_run(p->out_filter, &old, &tmpb, rte_update_pool) > F_ACCEPT)
131
            old = NULL;
132
        }
133
    }
134
  if (new || old)
135
    p->rt_notify(p, net, new, old, tmpa);
136
  if (new && new != new0)        /* Discard temporary rte's */
137
    rte_free(new);
138
  if (old && old != old0)
139
    rte_free(old);
140
}
141

    
142
static void
143
rte_announce(rtable *tab, net *net, rte *new, rte *old, ea_list *tmpa)
144
{
145
  struct announce_hook *a;
146
  int class = ipa_classify(net->n.prefix);
147

    
148
  WALK_LIST(a, tab->hooks)
149
    {
150
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
151
      do_rte_announce(a, net, new, old, tmpa, class);
152
    }
153
}
154

    
155
void
156
rt_feed_baby(struct proto *p)
157
{
158
  struct announce_hook *h;
159

    
160
  if (!p->ahooks)
161
    return;
162
  debug("Announcing routes to new protocol %s\n", p->name);
163
  for(h=p->ahooks; h; h=h->next)
164
    {
165
      rtable *t = h->table;
166
      FIB_WALK(&t->fib, fn)
167
        {
168
          net *n = (net *) fn;
169
          rte *e;
170
          for(e=n->routes; e; e=e->next)
171
            {
172
              struct proto *q = e->attrs->proto;
173
              ea_list *tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
174
              do_rte_announce(h, n, e, NULL, tmpa, ipa_classify(n->n.prefix));
175
              lp_flush(rte_update_pool);
176
            }
177
        }
178
      FIB_WALK_END;
179
    }
180
}
181

    
182
static inline int
183
rte_validate(rte *e)
184
{
185
  int c;
186
  net *n = e->net;
187

    
188
  ASSERT(!ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))));
189
  if (n->n.pxlen)
190
    {
191
      c = ipa_classify(n->n.prefix);
192
      if (c < 0 || !(c & IADDR_HOST))
193
        {
194
          if (!ipa_nonzero(n->n.prefix) && n->n.pxlen <= 1)
195
            return 1;                /* Default route and half-default route is OK */
196
          log(L_WARN "Ignoring bogus route %I/%d received from %I via %s",
197
              n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
198
          return 0;
199
        }
200
      if ((c & IADDR_SCOPE_MASK) < e->attrs->proto->min_scope)
201
        {
202
          log(L_WARN "Ignoring %s scope route %I/%d received from %I via %s",
203
              ip_scope_text(c & IADDR_SCOPE_MASK),
204
              n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
205
          return 0;
206
        }
207
    }
208
  return 1;
209
}
210

    
211
void
212
rte_free(rte *e)
213
{
214
  if (e->attrs->aflags & RTAF_CACHED)
215
    rta_free(e->attrs);
216
  sl_free(rte_slab, e);
217
}
218

    
219
static inline void
220
rte_free_quick(rte *e)
221
{
222
  rta_free(e->attrs);
223
  sl_free(rte_slab, e);
224
}
225

    
226
static void
227
rte_recalculate(rtable *table, net *net, struct proto *p, rte *new, ea_list *tmpa)
228
{
229
  rte *old_best = net->routes;
230
  rte *old = NULL;
231
  rte **k, *r, *s;
232

    
233
  k = &net->routes;                        /* Find and remove original route from the same protocol */
234
  while (old = *k)
235
    {
236
      if (old->attrs->proto == p)
237
        {
238
          *k = old->next;
239
          break;
240
        }
241
      k = &old->next;
242
    }
243

    
244
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
245
    {
246
      rte_announce(table, net, new, old_best, tmpa);
247
      new->next = net->routes;
248
      net->routes = new;
249
    }
250
  else
251
    {
252
      if (old == old_best)                /* It has _replaced_ the old optimal route */
253
        {
254
          r = new;                        /* Find new optimal route and announce it */
255
          for(s=net->routes; s; s=s->next)
256
            if (rte_better(s, r))
257
              r = s;
258
          rte_announce(table, net, r, old_best, tmpa);
259
          if (r)                        /* Re-link the new optimal route */
260
            {
261
              k = &net->routes;
262
              while (s = *k)
263
                {
264
                  if (s == r)
265
                    {
266
                      *k = r->next;
267
                      break;
268
                    }
269
                  k = &s->next;
270
                }
271
              r->next = net->routes;
272
              net->routes = r;
273
              if (!r && rt_gc_counter++ >= RT_GC_MIN_COUNT && rt_last_gc + RT_GC_MIN_TIME <= now)
274
                ev_schedule(rt_gc_event);
275
            }
276
        }
277
      if (new)                                /* Link in the new non-optimal route */
278
        {
279
          new->next = old_best->next;
280
          old_best->next = new;
281
        }
282
    }
283
  if (old)
284
    {
285
      if (p->rte_remove)
286
        p->rte_remove(net, old);
287
      rte_free_quick(old);
288
    }
289
  if (new)
290
    {
291
      new->lastmod = now;
292
      if (p->rte_insert)
293
        p->rte_insert(net, new);
294
    }
295
}
296

    
297
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
298

    
299
static inline void
300
rte_update_lock(void)
301
{
302
  rte_update_nest_cnt++;
303
}
304

    
305
static inline void
306
rte_update_unlock(void)
307
{
308
  if (!--rte_update_nest_cnt)
309
    lp_flush(rte_update_pool);
310
}
311

    
312
void
313
rte_update(rtable *table, net *net, struct proto *p, rte *new)
314
{
315
  ea_list *tmpa = NULL;
316

    
317
  rte_update_lock();
318
  if (new)
319
    {
320
      if (!rte_validate(new) || p->in_filter == FILTER_REJECT)
321
        goto drop;
322
      if (p->make_tmp_attrs)
323
        tmpa = p->make_tmp_attrs(new, rte_update_pool);
324
      if (p->in_filter)
325
        {
326
          ea_list *old_tmpa = tmpa;
327
          int fr = f_run(p->in_filter, &new, &tmpa, rte_update_pool);
328
          if (fr > F_ACCEPT)
329
            goto drop;
330
          if (tmpa != old_tmpa && p->store_tmp_attrs)
331
            p->store_tmp_attrs(new, tmpa);
332
        }
333
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
334
        new->attrs = rta_lookup(new->attrs);
335
      new->flags |= REF_COW;
336
    }
337
  rte_recalculate(table, net, p, new, tmpa);
338
  rte_update_unlock();
339
  return;
340

    
341
drop:
342
  rte_free(new);
343
  rte_update_unlock();
344
}
345

    
346
void
347
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
348
{
349
  rte_update_lock();
350
  rte_recalculate(t, old->net, old->attrs->proto, NULL, NULL);
351
  rte_update_unlock();
352
}
353

    
354
void
355
rte_dump(rte *e)
356
{
357
  net *n = e->net;
358
  if (n)
359
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
360
  else
361
    debug("??? ");
362
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
363
  rta_dump(e->attrs);
364
  if (e->attrs->proto->proto->dump_attrs)
365
    e->attrs->proto->proto->dump_attrs(e);
366
  debug("\n");
367
}
368

    
369
void
370
rt_dump(rtable *t)
371
{
372
  rte *e;
373
  net *n;
374
  struct announce_hook *a;
375

    
376
  debug("Dump of routing table <%s>\n", t->name);
377
#ifdef DEBUGGING
378
  fib_check(&t->fib);
379
#endif
380
  FIB_WALK(&t->fib, fn)
381
    {
382
      n = (net *) fn;
383
      for(e=n->routes; e; e=e->next)
384
        rte_dump(e);
385
    }
386
  FIB_WALK_END;
387
  WALK_LIST(a, t->hooks)
388
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
389
  debug("\n");
390
}
391

    
392
void
393
rt_dump_all(void)
394
{
395
  rtable *t;
396

    
397
  WALK_LIST(t, routing_tables)
398
    rt_dump(t);
399
}
400

    
401
static int
402
rt_gc(void *unused)
403
{
404
  rtable *t;
405

    
406
  DBG("Entered routing table garbage collector after %d seconds and %d deletes\n", (int)(now - rt_last_gc), rt_gc_counter);
407
  rt_prune_all();
408
  rt_last_gc = now;
409
  rt_gc_counter = 0;
410
  return 0;
411
}
412

    
413
void
414
rt_init(void)
415
{
416
  rta_init();
417
  rt_table_pool = rp_new(&root_pool, "Routing tables");
418
  rte_update_pool = lp_new(rt_table_pool, 4080);
419
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
420
  rt_last_gc = now;
421
  rt_gc_event = ev_new(rt_table_pool);
422
  rt_gc_event->hook = rt_gc;
423
  init_list(&routing_tables);
424
}
425

    
426
void
427
rt_prune(rtable *tab)
428
{
429
  struct fib_iterator fit;
430
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
431

    
432
  DBG("Pruning route table %s\n", tab->name);
433
  FIB_ITERATE_INIT(&fit, &tab->fib);
434
again:
435
  FIB_ITERATE_START(&tab->fib, &fit, f)
436
    {
437
      net *n = (net *) f;
438
      rte *e;
439
      ncnt++;
440
    rescan:
441
      for (e=n->routes; e; e=e->next, rcnt++)
442
        if (e->attrs->proto->core_state != FS_HAPPY)
443
          {
444
            rte_discard(tab, e);
445
            rdel++;
446
            goto rescan;
447
          }
448
      if (!n->routes)                /* Orphaned FIB entry? */
449
        {
450
          FIB_ITERATE_PUT(&fit, f);
451
          fib_delete(&tab->fib, f);
452
          ndel++;
453
          goto again;
454
        }
455
    }
456
  FIB_ITERATE_END(f);
457
  DBG("Pruned %d of %d routes and %d of %d networks\n", rcnt, rdel, ncnt, ndel);
458
}
459

    
460
void
461
rt_prune_all(void)
462
{
463
  rtable *t;
464

    
465
  WALK_LIST(t, routing_tables)
466
    rt_prune(t);
467
}
468

    
469
void
470
rt_preconfig(struct config *c)
471
{
472
  struct symbol *s = cf_find_symbol("master");
473
  struct rtable_config *r = cfg_allocz(sizeof(struct rtable_config));
474

    
475
  cf_define_symbol(s, SYM_TABLE, r);
476
  r->name = s->name;
477
  init_list(&c->tables);
478
  add_tail(&c->tables, &r->n);
479
  c->master_rtc = r;
480
}
481

    
482
void
483
rt_commit(struct config *c)
484
{
485
  struct rtable_config *r;
486

    
487
  WALK_LIST(r, c->tables)
488
    {
489
      rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
490
      rt_setup(rt_table_pool, t, r->name);
491
      add_tail(&routing_tables, &t->n);
492
      r->table = t;
493
    }
494
}
495

    
496
/*
497
 *  CLI commands
498
 */
499

    
500
static void
501
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d)
502
{
503
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH];
504
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
505
  rta *a = e->attrs;
506

    
507
  switch (a->dest)
508
    {
509
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
510
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
511
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
512
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
513
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
514
    default:                bsprintf(via, "???");
515
    }
516
  tm_format_reltime(tm, e->lastmod);
517
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
518
    bsprintf(from, " from %I", a->from);
519
  else
520
    from[0] = 0;
521
  if (a->proto->proto->get_route_info)
522
    a->proto->proto->get_route_info(e, info);
523
  else
524
    bsprintf(info, " (%d)", e->pref);
525
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
526
  if (d->verbose)
527
    {
528
      rta_show(c, a);
529
      if (a->proto->proto->show_route_data)
530
        a->proto->proto->show_route_data(e);
531
    }
532
}
533

    
534
static void
535
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
536
{
537
  rte *e, *ee;
538
  byte ia[STD_ADDRESS_P_LENGTH+8];
539

    
540
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
541
  for(e=n->routes; e; e=e->next)
542
    {
543
      struct ea_list *tmpa = NULL;
544
      ee = e;
545
      rte_update_lock();                /* We use the update buffer for filtering */
546
      if (d->filter == FILTER_ACCEPT || f_run(d->filter, &ee, &tmpa, rte_update_pool) <= F_ACCEPT)
547
        {
548
          rt_show_rte(c, ia, e, d);
549
          ia[0] = 0;
550
        }
551
      if (e != ee)
552
        rte_free(ee);
553
      rte_update_unlock();
554
    }
555
}
556

    
557
static void
558
rt_show_cont(struct cli *c)
559
{
560
  struct rt_show_data *d = c->rover;
561
  unsigned max = 1;                        /* FIXME: After some debugging, increase to reasonable amount */
562
  struct fib *fib = &d->table->fib;
563
  struct fib_iterator *it = &d->fit;
564

    
565
  FIB_ITERATE_START(fib, it, f)
566
    {
567
      net *n = (net *) f;
568
      if (!max--)
569
        {
570
          FIB_ITERATE_PUT(it, f);
571
          return;
572
        }
573
      rt_show_net(c, n, d);
574
    }
575
  FIB_ITERATE_END(f);
576
  cli_printf(c, 0, "");
577
  c->cont = c->cleanup = NULL;
578
}
579

    
580
static void
581
rt_show_cleanup(struct cli *c)
582
{
583
  struct rt_show_data *d = c->rover;
584

    
585
  /* Unlink the iterator */
586
  fit_get(&d->table->fib, &d->fit);
587
}
588

    
589
void
590
rt_show(struct rt_show_data *d)
591
{
592
  struct rtable_config *tc;
593
  net *n;
594

    
595
  if (d->pxlen == 256)
596
    {
597
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
598
      this_cli->cont = rt_show_cont;
599
      this_cli->cleanup = rt_show_cleanup;
600
      this_cli->rover = d;
601
    }
602
  else
603
    {
604
      n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
605
      if (n)
606
        {
607
          rt_show_net(this_cli, n, d);
608
          cli_msg(0, "");
609
        }
610
      else
611
        cli_msg(8001, "Network not in table");
612
    }
613
}