Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 7e95c05d

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
rta_next_hop_outdated(rta *a)
967
{
968
  struct hostentry *he = a->hostentry;
969

    
970
  if (!he)
971
    return 0;
972

    
973
  if (!he->src)
974
    return a->dest != RTD_UNREACHABLE;
975

    
976
  return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) ||
977
    (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
978
    !mpnh_same(a->nexthops, he->src->nexthops);
979
}
980

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

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

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

    
1004
  return e;
1005
}
1006

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

    
1014
  old_best = n->routes;
1015
  if (!old_best)
1016
    return 0;
1017

    
1018
  new_best = NULL;
1019

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

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

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

    
1035
          e = new;
1036
          count++;
1037
        }
1038

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

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

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

    
1059
   if (free_old_best)
1060
    rte_free_quick(old_best);
1061

    
1062
  return count;
1063
}
1064

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

    
1071
  if (tab->nhu_state == 0)
1072
    return;
1073

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

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

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

    
1095
  if (tab->nhu_state > 0)
1096
    ev_schedule(tab->rt_event);
1097
}
1098

    
1099

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1313

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

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

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

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

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

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

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

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

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

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

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

    
1388
  he->addr = a;
1389
  he->link = ll;
1390
  he->tab = dep;
1391
  he->hash_key = k;
1392
  he->uc = 0;
1393
  he->src = NULL;
1394

    
1395
  add_tail(&hc->hostentries, &he->ln);
1396
  hc_insert(hc, he);
1397

    
1398
  hc->hash_items++;
1399
  if (hc->hash_items > hc->hash_max)
1400
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
1401

    
1402
  return he;
1403
}
1404

    
1405
static void
1406
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
1407
{
1408
  rta_free(he->src);
1409

    
1410
  rem_node(&he->ln);
1411
  hc_remove(hc, he);
1412
  sl_free(hc->slab, he);
1413

    
1414
  hc->hash_items--;
1415
  if (hc->hash_items < hc->hash_min)
1416
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
1417
}
1418

    
1419
static void
1420
rt_init_hostcache(rtable *tab)
1421
{
1422
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
1423
  init_list(&hc->hostentries);
1424

    
1425
  hc->hash_items = 0;
1426
  hc_alloc_table(hc, HC_DEF_ORDER);
1427
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
1428

    
1429
  hc->lp = lp_new(rt_table_pool, 1008);
1430
  hc->trie = f_new_trie(hc->lp);
1431

    
1432
  tab->hostcache = hc;
1433
}
1434

    
1435
static void
1436
rt_free_hostcache(rtable *tab)
1437
{
1438
  struct hostcache *hc = tab->hostcache;
1439

    
1440
  node *n;
1441
  WALK_LIST(n, hc->hostentries)
1442
    {
1443
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
1444
      rta_free(he->src);
1445

    
1446
      if (he->uc)
1447
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
1448
    }
1449

    
1450
  rfree(hc->slab);
1451
  rfree(hc->lp);
1452
  mb_free(hc->hash_table);
1453
  mb_free(hc);
1454
}
1455

    
1456
static void
1457
rt_notify_hostcache(rtable *tab, net *net)
1458
{
1459
  struct hostcache *hc = tab->hostcache;
1460

    
1461
  if (tab->hcu_scheduled)
1462
    return;
1463

    
1464
  if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
1465
    rt_schedule_hcu(tab);
1466
}
1467

    
1468
static int
1469
if_local_addr(ip_addr a, struct iface *i)
1470
{
1471
  struct ifa *b;
1472

    
1473
  WALK_LIST(b, i->addrs)
1474
    if (ipa_equal(a, b->ip))
1475
      return 1;
1476

    
1477
  return 0;
1478
}
1479

    
1480
static u32 
1481
rt_get_igp_metric(rte *rt)
1482
{
1483
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
1484

    
1485
  if (ea)
1486
    return ea->u.data;
1487

    
1488
  rta *a = rt->attrs;
1489
  if ((a->source == RTS_OSPF) ||
1490
      (a->source == RTS_OSPF_IA) ||
1491
      (a->source == RTS_OSPF_EXT1))
1492
    return rt->u.ospf.metric1;
1493

    
1494
  if (a->source == RTS_RIP)
1495
    return rt->u.rip.metric;
1496

    
1497
  /* Device routes */
1498
  if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
1499
    return 0;
1500

    
1501
  return IGP_METRIC_UNKNOWN;
1502
}
1503

    
1504
static int
1505
rt_update_hostentry(rtable *tab, struct hostentry *he)
1506
{
1507
  rta *old_src = he->src;
1508
  int pxlen = 0;
1509

    
1510
  /* Reset the hostentry */ 
1511
  he->src = NULL;
1512
  he->gw = IPA_NONE;
1513
  he->dest = RTD_UNREACHABLE;
1514
  he->igp_metric = 0;
1515

    
1516
  net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
1517
  if (n)
1518
    {
1519
      rta *a = n->routes->attrs;
1520
      pxlen = n->n.pxlen;
1521

    
1522
      if (a->hostentry)
1523
        {
1524
          /* Recursive route should not depend on another recursive route */
1525
          log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d",
1526
              he->addr, n->n.prefix, pxlen);
1527
          goto done;
1528
        }
1529

    
1530
      if (a->dest == RTD_DEVICE)
1531
        {
1532
          if (if_local_addr(he->addr, a->iface))
1533
            {
1534
              /* The host address is a local address, this is not valid */
1535
              log(L_WARN "Next hop address %I is a local address of iface %s",
1536
                  he->addr, a->iface->name);
1537
              goto done;
1538
                  }
1539

    
1540
          /* The host is directly reachable, use link as a gateway */
1541
          he->gw = he->link;
1542
          he->dest = RTD_ROUTER;
1543
        }
1544
      else
1545
        {
1546
          /* The host is reachable through some route entry */
1547
          he->gw = a->gw;
1548
          he->dest = a->dest;
1549
        }
1550

    
1551
      he->src = rta_clone(a);
1552
      he->igp_metric = rt_get_igp_metric(n->routes);
1553
    }
1554

    
1555
 done:
1556
  /* Add a prefix range to the trie */
1557
  trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH);
1558

    
1559
  rta_free(old_src);
1560
  return old_src != he->src;
1561
}
1562

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

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

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

    
1583
      if (rt_update_hostentry(tab, he))
1584
        rt_schedule_nhu(he->tab);
1585
    }
1586

    
1587
  tab->hcu_scheduled = 0;
1588
}
1589

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

    
1595
  if (!tab->hostcache)
1596
    rt_init_hostcache(tab);
1597

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

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

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

    
1615
/*
1616
 *  CLI commands
1617
 */
1618

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

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

    
1636
static void
1637
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
1638
{
1639
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8];
1640
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
1641
  rta *a = e->attrs;
1642
  int primary = (e->net->routes == e);
1643
  struct mpnh *nh;
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
  for (nh = a->nexthops; nh; nh = nh->next)
1667
    cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1);
1668
  if (d->verbose)
1669
    rta_show(c, a, tmpa);
1670
}
1671

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

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

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

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

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

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

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

    
1778
void
1779
rt_show(struct rt_show_data *d)
1780
{
1781
  net *n;
1782

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

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

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

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

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

1857
#endif