Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 2c9033af

History | View | Annotate | Download (44.5 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
pool *rt_table_pool;
47

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

    
51
static list routing_tables;
52

    
53
static void rt_format_via(rte *e, byte *via);
54
static void rt_free_hostcache(rtable *tab);
55
static void rt_notify_hostcache(rtable *tab, net *net);
56
static void rt_update_hostcache(rtable *tab);
57
static void rt_next_hop_update(rtable *tab);
58
static void rt_prune(rtable *tab);
59

    
60
static inline void rt_schedule_gc(rtable *tab);
61

    
62
/* Like fib_route(), but skips empty net entries */
63
static net *
64
net_route(rtable *tab, ip_addr a, int len)
65
{
66
  ip_addr a0;
67
  net *n;
68

    
69
  while (len >= 0)
70
    {
71
      a0 = ipa_and(a, ipa_mkmask(len));
72
      n = fib_find(&tab->fib, &a0, len);
73
      if (n && n->routes)
74
        return n;
75
      len--;
76
    }
77
  return NULL;
78
}
79

    
80
static void
81
rte_init(struct fib_node *N)
82
{
83
  net *n = (net *) N;
84

    
85
  N->flags = 0;
86
  n->routes = NULL;
87
}
88

    
89
/**
90
 * rte_find - find a route
91
 * @net: network node
92
 * @p: protocol
93
 *
94
 * The rte_find() function returns a route for destination @net
95
 * which belongs has been defined by protocol @p.
96
 */
97
rte *
98
rte_find(net *net, struct proto *p)
99
{
100
  rte *e = net->routes;
101

    
102
  while (e && e->attrs->proto != p)
103
    e = e->next;
104
  return e;
105
}
106

    
107
/**
108
 * rte_get_temp - get a temporary &rte
109
 * @a: attributes to assign to the new route (a &rta; in case it's
110
 * un-cached, rte_update() will create a cached copy automatically)
111
 *
112
 * Create a temporary &rte and bind it with the attributes @a.
113
 * Also set route preference to the default preference set for
114
 * the protocol.
115
 */
116
rte *
117
rte_get_temp(rta *a)
118
{
119
  rte *e = sl_alloc(rte_slab);
120

    
121
  e->attrs = a;
122
  e->flags = 0;
123
  e->pref = a->proto->preference;
124
  return e;
125
}
126

    
127
rte *
128
rte_do_cow(rte *r)
129
{
130
  rte *e = sl_alloc(rte_slab);
131

    
132
  memcpy(e, r, sizeof(rte));
133
  e->attrs = rta_clone(r->attrs);
134
  e->flags = 0;
135
  return e;
136
}
137

    
138
static int                                /* Actually better or at least as good as */
139
rte_better(rte *new, rte *old)
140
{
141
  int (*better)(rte *, rte *);
142

    
143
  if (!old)
144
    return 1;
145
  if (new->pref > old->pref)
146
    return 1;
147
  if (new->pref < old->pref)
148
    return 0;
149
  if (new->attrs->proto->proto != old->attrs->proto->proto)
150
    {
151
      /*
152
       *  If the user has configured protocol preferences, so that two different protocols
153
       *  have the same preference, try to break the tie by comparing addresses. Not too
154
       *  useful, but keeps the ordering of routes unambiguous.
155
       */
156
      return new->attrs->proto->proto > old->attrs->proto->proto;
157
    }
158
  if (better = new->attrs->proto->rte_better)
159
    return better(new, old);
160
  return 0;
161
}
162

    
163
static void
164
rte_trace(struct proto *p, rte *e, int dir, char *msg)
165
{
166
  byte via[STD_ADDRESS_P_LENGTH+32];
167

    
168
  rt_format_via(e, via);
169
  log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
170
}
171

    
172
static inline void
173
rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg)
174
{
175
  if (p->debug & flag)
176
    rte_trace(p, e, '>', msg);
177
}
178

    
179
static inline void
180
rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg)
181
{
182
  if (p->debug & flag)
183
    rte_trace(p, e, '<', msg);
184
}
185

    
186
static inline void
187
do_rte_announce(struct announce_hook *a, int type UNUSED, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
188
{
189
  struct proto *p = a->proto;
190
  struct filter *filter = p->out_filter;
191
  struct proto_stats *stats = &p->stats;
192
  rte *new0 = new;
193
  rte *old0 = old;
194
  int ok;
195

    
196
#ifdef CONFIG_PIPE
197
  /* The secondary direction of the pipe */
198
  if (proto_is_pipe(p) && (p->table != a->table))
199
    {
200
      filter = p->in_filter;
201
      stats = pipe_get_peer_stats(p);
202
    }
203
#endif
204

    
205
  if (new)
206
    {
207
      stats->exp_updates_received++;
208

    
209
      char *drop_reason = NULL;
210
      if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
211
        {
212
          stats->exp_updates_rejected++;
213
          drop_reason = "rejected by protocol";
214
        }
215
      else if (ok)
216
        rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
217
      else if ((filter == FILTER_REJECT) ||
218
               (filter && f_run(filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
219
        {
220
          stats->exp_updates_filtered++;
221
          drop_reason = "filtered out";
222
        }
223
      if (drop_reason)
224
        {
225
          rte_trace_out(D_FILTERS, p, new, drop_reason);
226
          if (new != new0)
227
            rte_free(new);
228
          new = NULL;
229
        }
230
    }
231
  else
232
    stats->exp_withdraws_received++;
233

    
234
  /*
235
   * This is a tricky part - we don't know whether route 'old' was
236
   * exported to protocol 'p' or was filtered by the export filter.
237
   * We try tu run the export filter to know this to have a correct
238
   * value in 'old' argument of rte_update (and proper filter value)
239
   *
240
   * FIXME - this is broken because 'configure soft' may change
241
   * filters but keep routes. Refeed is expected to be called after
242
   * change of the filters and with old == new, therefore we do not
243
   * even try to run the filter on an old route, This may lead to 
244
   * 'spurious withdraws' but ensure that there are no 'missing
245
   * withdraws'.
246
   *
247
   * This is not completely safe as there is a window between
248
   * reconfiguration and the end of refeed - if a newly filtered
249
   * route disappears during this period, proper withdraw is not
250
   * sent (because old would be also filtered) and the route is
251
   * not refeeded (because it disappeared before that).
252
   */
253

    
254
  if (old && !refeed)
255
    {
256
      if (filter == FILTER_REJECT)
257
        old = NULL;
258
      else
259
        {
260
          ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
261
          ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
262
          if (ok < 0 || (!ok && filter && f_run(filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
263
            {
264
              if (old != old0)
265
                rte_free(old);
266
              old = NULL;
267
            }
268
        }
269
    }
270

    
271
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
272
  if (!new && !old)
273
    return;
274

    
275
  if (new)
276
    stats->exp_updates_accepted++;
277
  else
278
    stats->exp_withdraws_accepted++;
279

    
280
  /* Hack: We do not decrease exp_routes during refeed, we instead
281
     reset exp_routes at the start of refeed. */
282
  if (new)
283
    stats->exp_routes++;
284
  if (old && !refeed)
285
    stats->exp_routes--;
286

    
287
  if (p->debug & D_ROUTES)
288
    {
289
      if (new && old)
290
        rte_trace_out(D_ROUTES, p, new, "replaced");
291
      else if (new)
292
        rte_trace_out(D_ROUTES, p, new, "added");
293
      else if (old)
294
        rte_trace_out(D_ROUTES, p, old, "removed");
295
    }
296
  if (!new)
297
    p->rt_notify(p, a->table, net, NULL, old, NULL);
298
  else if (tmpa)
299
    {
300
      ea_list *t = tmpa;
301
      while (t->next)
302
        t = t->next;
303
      t->next = new->attrs->eattrs;
304
      p->rt_notify(p, a->table, net, new, old, tmpa);
305
      t->next = NULL;
306
    }
307
  else
308
    p->rt_notify(p, a->table, net, new, old, new->attrs->eattrs);
309
  if (new && new != new0)        /* Discard temporary rte's */
310
    rte_free(new);
311
  if (old && old != old0)
312
    rte_free(old);
313
}
314

    
315
/**
316
 * rte_announce - announce a routing table change
317
 * @tab: table the route has been added to
318
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
319
 * @net: network in question
320
 * @new: the new route to be announced
321
 * @old: the previous route for the same network
322
 * @tmpa: a list of temporary attributes belonging to the new route
323
 *
324
 * This function gets a routing table update and announces it
325
 * to all protocols that acccepts given type of route announcement
326
 * and are connected to the same table by their announcement hooks.
327
 *
328
 * Route announcement of type RA_OPTIMAL si generated when optimal
329
 * route (in routing table @tab) changes. In that case @old stores the
330
 * old optimal route.
331
 *
332
 * Route announcement of type RA_ANY si generated when any route (in
333
 * routing table @tab) changes In that case @old stores the old route
334
 * from the same protocol.
335
 *
336
 * For each appropriate protocol, we first call its import_control()
337
 * hook which performs basic checks on the route (each protocol has a
338
 * right to veto or force accept of the route before any filter is
339
 * asked) and adds default values of attributes specific to the new
340
 * protocol (metrics, tags etc.).  Then it consults the protocol's
341
 * export filter and if it accepts the route, the rt_notify() hook of
342
 * the protocol gets called.
343
 */
344
static void
345
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, ea_list *tmpa)
346
{
347
  struct announce_hook *a;
348

    
349
  if (type == RA_OPTIMAL)
350
    {
351
      if (new)
352
        new->attrs->proto->stats.pref_routes++;
353
      if (old)
354
        old->attrs->proto->stats.pref_routes--;
355

    
356
      if (tab->hostcache)
357
        rt_notify_hostcache(tab, net);
358
    }
359

    
360
  WALK_LIST(a, tab->hooks)
361
    {
362
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
363
      if (a->proto->accept_ra_types == type)
364
        do_rte_announce(a, type, net, new, old, tmpa, 0);
365
    }
366
}
367

    
368

    
369
static inline int
370
rte_validate(rte *e)
371
{
372
  int c;
373
  net *n = e->net;
374

    
375
  if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
376
    {
377
      log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
378
          n->n.prefix, n->n.pxlen, e->sender->name);
379
      return 0;
380
    }
381

    
382
  c = ipa_classify_net(n->n.prefix);
383
  if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
384
    {
385
      log(L_WARN "Ignoring bogus route %I/%d received via %s",
386
          n->n.prefix, n->n.pxlen, e->sender->name);
387
      return 0;
388
    }
389

    
390
  return 1;
391
}
392

    
393
/**
394
 * rte_free - delete a &rte
395
 * @e: &rte to be deleted
396
 *
397
 * rte_free() deletes the given &rte from the routing table it's linked to.
398
 */
399
void
400
rte_free(rte *e)
401
{
402
  if (e->attrs->aflags & RTAF_CACHED)
403
    rta_free(e->attrs);
404
  sl_free(rte_slab, e);
405
}
406

    
407
static inline void
408
rte_free_quick(rte *e)
409
{
410
  rta_free(e->attrs);
411
  sl_free(rte_slab, e);
412
}
413

    
414
static int
415
rte_same(rte *x, rte *y)
416
{
417
  return
418
    x->attrs == y->attrs &&
419
    x->flags == y->flags &&
420
    x->pflags == y->pflags &&
421
    x->pref == y->pref &&
422
    (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
423
}
424

    
425
static void
426
rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
427
{
428
  struct proto_stats *stats = &p->stats;
429
  rte *old_best = net->routes;
430
  rte *old = NULL;
431
  rte **k, *r, *s;
432

    
433
#ifdef CONFIG_PIPE
434
  if (proto_is_pipe(p) && (p->table == table))
435
    stats = pipe_get_peer_stats(p);
436
#endif
437

    
438
  k = &net->routes;                        /* Find and remove original route from the same protocol */
439
  while (old = *k)
440
    {
441
      if (old->attrs->proto == src)
442
        {
443
          /* If there is the same route in the routing table but from
444
           * a different sender, then there are two paths from the
445
           * source protocol to this routing table through transparent
446
           * pipes, which is not allowed.
447
           *
448
           * We log that and ignore the route. If it is withdraw, we
449
           * ignore it completely (there might be 'spurious withdraws',
450
           * see FIXME in do_rte_announce())
451
           */
452
          if (old->sender != p)
453
            {
454
              if (new)
455
                {
456
                  log(L_ERR "Pipe collision detected when sending %I/%d to table %s",
457
                      net->n.prefix, net->n.pxlen, table->name);
458
                  rte_free_quick(new);
459
                }
460
              return;
461
            }
462

    
463
          if (new && rte_same(old, new))
464
            {
465
              /* No changes, ignore the new route */
466
              stats->imp_updates_ignored++;
467
              rte_trace_in(D_ROUTES, p, new, "ignored");
468
              rte_free_quick(new);
469
#ifdef CONFIG_RIP
470
              /* lastmod is used internally by RIP as the last time
471
                 when the route was received. */
472
              if (src->proto == &proto_rip)
473
                old->lastmod = now;
474
#endif
475
              return;
476
            }
477
          *k = old->next;
478
          break;
479
        }
480
      k = &old->next;
481
    }
482

    
483
  if (!old && !new)
484
    {
485
      stats->imp_withdraws_ignored++;
486
      return;
487
    }
488

    
489
  if (new)
490
    stats->imp_updates_accepted++;
491
  else
492
    stats->imp_withdraws_accepted++;
493

    
494
  if (new)
495
    stats->imp_routes++;
496
  if (old)
497
    stats->imp_routes--;
498

    
499
  rte_announce(table, RA_ANY, net, new, old, tmpa);
500

    
501
  if (new && rte_better(new, old_best))
502
    {
503
      /* The first case - the new route is cleary optimal, we link it
504
         at the first position and announce it */
505

    
506
      rte_trace_in(D_ROUTES, p, new, "added [best]");
507
      rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
508
      new->next = net->routes;
509
      net->routes = new;
510
    }
511
  else if (old == old_best)
512
    {
513
      /* The second case - the old best route disappeared, we add the
514
         new route (if we have any) to the list (we don't care about
515
         position) and then we elect the new optimal route and relink
516
         that route at the first position and announce it. New optimal
517
         route might be NULL if there is no more routes */
518

    
519
      /* Add the new route to the list */
520
      if (new)
521
        {
522
          rte_trace_in(D_ROUTES, p, new, "added");
523
          new->next = net->routes;
524
          net->routes = new;
525
        }
526

    
527
      /* Find new optimal route */
528
      r = NULL;
529
      for (s=net->routes; s; s=s->next)
530
        if (rte_better(s, r))
531
          r = s;
532

    
533
      /* Announce optimal route */
534
      rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
535

    
536
      /* And relink it (if there is any) */
537
      if (r)
538
        {
539
          k = &net->routes;
540
          while (s = *k)
541
            {
542
              if (s == r)
543
                {
544
                  *k = r->next;
545
                  break;
546
                }
547
              k = &s->next;
548
            }
549
          r->next = net->routes;
550
          net->routes = r;
551
        }
552
      else if (table->gc_counter++ >= table->config->gc_max_ops &&
553
               table->gc_time + table->config->gc_min_time <= now)
554
        rt_schedule_gc(table);
555
    }
556
  else if (new)
557
    {
558
      /* The third case - the new route is not better than the old
559
         best route (therefore old_best != NULL) and the old best
560
         route was not removed (therefore old_best == net->routes).
561
         We just link the new route after the old best route. */
562

    
563
      ASSERT(net->routes != NULL);
564
      new->next = net->routes->next;
565
      net->routes->next = new;
566
      rte_trace_in(D_ROUTES, p, new, "added");
567
    }
568

    
569
  /* Log the route removal */
570
  if (!new && old && (p->debug & D_ROUTES))
571
    {
572
      if (old != old_best)
573
        rte_trace_in(D_ROUTES, p, old, "removed");
574
      else if (net->routes)
575
        rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
576
      else
577
        rte_trace_in(D_ROUTES, p, old, "removed [sole]");
578
    }
579

    
580
  if (old)
581
    {
582
      if (p->rte_remove)
583
        p->rte_remove(net, old);
584
      rte_free_quick(old);
585
    }
586
  if (new)
587
    {
588
      new->lastmod = now;
589
      if (p->rte_insert)
590
        p->rte_insert(net, new);
591
    }
592
}
593

    
594
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
595

    
596
static inline void
597
rte_update_lock(void)
598
{
599
  rte_update_nest_cnt++;
600
}
601

    
602
static inline void
603
rte_update_unlock(void)
604
{
605
  if (!--rte_update_nest_cnt)
606
    lp_flush(rte_update_pool);
607
}
608

    
609
/**
610
 * rte_update - enter a new update to a routing table
611
 * @table: table to be updated
612
 * @net: network node
613
 * @p: protocol submitting the update
614
 * @src: protocol originating the update
615
 * @new: a &rte representing the new route or %NULL for route removal.
616
 *
617
 * This function is called by the routing protocols whenever they discover
618
 * a new route or wish to update/remove an existing route. The right announcement
619
 * sequence is to build route attributes first (either un-cached with @aflags set
620
 * to zero or a cached one using rta_lookup(); in this case please note that
621
 * you need to increase the use count of the attributes yourself by calling
622
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
623
 * the appropriate data and finally submit the new &rte by calling rte_update().
624
 *
625
 * @src specifies the protocol that originally created the route and the meaning
626
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
627
 * same value as @new->attrs->proto. @p specifies the protocol that called
628
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
629
 * stores @p in @new->sender;
630
 *
631
 * When rte_update() gets any route, it automatically validates it (checks,
632
 * whether the network and next hop address are valid IP addresses and also
633
 * whether a normal routing protocol doesn't try to smuggle a host or link
634
 * scope route to the table), converts all protocol dependent attributes stored
635
 * in the &rte to temporary extended attributes, consults import filters of the
636
 * protocol to see if the route should be accepted and/or its attributes modified,
637
 * stores the temporary attributes back to the &rte.
638
 *
639
 * Now, having a "public" version of the route, we
640
 * automatically find any old route defined by the protocol @src
641
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
642
 * recalculate the optimal route for this destination and finally broadcast
643
 * the change (if any) to all routing protocols by calling rte_announce().
644
 *
645
 * All memory used for attribute lists and other temporary allocations is taken
646
 * from a special linear pool @rte_update_pool and freed when rte_update()
647
 * finishes.
648
 */
649

    
650
void
651
rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
652
{
653
  ea_list *tmpa = NULL;
654
  struct proto_stats *stats = &p->stats;
655

    
656
#ifdef CONFIG_PIPE
657
  if (proto_is_pipe(p) && (p->table == table))
658
    stats = pipe_get_peer_stats(p);
659
#endif
660

    
661
  rte_update_lock();
662
  if (new)
663
    {
664
      new->sender = p;
665
      struct filter *filter = p->in_filter;
666

    
667
      /* Do not filter routes going through the pipe, 
668
         they are filtered in the export filter only. */
669
#ifdef CONFIG_PIPE
670
      if (proto_is_pipe(p))
671
        filter = FILTER_ACCEPT;
672
#endif
673

    
674
      stats->imp_updates_received++;
675
      if (!rte_validate(new))
676
        {
677
          rte_trace_in(D_FILTERS, p, new, "invalid");
678
          stats->imp_updates_invalid++;
679
          goto drop;
680
        }
681
      if (filter == FILTER_REJECT)
682
        {
683
          stats->imp_updates_filtered++;
684
          rte_trace_in(D_FILTERS, p, new, "filtered out");
685
          goto drop;
686
        }
687
      if (src->make_tmp_attrs)
688
        tmpa = src->make_tmp_attrs(new, rte_update_pool);
689
      if (filter)
690
        {
691
          ea_list *old_tmpa = tmpa;
692
          int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
693
          if (fr > F_ACCEPT)
694
            {
695
              stats->imp_updates_filtered++;
696
              rte_trace_in(D_FILTERS, p, new, "filtered out");
697
              goto drop;
698
            }
699
          if (tmpa != old_tmpa && src->store_tmp_attrs)
700
            src->store_tmp_attrs(new, tmpa);
701
        }
702
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
703
        new->attrs = rta_lookup(new->attrs);
704
      new->flags |= REF_COW;
705
    }
706
  else
707
    stats->imp_withdraws_received++;
708

    
709
  rte_recalculate(table, net, p, src, new, tmpa);
710
  rte_update_unlock();
711
  return;
712

    
713
drop:
714
  rte_free(new);
715
  rte_recalculate(table, net, p, src, NULL, NULL);
716
  rte_update_unlock();
717
}
718

    
719
/* Independent call to rte_announce(), used from next hop
720
   recalculation, outside of rte_update(). new must be non-NULL */
721
static inline void 
722
rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old)
723
{
724
  struct proto *src;
725
  ea_list *tmpa;
726

    
727
  rte_update_lock();
728
  src = new->attrs->proto;
729
  tmpa = src->make_tmp_attrs ? src->make_tmp_attrs(new, rte_update_pool) : NULL;
730
  rte_announce(tab, type, n, new, old, tmpa);
731
  rte_update_unlock();
732
}
733

    
734
void
735
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
736
{
737
  rte_update_lock();
738
  rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
739
  rte_update_unlock();
740
}
741

    
742
/**
743
 * rte_dump - dump a route
744
 * @e: &rte to be dumped
745
 *
746
 * This functions dumps contents of a &rte to debug output.
747
 */
748
void
749
rte_dump(rte *e)
750
{
751
  net *n = e->net;
752
  if (n)
753
    debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
754
  else
755
    debug("??? ");
756
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
757
  rta_dump(e->attrs);
758
  if (e->attrs->proto->proto->dump_attrs)
759
    e->attrs->proto->proto->dump_attrs(e);
760
  debug("\n");
761
}
762

    
763
/**
764
 * rt_dump - dump a routing table
765
 * @t: routing table to be dumped
766
 *
767
 * This function dumps contents of a given routing table to debug output.
768
 */
769
void
770
rt_dump(rtable *t)
771
{
772
  rte *e;
773
  net *n;
774
  struct announce_hook *a;
775

    
776
  debug("Dump of routing table <%s>\n", t->name);
777
#ifdef DEBUGGING
778
  fib_check(&t->fib);
779
#endif
780
  FIB_WALK(&t->fib, fn)
781
    {
782
      n = (net *) fn;
783
      for(e=n->routes; e; e=e->next)
784
        rte_dump(e);
785
    }
786
  FIB_WALK_END;
787
  WALK_LIST(a, t->hooks)
788
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
789
  debug("\n");
790
}
791

    
792
/**
793
 * rt_dump_all - dump all routing tables
794
 *
795
 * This function dumps contents of all routing tables to debug output.
796
 */
797
void
798
rt_dump_all(void)
799
{
800
  rtable *t;
801

    
802
  WALK_LIST(t, routing_tables)
803
    rt_dump(t);
804
}
805

    
806
static inline void
807
rt_schedule_gc(rtable *tab)
808
{
809
  if (tab->gc_scheduled)
810
    return;
811

    
812
  tab->gc_scheduled = 1;
813
  ev_schedule(tab->rt_event);
814
}
815

    
816
static inline void
817
rt_schedule_hcu(rtable *tab)
818
{
819
  if (tab->hcu_scheduled)
820
    return;
821

    
822
  tab->hcu_scheduled = 1;
823
  ev_schedule(tab->rt_event);
824
}
825

    
826
static inline void
827
rt_schedule_nhu(rtable *tab)
828
{
829
  if (tab->nhu_state == 0)
830
    ev_schedule(tab->rt_event);
831

    
832
  /* state change 0->1, 2->3 */
833
  tab->nhu_state |= 1;
834
}
835

    
836
static void
837
rt_event(void *ptr)
838
{
839
  rtable *tab = ptr;
840

    
841
  if (tab->hcu_scheduled)
842
    rt_update_hostcache(tab);
843

    
844
  if (tab->nhu_state)
845
    rt_next_hop_update(tab);
846

    
847
  if (tab->gc_scheduled)
848
    rt_prune(tab);
849
}
850

    
851
void
852
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
853
{
854
  bzero(t, sizeof(*t));
855
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
856
  t->name = name;
857
  t->config = cf;
858
  init_list(&t->hooks);
859
  if (cf)
860
    {
861
      t->rt_event = ev_new(p);
862
      t->rt_event->hook = rt_event;
863
      t->rt_event->data = t;
864
      t->gc_time = now;
865
    }
866
}
867

    
868
/**
869
 * rt_init - initialize routing tables
870
 *
871
 * This function is called during BIRD startup. It initializes the
872
 * routing table module.
873
 */
874
void
875
rt_init(void)
876
{
877
  rta_init();
878
  rt_table_pool = rp_new(&root_pool, "Routing tables");
879
  rte_update_pool = lp_new(rt_table_pool, 4080);
880
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
881
  init_list(&routing_tables);
882
}
883

    
884
/**
885
 * rt_prune - prune a routing table
886
 * @tab: routing table to be pruned
887
 *
888
 * This function is called whenever a protocol shuts down. It scans
889
 * the routing table and removes all routes belonging to inactive
890
 * protocols and also stale network entries.
891
 */
892
static void
893
rt_prune(rtable *tab)
894
{
895
  struct fib_iterator fit;
896
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
897

    
898
  DBG("Pruning route table %s\n", tab->name);
899
#ifdef DEBUGGING
900
  fib_check(&tab->fib);
901
#endif
902
  FIB_ITERATE_INIT(&fit, &tab->fib);
903
again:
904
  FIB_ITERATE_START(&tab->fib, &fit, f)
905
    {
906
      net *n = (net *) f;
907
      rte *e;
908
      ncnt++;
909
    rescan:
910
      for (e=n->routes; e; e=e->next, rcnt++)
911
        if (e->sender->core_state != FS_HAPPY &&
912
            e->sender->core_state != FS_FEEDING)
913
          {
914
            rte_discard(tab, e);
915
            rdel++;
916
            goto rescan;
917
          }
918
      if (!n->routes)                /* Orphaned FIB entry? */
919
        {
920
          FIB_ITERATE_PUT(&fit, f);
921
          fib_delete(&tab->fib, f);
922
          ndel++;
923
          goto again;
924
        }
925
    }
926
  FIB_ITERATE_END(f);
927
  DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
928
#ifdef DEBUGGING
929
  fib_check(&tab->fib);
930
#endif
931
  tab->gc_counter = 0;
932
  tab->gc_time = now;
933
  tab->gc_scheduled = 0;
934
}
935

    
936
/**
937
 * rt_prune_all - prune all routing tables
938
 *
939
 * This function calls rt_prune() for all known routing tables.
940
 */
941
void
942
rt_prune_all(void)
943
{
944
  rtable *t;
945

    
946
  WALK_LIST(t, routing_tables)
947
    rt_prune(t);
948
}
949

    
950
void
951
rt_preconfig(struct config *c)
952
{
953
  struct symbol *s = cf_find_symbol("master");
954

    
955
  init_list(&c->tables);
956
  c->master_rtc = rt_new_table(s);
957
}
958

    
959

    
960
/* 
961
 * Some functions for handing internal next hop updates
962
 * triggered by rt_schedule_nhu().
963
 */
964

    
965
static inline int
966
hostentry_diff(struct hostentry *he, struct iface *iface, ip_addr gw,
967
               byte dest, u32 igp_metric)
968
{
969
  return (he->iface != iface) || !ipa_equal(he->gw, gw) ||
970
    (he->dest != dest) || (he->igp_metric != igp_metric);
971
}
972

    
973
static inline int
974
rta_next_hop_outdated(rta *a)
975
{
976
  struct hostentry *he = a->hostentry;
977
  return he && hostentry_diff(he, a->iface, a->gw, a->dest, a->igp_metric);
978
}
979

    
980
static inline void
981
rta_apply_hostentry(rta *a, struct hostentry *he)
982
{
983
  a->hostentry = he;
984
  a->iface = he->iface;
985
  a->gw = he->gw;
986
  a->dest = he->dest;
987
  a->igp_metric = he->igp_metric;
988
}
989

    
990
static inline rte *
991
rt_next_hop_update_rte(rtable *tab, rte *old)
992
{
993
  rta a;
994
  memcpy(&a, old->attrs, sizeof(rta));
995
  rta_apply_hostentry(&a, old->attrs->hostentry);
996
  a.aflags = 0;
997

    
998
  rte *e = sl_alloc(rte_slab);
999
  memcpy(e, old, sizeof(rte));
1000
  e->attrs = rta_lookup(&a);
1001

    
1002
  return e;
1003
}
1004

    
1005
static inline int
1006
rt_next_hop_update_net(rtable *tab, net *n)
1007
{
1008
  rte **k, *e, *new, *old_best, **new_best;
1009
  int count = 0;
1010
  int free_old_best = 0;
1011

    
1012
  old_best = n->routes;
1013
  if (!old_best)
1014
    return 0;
1015

    
1016
  new_best = NULL;
1017

    
1018
  for (k = &n->routes; e = *k; k = &e->next)
1019
    {
1020
      if (rta_next_hop_outdated(e->attrs))
1021
        {
1022
          new = rt_next_hop_update_rte(tab, e);
1023
          *k = new;
1024

    
1025
          rte_announce_i(tab, RA_ANY, n, new, e);
1026
          rte_trace_in(D_ROUTES, new->sender, new, "updated");
1027

    
1028
          if (e != old_best)
1029
            rte_free_quick(e);
1030
          else /* Freeing of the old best rte is postponed */
1031
            free_old_best = 1;
1032

    
1033
          e = new;
1034
          count++;
1035
        }
1036

    
1037
      if (!new_best || rte_better(e, *new_best))
1038
        new_best = k;
1039
    }
1040

    
1041
  /* Relink the new best route to the first position */
1042
  new = *new_best;
1043
  if (new != n->routes)
1044
    {
1045
      *new_best = new->next;
1046
      new->next = n->routes;
1047
      n->routes = new;
1048
    }
1049

    
1050
  /* Announce the new best route */
1051
  if (new != old_best)
1052
    {
1053
      rte_announce_i(tab, RA_OPTIMAL, n, new, old_best);
1054
      rte_trace_in(D_ROUTES, new->sender, new, "updated [best]");
1055
    }
1056

    
1057
   if (free_old_best)
1058
    rte_free_quick(old_best);
1059

    
1060
  return count;
1061
}
1062

    
1063
static void
1064
rt_next_hop_update(rtable *tab)
1065
{
1066
  struct fib_iterator *fit = &tab->nhu_fit;
1067
  int max_feed = 32;
1068

    
1069
  if (tab->nhu_state == 0)
1070
    return;
1071

    
1072
  if (tab->nhu_state == 1)
1073
    {
1074
      FIB_ITERATE_INIT(fit, &tab->fib);
1075
      tab->nhu_state = 2;
1076
    }
1077

    
1078
  FIB_ITERATE_START(&tab->fib, fit, fn)
1079
    {
1080
      if (max_feed <= 0)
1081
        {
1082
          FIB_ITERATE_PUT(fit, fn);
1083
          ev_schedule(tab->rt_event);
1084
          return;
1085
        }
1086
      max_feed -= rt_next_hop_update_net(tab, (net *) fn);
1087
    }
1088
  FIB_ITERATE_END(fn);
1089

    
1090
  /* state change 2->0, 3->1 */
1091
  tab->nhu_state &= 1;
1092

    
1093
  if (tab->nhu_state > 0)
1094
    ev_schedule(tab->rt_event);
1095
}
1096

    
1097

    
1098
struct rtable_config *
1099
rt_new_table(struct symbol *s)
1100
{
1101
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
1102

    
1103
  cf_define_symbol(s, SYM_TABLE, c);
1104
  c->name = s->name;
1105
  add_tail(&new_config->tables, &c->n);
1106
  c->gc_max_ops = 1000;
1107
  c->gc_min_time = 5;
1108
  return c;
1109
}
1110

    
1111
/**
1112
 * rt_lock_table - lock a routing table
1113
 * @r: routing table to be locked
1114
 *
1115
 * Lock a routing table, because it's in use by a protocol,
1116
 * preventing it from being freed when it gets undefined in a new
1117
 * configuration.
1118
 */
1119
void
1120
rt_lock_table(rtable *r)
1121
{
1122
  r->use_count++;
1123
}
1124

    
1125
/**
1126
 * rt_unlock_table - unlock a routing table
1127
 * @r: routing table to be unlocked
1128
 *
1129
 * Unlock a routing table formerly locked by rt_lock_table(),
1130
 * that is decrease its use count and delete it if it's scheduled
1131
 * for deletion by configuration changes.
1132
 */
1133
void
1134
rt_unlock_table(rtable *r)
1135
{
1136
  if (!--r->use_count && r->deleted)
1137
    {
1138
      struct config *conf = r->deleted;
1139
      DBG("Deleting routing table %s\n", r->name);
1140
      if (r->hostcache)
1141
        rt_free_hostcache(r);
1142
      rem_node(&r->n);
1143
      fib_free(&r->fib);
1144
      rfree(r->rt_event);
1145
      mb_free(r);
1146
      config_del_obstacle(conf);
1147
    }
1148
}
1149

    
1150
/**
1151
 * rt_commit - commit new routing table configuration
1152
 * @new: new configuration
1153
 * @old: original configuration or %NULL if it's boot time config
1154
 *
1155
 * Scan differences between @old and @new configuration and modify
1156
 * the routing tables according to these changes. If @new defines a
1157
 * previously unknown table, create it, if it omits a table existing
1158
 * in @old, schedule it for deletion (it gets deleted when all protocols
1159
 * disconnect from it by calling rt_unlock_table()), if it exists
1160
 * in both configurations, leave it unchanged.
1161
 */
1162
void
1163
rt_commit(struct config *new, struct config *old)
1164
{
1165
  struct rtable_config *o, *r;
1166

    
1167
  DBG("rt_commit:\n");
1168
  if (old)
1169
    {
1170
      WALK_LIST(o, old->tables)
1171
        {
1172
          rtable *ot = o->table;
1173
          if (!ot->deleted)
1174
            {
1175
              struct symbol *sym = cf_find_symbol(o->name);
1176
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
1177
                {
1178
                  DBG("\t%s: same\n", o->name);
1179
                  r = sym->def;
1180
                  r->table = ot;
1181
                  ot->name = r->name;
1182
                  ot->config = r;
1183
                }
1184
              else
1185
                {
1186
                  DBG("\t%s: deleted\n", o->name);
1187
                  ot->deleted = old;
1188
                  config_add_obstacle(old);
1189
                  rt_lock_table(ot);
1190
                  rt_unlock_table(ot);
1191
                }
1192
            }
1193
        }
1194
    }
1195

    
1196
  WALK_LIST(r, new->tables)
1197
    if (!r->table)
1198
      {
1199
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
1200
        DBG("\t%s: created\n", r->name);
1201
        rt_setup(rt_table_pool, t, r->name, r);
1202
        add_tail(&routing_tables, &t->n);
1203
        r->table = t;
1204
      }
1205
  DBG("\tdone\n");
1206
}
1207

    
1208
static inline void
1209
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
1210
{
1211
  struct proto *q = e->attrs->proto;
1212
  ea_list *tmpa;
1213

    
1214
  rte_update_lock();
1215
  tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
1216
  do_rte_announce(h, type, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding);
1217
  rte_update_unlock();
1218
}
1219

    
1220
/**
1221
 * rt_feed_baby - advertise routes to a new protocol
1222
 * @p: protocol to be fed
1223
 *
1224
 * This function performs one pass of advertisement of routes to a newly
1225
 * initialized protocol. It's called by the protocol code as long as it
1226
 * has something to do. (We avoid transferring all the routes in single
1227
 * pass in order not to monopolize CPU time.)
1228
 */
1229
int
1230
rt_feed_baby(struct proto *p)
1231
{
1232
  struct announce_hook *h;
1233
  struct fib_iterator *fit;
1234
  int max_feed = 256;
1235

    
1236
  if (!p->feed_ahook)                        /* Need to initialize first */
1237
    {
1238
      if (!p->ahooks)
1239
        return 1;
1240
      DBG("Announcing routes to new protocol %s\n", p->name);
1241
      p->feed_ahook = p->ahooks;
1242
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1243
      goto next_hook;
1244
    }
1245
  fit = p->feed_iterator;
1246

    
1247
again:
1248
  h = p->feed_ahook;
1249
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1250
    {
1251
      net *n = (net *) fn;
1252
      rte *e = n->routes;
1253
      if (max_feed <= 0)
1254
        {
1255
          FIB_ITERATE_PUT(fit, fn);
1256
          return 0;
1257
        }
1258

    
1259
      if (p->accept_ra_types == RA_OPTIMAL)
1260
        if (e)
1261
          {
1262
            if (p->core_state != FS_FEEDING)
1263
              return 1;  /* In the meantime, the protocol fell down. */
1264
            do_feed_baby(p, RA_OPTIMAL, h, n, e);
1265
            max_feed--;
1266
          }
1267

    
1268
      if (p->accept_ra_types == RA_ANY)
1269
        for(e = n->routes; e != NULL; e = e->next)
1270
          {
1271
            if (p->core_state != FS_FEEDING)
1272
              return 1;  /* In the meantime, the protocol fell down. */
1273
            do_feed_baby(p, RA_ANY, h, n, e);
1274
            max_feed--;
1275
          }
1276
    }
1277
  FIB_ITERATE_END(fn);
1278
  p->feed_ahook = h->next;
1279
  if (!p->feed_ahook)
1280
    {
1281
      mb_free(p->feed_iterator);
1282
      p->feed_iterator = NULL;
1283
      return 1;
1284
    }
1285

    
1286
next_hook:
1287
  h = p->feed_ahook;
1288
  FIB_ITERATE_INIT(fit, &h->table->fib);
1289
  goto again;
1290
}
1291

    
1292
/**
1293
 * rt_feed_baby_abort - abort protocol feeding
1294
 * @p: protocol
1295
 *
1296
 * This function is called by the protocol code when the protocol
1297
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1298
 * has finished.
1299
 */
1300
void
1301
rt_feed_baby_abort(struct proto *p)
1302
{
1303
  if (p->feed_ahook)
1304
    {
1305
      /* Unlink the iterator and exit */
1306
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1307
      p->feed_ahook = NULL;
1308
    }
1309
}
1310

    
1311

    
1312
static inline unsigned
1313
ptr_hash(void *ptr)
1314
{
1315
  uintptr_t p = (uintptr_t) ptr;
1316
  return p ^ (p << 8) ^ (p >> 16);
1317
}
1318

    
1319
static inline unsigned
1320
hc_hash(ip_addr a, rtable *dep)
1321
{
1322
  return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff;
1323
}
1324

    
1325
static inline void
1326
hc_insert(struct hostcache *hc, struct hostentry *he)
1327
{
1328
  unsigned int k = he->hash_key >> hc->hash_shift;
1329
  he->next = hc->hash_table[k];
1330
  hc->hash_table[k] = he;
1331
}
1332

    
1333
static inline void
1334
hc_remove(struct hostcache *hc, struct hostentry *he)
1335
{
1336
  struct hostentry **hep;
1337
  unsigned int k = he->hash_key >> hc->hash_shift;
1338

    
1339
  for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
1340
  *hep = he->next;
1341
}
1342

    
1343
#define HC_DEF_ORDER 10
1344
#define HC_HI_MARK *4
1345
#define HC_HI_STEP 2
1346
#define HC_HI_ORDER 16                        /* Must be at most 16 */
1347
#define HC_LO_MARK /5
1348
#define HC_LO_STEP 2
1349
#define HC_LO_ORDER 10
1350

    
1351
static void
1352
hc_alloc_table(struct hostcache *hc, unsigned order)
1353
{
1354
  unsigned hsize = 1 << order;
1355
  hc->hash_order = order;
1356
  hc->hash_shift = 16 - order;
1357
  hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
1358
  hc->hash_min = (order <= HC_LO_ORDER) ?  0 : (hsize HC_LO_MARK);
1359

    
1360
  hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
1361
}
1362

    
1363
static void
1364
hc_resize(struct hostcache *hc, unsigned new_order)
1365
{
1366
  unsigned old_size = 1 << hc->hash_order;
1367
  struct hostentry **old_table = hc->hash_table;
1368
  struct hostentry *he, *hen;
1369
  int i;
1370

    
1371
  hc_alloc_table(hc, new_order);
1372
  for (i = 0; i < old_size; i++)
1373
    for (he = old_table[i]; he != NULL; he=hen)
1374
      {
1375
        hen = he->next;
1376
        hc_insert(hc, he);
1377
      }
1378
  mb_free(old_table);
1379
}
1380

    
1381
static struct hostentry *
1382
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
1383
{
1384
  struct hostentry *he = sl_alloc(hc->slab);
1385

    
1386
  he->addr = a;
1387
  he->link = ll;
1388
  he->tab = dep;
1389
  he->hash_key = k;
1390
  he->uc = 0;
1391

    
1392
  add_tail(&hc->hostentries, &he->ln);
1393
  hc_insert(hc, he);
1394

    
1395
  hc->hash_items++;
1396
  if (hc->hash_items > hc->hash_max)
1397
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
1398

    
1399
  return he;
1400
}
1401

    
1402
static void
1403
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
1404
{
1405
  rem_node(&he->ln);
1406
  hc_remove(hc, he);
1407
  sl_free(hc->slab, he);
1408

    
1409
  hc->hash_items--;
1410
  if (hc->hash_items < hc->hash_min)
1411
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
1412
}
1413

    
1414
static void
1415
rt_init_hostcache(rtable *tab)
1416
{
1417
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
1418
  init_list(&hc->hostentries);
1419

    
1420
  hc->hash_items = 0;
1421
  hc_alloc_table(hc, HC_DEF_ORDER);
1422
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
1423

    
1424
  hc->lp = lp_new(rt_table_pool, 1008);
1425
  hc->trie = f_new_trie(hc->lp);
1426

    
1427
  tab->hostcache = hc;
1428
}
1429

    
1430
static void
1431
rt_free_hostcache(rtable *tab)
1432
{
1433
  struct hostcache *hc = tab->hostcache;
1434

    
1435
  node *n;
1436
  WALK_LIST(n, hc->hostentries)
1437
    {
1438
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
1439
      if (he->uc)
1440
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
1441
    }
1442

    
1443
  rfree(hc->slab);
1444
  rfree(hc->lp);
1445
  mb_free(hc->hash_table);
1446
  mb_free(hc);
1447
}
1448

    
1449
static void
1450
rt_notify_hostcache(rtable *tab, net *net)
1451
{
1452
  struct hostcache *hc = tab->hostcache;
1453

    
1454
  if (tab->hcu_scheduled)
1455
    return;
1456

    
1457
  if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
1458
    rt_schedule_hcu(tab);
1459
}
1460

    
1461
static int
1462
if_local_addr(ip_addr a, struct iface *i)
1463
{
1464
  struct ifa *b;
1465

    
1466
  WALK_LIST(b, i->addrs)
1467
    if (ipa_equal(a, b->ip))
1468
      return 1;
1469

    
1470
  return 0;
1471
}
1472

    
1473
static u32 
1474
rt_get_igp_metric(rte *rt)
1475
{
1476
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
1477

    
1478
  if (ea)
1479
    return ea->u.data;
1480

    
1481
  rta *a = rt->attrs;
1482
  if ((a->source == RTS_OSPF) ||
1483
      (a->source == RTS_OSPF_IA) ||
1484
      (a->source == RTS_OSPF_EXT1))
1485
    return rt->u.ospf.metric1;
1486

    
1487
  if (a->source == RTS_RIP)
1488
    return rt->u.rip.metric;
1489

    
1490
  /* Device routes */
1491
  if (a->dest != RTD_ROUTER)
1492
    return 0;
1493

    
1494
  return IGP_METRIC_UNKNOWN;
1495
}
1496

    
1497
static int
1498
rt_update_hostentry(rtable *tab, struct hostentry *he)
1499
{
1500
  struct iface *old_iface = he->iface;
1501
  ip_addr old_gw = he->gw;
1502
  byte old_dest = he->dest;
1503
  u32 old_metric = he->igp_metric;
1504
  int pxlen = 0;
1505

    
1506
  net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
1507
  if (n)
1508
    {
1509
      rta *a = n->routes->attrs;
1510
      pxlen = n->n.pxlen;
1511

    
1512
      if (a->hostentry)
1513
        {
1514
          /* Recursive route should not depend on another recursive route */
1515
          log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d",
1516
              he->addr, n->n.prefix, n->n.pxlen);
1517
          he->iface = NULL;
1518
          he->gw = IPA_NONE;
1519
          he->dest = RTD_UNREACHABLE;
1520
        }
1521
      else if (a->dest == RTD_DEVICE)
1522
        {
1523
          if (if_local_addr(he->addr, a->iface))
1524
            {
1525
              /* The host address is a local address, this is not valid */
1526
              log(L_WARN "Next hop address %I is a local address of iface %s",
1527
                  he->addr, a->iface->name);
1528
              he->iface = NULL;
1529
              he->gw = IPA_NONE;
1530
              he->dest = RTD_UNREACHABLE;
1531
                  }
1532
          else
1533
            {
1534
              /* The host is directly reachable, use link as a gateway */
1535
              he->iface = a->iface;
1536
              he->gw = he->link;
1537
              he->dest = RTD_ROUTER;
1538
            }
1539
        }
1540
      else
1541
        {
1542
          /* The host is reachable through some route entry */
1543
          he->iface = a->iface;
1544
          he->gw = a->gw;
1545
          he->dest = a->dest;
1546
        }
1547

    
1548
      he->igp_metric = he->iface ? rt_get_igp_metric(n->routes) : 0;
1549
    }
1550
  else
1551
    {
1552
      /* The host is unreachable */
1553
      he->iface = NULL;
1554
      he->gw = IPA_NONE;
1555
      he->dest = RTD_UNREACHABLE;
1556
      he->igp_metric = 0;
1557
    }
1558

    
1559
  /* Add a prefix range to the trie */
1560
  trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH);
1561

    
1562
  return hostentry_diff(he, old_iface, old_gw, old_dest, old_metric);
1563
}
1564

    
1565
static void
1566
rt_update_hostcache(rtable *tab)
1567
{
1568
  struct hostcache *hc = tab->hostcache;
1569
  struct hostentry *he;
1570
  node *n, *x;
1571

    
1572
  /* Reset the trie */
1573
  lp_flush(hc->lp);
1574
  hc->trie = f_new_trie(hc->lp);
1575

    
1576
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
1577
    {
1578
      he = SKIP_BACK(struct hostentry, ln, n);
1579
      if (!he->uc)
1580
        {
1581
          hc_delete_hostentry(hc, he);
1582
          continue;
1583
        }
1584

    
1585
      if (rt_update_hostentry(tab, he))
1586
        rt_schedule_nhu(he->tab);
1587
    }
1588

    
1589
  tab->hcu_scheduled = 0;
1590
}
1591

    
1592
static struct hostentry *
1593
rt_find_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
1594
{
1595
  struct hostentry *he;
1596

    
1597
  if (!tab->hostcache)
1598
    rt_init_hostcache(tab);
1599

    
1600
  unsigned int k = hc_hash(a, dep);
1601
  struct hostcache *hc = tab->hostcache;
1602
  for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
1603
    if (ipa_equal(he->addr, a) && (he->tab == dep))
1604
      return he;
1605

    
1606
  he = hc_new_hostentry(hc, a, ll, dep, k);
1607
  rt_update_hostentry(tab, he);
1608
  return he;
1609
}
1610

    
1611
void
1612
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll)
1613
{
1614
  rta_apply_hostentry(a, rt_find_hostentry(tab, *gw, *ll, dep));
1615
}
1616

    
1617
/*
1618
 *  CLI commands
1619
 */
1620

    
1621
static void
1622
rt_format_via(rte *e, byte *via)
1623
{
1624
  rta *a = e->attrs;
1625

    
1626
  switch (a->dest)
1627
    {
1628
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
1629
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
1630
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
1631
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
1632
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
1633
    default:                bsprintf(via, "???");
1634
    }
1635
}
1636

    
1637
static void
1638
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1639
{
1640
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+6];
1641
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
1642
  rta *a = e->attrs;
1643
  int primary = (e->net->routes == e);
1644

    
1645
  rt_format_via(e, via);
1646
  tm_format_datetime(tm, &config->tf_route, e->lastmod);
1647
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
1648
    bsprintf(from, " from %I", a->from);
1649
  else
1650
    from[0] = 0;
1651
  if (a->proto->proto->get_route_info || d->verbose)
1652
    {
1653
      /* Need to normalize the extended attributes */
1654
      ea_list *t = tmpa;
1655
      t = ea_append(t, a->eattrs);
1656
      tmpa = alloca(ea_scan(t));
1657
      ea_merge(t, tmpa);
1658
      ea_sort(tmpa);
1659
    }
1660
  if (a->proto->proto->get_route_info)
1661
    a->proto->proto->get_route_info(e, info, tmpa);
1662
  else
1663
    bsprintf(info, " (%d)", e->pref);
1664
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->proto->name,
1665
             tm, from, primary ? " *" : "", info);
1666
  if (d->verbose)
1667
    rta_show(c, a, tmpa);
1668
}
1669

    
1670
static void
1671
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
1672
{
1673
  rte *e, *ee;
1674
  byte ia[STD_ADDRESS_P_LENGTH+8];
1675
  int ok;
1676

    
1677
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
1678
  if (n->routes)
1679
    d->net_counter++;
1680
  for(e=n->routes; e; e=e->next)
1681
    {
1682
      struct ea_list *tmpa, *old_tmpa;
1683
      struct proto *p0 = e->attrs->proto;
1684
      struct proto *p1 = d->export_protocol;
1685
      struct proto *p2 = d->show_protocol;
1686
      d->rt_counter++;
1687
      ee = e;
1688
      rte_update_lock();                /* We use the update buffer for filtering */
1689
      old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
1690
      ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1691
      if (p2 && p2 != p0) ok = 0;
1692
      if (ok && d->export_mode)
1693
        {
1694
          int ic;
1695
          if ((ic = p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0) < 0)
1696
            ok = 0;
1697
          else if (!ic && d->export_mode > 1)
1698
            {
1699
              /* FIXME - this shows what should be exported according
1700
                 to current filters, but not what was really exported.
1701
                 'configure soft' command may change the export filter
1702
                 and do not update routes */
1703

    
1704
              if ((p1->out_filter == FILTER_REJECT) ||
1705
                  (p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
1706
                ok = 0;
1707
            }
1708
        }
1709
      if (ok)
1710
        {
1711
          d->show_counter++;
1712
          if (d->stats < 2)
1713
            rt_show_rte(c, ia, e, d, tmpa);
1714
          ia[0] = 0;
1715
        }
1716
      if (e != ee)
1717
        rte_free(ee);
1718
      rte_update_unlock();
1719
      if (d->primary_only)
1720
        break;
1721
    }
1722
}
1723

    
1724
static void
1725
rt_show_cont(struct cli *c)
1726
{
1727
  struct rt_show_data *d = c->rover;
1728
#ifdef DEBUGGING
1729
  unsigned max = 4;
1730
#else
1731
  unsigned max = 64;
1732
#endif
1733
  struct fib *fib = &d->table->fib;
1734
  struct fib_iterator *it = &d->fit;
1735

    
1736
  FIB_ITERATE_START(fib, it, f)
1737
    {
1738
      net *n = (net *) f;
1739
      if (d->running_on_config && d->running_on_config != config)
1740
        {
1741
          cli_printf(c, 8004, "Stopped due to reconfiguration");
1742
          goto done;
1743
        }
1744
      if (d->export_protocol &&
1745
          d->export_protocol->core_state != FS_HAPPY &&
1746
          d->export_protocol->core_state != FS_FEEDING)
1747
        {
1748
          cli_printf(c, 8005, "Protocol is down");
1749
          goto done;
1750
        }
1751
      if (!max--)
1752
        {
1753
          FIB_ITERATE_PUT(it, f);
1754
          return;
1755
        }
1756
      rt_show_net(c, n, d);
1757
    }
1758
  FIB_ITERATE_END(f);
1759
  if (d->stats)
1760
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
1761
  else
1762
    cli_printf(c, 0, "");
1763
done:
1764
  c->cont = c->cleanup = NULL;
1765
}
1766

    
1767
static void
1768
rt_show_cleanup(struct cli *c)
1769
{
1770
  struct rt_show_data *d = c->rover;
1771

    
1772
  /* Unlink the iterator */
1773
  fit_get(&d->table->fib, &d->fit);
1774
}
1775

    
1776
void
1777
rt_show(struct rt_show_data *d)
1778
{
1779
  net *n;
1780

    
1781
  if (d->pxlen == 256)
1782
    {
1783
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
1784
      this_cli->cont = rt_show_cont;
1785
      this_cli->cleanup = rt_show_cleanup;
1786
      this_cli->rover = d;
1787
    }
1788
  else
1789
    {
1790
      if (d->show_for)
1791
        n = net_route(d->table, d->prefix, d->pxlen);
1792
      else
1793
        n = net_find(d->table, d->prefix, d->pxlen);
1794
      if (n)
1795
        {
1796
          rt_show_net(this_cli, n, d);
1797
          cli_msg(0, "");
1798
        }
1799
      else
1800
        cli_msg(8001, "Network not in table");
1801
    }
1802
}
1803

    
1804
/*
1805
 *  Documentation for functions declared inline in route.h
1806
 */
1807
#if 0
1808

1809
/**
1810
 * net_find - find a network entry
1811
 * @tab: a routing table
1812
 * @addr: address of the network
1813
 * @len: length of the network prefix
1814
 *
1815
 * net_find() looks up the given network in routing table @tab and
1816
 * returns a pointer to its &net entry or %NULL if no such network
1817
 * exists.
1818
 */
1819
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
1820
{ DUMMY; }
1821

1822
/**
1823
 * net_get - obtain a network entry
1824
 * @tab: a routing table
1825
 * @addr: address of the network
1826
 * @len: length of the network prefix
1827
 *
1828
 * net_get() looks up the given network in routing table @tab and
1829
 * returns a pointer to its &net entry. If no such entry exists, it's
1830
 * created.
1831
 */
1832
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
1833
{ DUMMY; }
1834

1835
/**
1836
 * rte_cow - copy a route for writing
1837
 * @r: a route entry to be copied
1838
 *
1839
 * rte_cow() takes a &rte and prepares it for modification. The exact action
1840
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
1841
 * just returned unchanged, else a new temporary entry with the same contents
1842
 * is created.
1843
 *
1844
 * The primary use of this function is inside the filter machinery -- when
1845
 * a filter wants to modify &rte contents (to change the preference or to
1846
 * attach another set of attributes), it must ensure that the &rte is not
1847
 * shared with anyone else (and especially that it isn't stored in any routing
1848
 * table).
1849
 *
1850
 * Result: a pointer to the new writable &rte.
1851
 */
1852
static inline rte * rte_cow(rte *r)
1853
{ DUMMY; }
1854

1855
#endif