Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 51762a45

History | View | Annotate | Download (59.9 KB)

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

    
9
/**
10
 * DOC: Routing tables
11
 *
12
 * Routing tables are probably the most important structures BIRD uses. They
13
 * hold all the information about known networks, the associated routes and
14
 * their attributes.
15
 *
16
 * There are multiple routing tables (a primary one together with any
17
 * number of secondary ones if requested by the configuration). Each table
18
 * is basically a FIB containing entries describing the individual
19
 * destination networks. For each network (represented by structure &net),
20
 * there is a one-way linked list of route entries (&rte), the first entry
21
 * on the list being the best one (i.e., the one we currently use
22
 * for routing), the order of the other ones is undetermined.
23
 *
24
 * The &rte contains information specific to the route (preference, protocol
25
 * metrics, time of last modification etc.) and a pointer to a &rta structure
26
 * (see the route attribute module for a precise explanation) holding the
27
 * remaining route attributes which are expected to be shared by multiple
28
 * routes in order to conserve memory.
29
 */
30

    
31
#undef LOCAL_DEBUG
32

    
33
#include "nest/bird.h"
34
#include "nest/route.h"
35
#include "nest/protocol.h"
36
#include "nest/cli.h"
37
#include "nest/iface.h"
38
#include "lib/resource.h"
39
#include "lib/event.h"
40
#include "lib/string.h"
41
#include "conf/conf.h"
42
#include "filter/filter.h"
43
#include "lib/string.h"
44
#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 inline int rt_prune_table(rtable *tab);
59
static inline void rt_schedule_gc(rtable *tab);
60
static inline void rt_schedule_prune(rtable *tab);
61

    
62

    
63
static inline struct ea_list *
64
make_tmp_attrs(struct rte *rt, struct linpool *pool)
65
{
66
  struct ea_list *(*mta)(struct rte *rt, struct linpool *pool);
67
  mta = rt->attrs->src->proto->make_tmp_attrs;
68
  return mta ? mta(rt, rte_update_pool) : NULL;
69
}
70

    
71
/* Like fib_route(), but skips empty net entries */
72
static net *
73
net_route(rtable *tab, ip_addr a, int len)
74
{
75
  ip_addr a0;
76
  net *n;
77

    
78
  while (len >= 0)
79
    {
80
      a0 = ipa_and(a, ipa_mkmask(len));
81
      n = fib_find(&tab->fib, &a0, len);
82
      if (n && rte_is_valid(n->routes))
83
        return n;
84
      len--;
85
    }
86
  return NULL;
87
}
88

    
89
static void
90
rte_init(struct fib_node *N)
91
{
92
  net *n = (net *) N;
93

    
94
  N->flags = 0;
95
  n->routes = NULL;
96
}
97

    
98
/**
99
 * rte_find - find a route
100
 * @net: network node
101
 * @src: route source
102
 *
103
 * The rte_find() function returns a route for destination @net
104
 * which is from route source @src.
105
 */
106
rte *
107
rte_find(net *net, struct rte_src *src)
108
{
109
  rte *e = net->routes;
110

    
111
  while (e && e->attrs->src != src)
112
    e = e->next;
113
  return e;
114
}
115

    
116
/**
117
 * rte_get_temp - get a temporary &rte
118
 * @a: attributes to assign to the new route (a &rta; in case it's
119
 * un-cached, rte_update() will create a cached copy automatically)
120
 *
121
 * Create a temporary &rte and bind it with the attributes @a.
122
 * Also set route preference to the default preference set for
123
 * the protocol.
124
 */
125
rte *
126
rte_get_temp(rta *a)
127
{
128
  rte *e = sl_alloc(rte_slab);
129

    
130
  e->attrs = a;
131
  e->flags = 0;
132
  e->pref = a->src->proto->preference;
133
  return e;
134
}
135

    
136
rte *
137
rte_do_cow(rte *r)
138
{
139
  rte *e = sl_alloc(rte_slab);
140

    
141
  memcpy(e, r, sizeof(rte));
142
  e->attrs = rta_clone(r->attrs);
143
  e->flags = 0;
144
  return e;
145
}
146

    
147
static int                                /* Actually better or at least as good as */
148
rte_better(rte *new, rte *old)
149
{
150
  int (*better)(rte *, rte *);
151

    
152
  if (!rte_is_valid(old))
153
    return 1;
154
  if (!rte_is_valid(new))
155
    return 0;
156

    
157
  if (new->pref > old->pref)
158
    return 1;
159
  if (new->pref < old->pref)
160
    return 0;
161
  if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
162
    {
163
      /*
164
       *  If the user has configured protocol preferences, so that two different protocols
165
       *  have the same preference, try to break the tie by comparing addresses. Not too
166
       *  useful, but keeps the ordering of routes unambiguous.
167
       */
168
      return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
169
    }
170
  if (better = new->attrs->src->proto->rte_better)
171
    return better(new, old);
172
  return 0;
173
}
174

    
175
static void
176
rte_trace(struct proto *p, rte *e, int dir, char *msg)
177
{
178
  byte via[STD_ADDRESS_P_LENGTH+32];
179

    
180
  rt_format_via(e, via);
181
  log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
182
}
183

    
184
static inline void
185
rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg)
186
{
187
  if (p->debug & flag)
188
    rte_trace(p, e, '>', msg);
189
}
190

    
191
static inline void
192
rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg)
193
{
194
  if (p->debug & flag)
195
    rte_trace(p, e, '<', msg);
196
}
197

    
198
static rte *
199
export_filter(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
200
{
201
  struct proto *p = ah->proto;
202
  struct filter *filter = ah->out_filter;
203
  struct proto_stats *stats = ah->stats;
204
  ea_list *tmpb = NULL;
205
  rte *rt;
206
  int v;
207

    
208
  rt = rt0;
209
  *rt_free = NULL;
210

    
211
  /* If called does not care for eattrs, we prepare one internally */
212
  if (!tmpa)
213
    {
214
      tmpb = make_tmp_attrs(rt, rte_update_pool);
215
      tmpa = &tmpb;
216
    }
217

    
218
  v = p->import_control ? p->import_control(p, &rt, tmpa, rte_update_pool) : 0;
219
  if (v < 0)
220
    {
221
      if (silent)
222
        goto reject;
223

    
224
      stats->exp_updates_rejected++;
225
      if (v == RIC_REJECT)
226
        rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
227
      goto reject;
228
    }
229
  if (v > 0)
230
    {
231
      if (!silent)
232
        rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
233
      goto accept;
234
    }
235

    
236
  v = filter && ((filter == FILTER_REJECT) ||
237
                 (f_run(filter, &rt, tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT));
238
  if (v)
239
    {
240
      if (silent)
241
        goto reject;
242

    
243
      stats->exp_updates_filtered++;
244
      rte_trace_out(D_FILTERS, p, rt, "filtered out");
245
      goto reject;
246
    }
247

    
248
 accept:
249
  if (rt != rt0)
250
    *rt_free = rt;
251
  return rt;
252

    
253
 reject:
254
  /* Discard temporary rte */
255
  if (rt != rt0)
256
    rte_free(rt);
257
  return NULL;
258
}
259

    
260
static void
261
do_rt_notify(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
262
{
263
  struct proto *p = ah->proto;
264
  struct proto_stats *stats = ah->stats;
265

    
266

    
267
  /*
268
   * First, apply export limit.
269
   *
270
   * Export route limits has several problems. Because exp_routes
271
   * counter is reset before refeed, we don't really know whether
272
   * limit is breached and whether the update is new or not. Therefore
273
   * the number of really exported routes may exceed the limit
274
   * temporarily (routes exported before and new routes in refeed).
275
   *
276
   * Minor advantage is that if the limit is decreased and refeed is
277
   * requested, the number of exported routes really decrease.
278
   *
279
   * Second problem is that with export limits, we don't know whether
280
   * old was really exported (it might be blocked by limit). When a
281
   * withdraw is exported, we announce it even when the previous
282
   * update was blocked. This is not a big issue, but the same problem
283
   * is in updating exp_routes counter. Therefore, to be consistent in
284
   * increases and decreases of exp_routes, we count exported routes
285
   * regardless of blocking by limits.
286
   *
287
   * Similar problem is in handling updates - when a new route is
288
   * received and blocking is active, the route would be blocked, but
289
   * when an update for the route will be received later, the update
290
   * would be propagated (as old != NULL). Therefore, we have to block
291
   * also non-new updates (contrary to import blocking).
292
   */
293

    
294
  struct proto_limit *l = ah->out_limit;
295
  if (l && new)
296
    {
297
      if ((!old || refeed) && (stats->exp_routes >= l->limit))
298
        proto_notify_limit(ah, l, PLD_OUT, stats->exp_routes);
299

    
300
      if (l->state == PLS_BLOCKED)
301
        {
302
          stats->exp_routes++;        /* see note above */
303
          stats->exp_updates_rejected++;
304
          rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
305
          new = NULL;
306

    
307
          if (!old)
308
            return;
309
        }
310
    }
311

    
312

    
313
  if (new)
314
    stats->exp_updates_accepted++;
315
  else
316
    stats->exp_withdraws_accepted++;
317

    
318
  /* Hack: We do not decrease exp_routes during refeed, we instead
319
     reset exp_routes at the start of refeed. */
320
  if (new)
321
    stats->exp_routes++;
322
  if (old && !refeed)
323
    stats->exp_routes--;
324

    
325
  if (p->debug & D_ROUTES)
326
    {
327
      if (new && old)
328
        rte_trace_out(D_ROUTES, p, new, "replaced");
329
      else if (new)
330
        rte_trace_out(D_ROUTES, p, new, "added");
331
      else if (old)
332
        rte_trace_out(D_ROUTES, p, old, "removed");
333
    }
334
  if (!new)
335
    p->rt_notify(p, ah->table, net, NULL, old, NULL);
336
  else if (tmpa)
337
    {
338
      ea_list *t = tmpa;
339
      while (t->next)
340
        t = t->next;
341
      t->next = new->attrs->eattrs;
342
      p->rt_notify(p, ah->table, net, new, old, tmpa);
343
      t->next = NULL;
344
    }
345
  else
346
    p->rt_notify(p, ah->table, net, new, old, new->attrs->eattrs);
347
}
348

    
349
static void
350
rt_notify_basic(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
351
{
352
  // struct proto *p = ah->proto;
353
  struct proto_stats *stats = ah->stats;
354

    
355
  rte *new_free = NULL;
356
  rte *old_free = NULL;
357

    
358
  if (new)
359
    stats->exp_updates_received++;
360
  else
361
    stats->exp_withdraws_received++;
362

    
363
  /*
364
   * This is a tricky part - we don't know whether route 'old' was
365
   * exported to protocol 'p' or was filtered by the export filter.
366
   * We try to run the export filter to know this to have a correct
367
   * value in 'old' argument of rte_update (and proper filter value)
368
   *
369
   * FIXME - this is broken because 'configure soft' may change
370
   * filters but keep routes. Refeed is expected to be called after
371
   * change of the filters and with old == new, therefore we do not
372
   * even try to run the filter on an old route, This may lead to 
373
   * 'spurious withdraws' but ensure that there are no 'missing
374
   * withdraws'.
375
   *
376
   * This is not completely safe as there is a window between
377
   * reconfiguration and the end of refeed - if a newly filtered
378
   * route disappears during this period, proper withdraw is not
379
   * sent (because old would be also filtered) and the route is
380
   * not refeeded (because it disappeared before that).
381
   */
382

    
383
  if (new)
384
    new = export_filter(ah, new, &new_free, &tmpa, 0);
385

    
386
  if (old && !refeed)
387
    old = export_filter(ah, old, &old_free, NULL, 1);
388

    
389
  /* FIXME - This is broken because of incorrect 'old' value (see above) */
390
  if (!new && !old)
391
    return;
392

    
393
  do_rt_notify(ah, net, new, old, tmpa, refeed);
394

    
395
  /* Discard temporary rte's */
396
  if (new_free)
397
    rte_free(new_free);
398
  if (old_free)
399
    rte_free(old_free);
400
}
401

    
402
static void
403
rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old,
404
                   ea_list *tmpa, int feed)
405
{
406
  // struct proto *p = ah->proto;
407
  struct proto_stats *stats = ah->stats;
408

    
409
  rte *new_best = NULL;
410
  rte *old_best = NULL;
411
  rte *new_free = NULL;
412
  rte *old_free = NULL;
413
  rte *r;
414

    
415
  /* Used to track whether we met old_changed position. If before_old is NULL
416
     old_changed was the first and we met it implicitly before current best route. */
417
  int old_meet = old_changed && !before_old;
418

    
419
  /* Note that before_old is either NULL or valid (not rejected) route.
420
     If old_changed is valid, before_old have to be too. If old changed route
421
     was not valid, caller must use NULL for both old_changed and before_old. */
422

    
423
  if (new_changed)
424
    stats->exp_updates_received++;
425
  else
426
    stats->exp_withdraws_received++;
427

    
428
  /* First, find the new_best route - first accepted by filters */
429
  for (r=net->routes; rte_is_valid(r); r=r->next)
430
    {
431
      if (new_best = export_filter(ah, r, &new_free, &tmpa, 0))
432
        break;
433

    
434
      /* Note if we walked around the position of old_changed route */
435
      if (r == before_old)
436
        old_meet = 1;
437
    }
438

    
439
  /* 
440
   * Second, handle the feed case. That means we do not care for
441
   * old_best. It is NULL for feed, and the new_best for refeed. 
442
   * For refeed, there is a hack similar to one in rt_notify_basic()
443
   * to ensure withdraws in case of changed filters
444
   */
445
  if (feed)
446
    {
447
      if (feed == 2)        /* refeed */
448
        old_best = new_best ? new_best :
449
          (rte_is_valid(net->routes) ? net->routes : NULL);
450
      else
451
        old_best = NULL;
452

    
453
      if (!new_best && !old_best)
454
        return;
455

    
456
      goto found;
457
    }
458

    
459
  /*
460
   * Now, we find the old_best route. Generally, it is the same as the
461
   * new_best, unless new_best is the same as new_changed or
462
   * old_changed is accepted before new_best.
463
   *
464
   * There are four cases:
465
   *
466
   * - We would find and accept old_changed before new_best, therefore
467
   *   old_changed is old_best. In remaining cases we suppose this
468
   *   is not true.
469
   *
470
   * - We found no new_best, therefore there is also no old_best and
471
   *   we ignore this withdraw.
472
   *
473
   * - We found new_best different than new_changed, therefore
474
   *   old_best is the same as new_best and we ignore this update.
475
   *
476
   * - We found new_best the same as new_changed, therefore it cannot
477
   *   be old_best and we have to continue search for old_best.
478
   */
479

    
480
  /* First case */
481
  if (old_meet)
482
    if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
483
      goto found;
484

    
485
  /* Second case */
486
  if (!new_best)
487
    return;
488

    
489
  /* Third case, we use r instead of new_best, because export_filter() could change it */
490
  if (r != new_changed)
491
    {
492
      if (new_free)
493
        rte_free(new_free);
494
      return;
495
    }
496

    
497
  /* Fourth case */
498
  for (r=r->next; rte_is_valid(r); r=r->next)
499
    {
500
      if (old_best = export_filter(ah, r, &old_free, NULL, 1))
501
        goto found;
502

    
503
      if (r == before_old)
504
        if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
505
          goto found;
506
    }
507

    
508
  /* Implicitly, old_best is NULL and new_best is non-NULL */
509

    
510
 found:
511
  do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2));
512

    
513
  /* Discard temporary rte's */
514
  if (new_free)
515
    rte_free(new_free);
516
  if (old_free)
517
    rte_free(old_free);
518
}
519

    
520
/**
521
 * rte_announce - announce a routing table change
522
 * @tab: table the route has been added to
523
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
524
 * @net: network in question
525
 * @new: the new route to be announced
526
 * @old: the previous route for the same network
527
 * @tmpa: a list of temporary attributes belonging to the new route
528
 *
529
 * This function gets a routing table update and announces it
530
 * to all protocols that acccepts given type of route announcement
531
 * and are connected to the same table by their announcement hooks.
532
 *
533
 * Route announcement of type RA_OPTIMAL si generated when optimal
534
 * route (in routing table @tab) changes. In that case @old stores the
535
 * old optimal route.
536
 *
537
 * Route announcement of type RA_ANY si generated when any route (in
538
 * routing table @tab) changes In that case @old stores the old route
539
 * from the same protocol.
540
 *
541
 * For each appropriate protocol, we first call its import_control()
542
 * hook which performs basic checks on the route (each protocol has a
543
 * right to veto or force accept of the route before any filter is
544
 * asked) and adds default values of attributes specific to the new
545
 * protocol (metrics, tags etc.).  Then it consults the protocol's
546
 * export filter and if it accepts the route, the rt_notify() hook of
547
 * the protocol gets called.
548
 */
549
static void
550
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *before_old, ea_list *tmpa)
551
{
552
  if (!rte_is_valid(old))
553
    old = before_old = NULL;
554

    
555
  if (!rte_is_valid(new))
556
    new = NULL;
557

    
558
  if (!old && !new)
559
    return;
560

    
561
  if (type == RA_OPTIMAL)
562
    {
563
      if (new)
564
        new->attrs->src->proto->stats.pref_routes++;
565
      if (old)
566
        old->attrs->src->proto->stats.pref_routes--;
567

    
568
      if (tab->hostcache)
569
        rt_notify_hostcache(tab, net);
570
    }
571

    
572
  struct announce_hook *a;
573
  WALK_LIST(a, tab->hooks)
574
    {
575
      ASSERT(a->proto->export_state != ES_DOWN);
576
      if (a->proto->accept_ra_types == type)
577
        if (type == RA_ACCEPTED)
578
          rt_notify_accepted(a, net, new, old, before_old, tmpa, 0);
579
        else
580
          rt_notify_basic(a, net, new, old, tmpa, 0);
581
    }
582
}
583

    
584
static inline int
585
rte_validate(rte *e)
586
{
587
  int c;
588
  net *n = e->net;
589

    
590
  if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
591
    {
592
      log(L_WARN "Ignoring bogus prefix %I/%d received via %s",
593
          n->n.prefix, n->n.pxlen, e->sender->proto->name);
594
      return 0;
595
    }
596

    
597
  c = ipa_classify_net(n->n.prefix);
598
  if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
599
    {
600
      log(L_WARN "Ignoring bogus route %I/%d received via %s",
601
          n->n.prefix, n->n.pxlen, e->sender->proto->name);
602
      return 0;
603
    }
604

    
605
  return 1;
606
}
607

    
608
/**
609
 * rte_free - delete a &rte
610
 * @e: &rte to be deleted
611
 *
612
 * rte_free() deletes the given &rte from the routing table it's linked to.
613
 */
614
void
615
rte_free(rte *e)
616
{
617
  if (rta_is_cached(e->attrs))
618
    rta_free(e->attrs);
619
  sl_free(rte_slab, e);
620
}
621

    
622
static inline void
623
rte_free_quick(rte *e)
624
{
625
  rta_free(e->attrs);
626
  sl_free(rte_slab, e);
627
}
628

    
629
static int
630
rte_same(rte *x, rte *y)
631
{
632
  return
633
    x->attrs == y->attrs &&
634
    x->flags == y->flags &&
635
    x->pflags == y->pflags &&
636
    x->pref == y->pref &&
637
    (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y));
638
}
639

    
640
static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); }
641

    
642
static void
643
rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, struct rte_src *src)
644
{
645
  struct proto *p = ah->proto;
646
  struct rtable *table = ah->table;
647
  struct proto_stats *stats = ah->stats;
648
  static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
649
  rte *before_old = NULL;
650
  rte *old_best = net->routes;
651
  rte *old = NULL;
652
  rte **k;
653

    
654
  k = &net->routes;                        /* Find and remove original route from the same protocol */
655
  while (old = *k)
656
    {
657
      if (old->attrs->src == src)
658
        {
659
          /* If there is the same route in the routing table but from
660
           * a different sender, then there are two paths from the
661
           * source protocol to this routing table through transparent
662
           * pipes, which is not allowed.
663
           *
664
           * We log that and ignore the route. If it is withdraw, we
665
           * ignore it completely (there might be 'spurious withdraws',
666
           * see FIXME in do_rte_announce())
667
           */
668
          if (old->sender->proto != p)
669
            {
670
              if (new)
671
                {
672
                  log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %I/%d to table %s",
673
                      net->n.prefix, net->n.pxlen, table->name);
674
                  rte_free_quick(new);
675
                }
676
              return;
677
            }
678

    
679
          if (new && rte_same(old, new))
680
            {
681
              /* No changes, ignore the new route */
682

    
683
              if (!rte_is_filtered(new))
684
                {
685
                  stats->imp_updates_ignored++;
686
                  rte_trace_in(D_ROUTES, p, new, "ignored");
687
                }
688

    
689
              rte_free_quick(new);
690
#ifdef CONFIG_RIP
691
              /* lastmod is used internally by RIP as the last time
692
                 when the route was received. */
693
              if (src->proto->proto == &proto_rip)
694
                old->lastmod = now;
695
#endif
696
              return;
697
            }
698
          *k = old->next;
699
          break;
700
        }
701
      k = &old->next;
702
      before_old = old;
703
    }
704

    
705
  if (!old)
706
    before_old = NULL;
707

    
708
  if (!old && !new)
709
    {
710
      stats->imp_withdraws_ignored++;
711
      return;
712
    }
713

    
714
  int new_ok = rte_is_ok(new);
715
  int old_ok = rte_is_ok(old);
716

    
717
  struct proto_limit *l = ah->rx_limit;
718
  if (l && !old && new)
719
    {
720
      u32 all_routes = stats->imp_routes + stats->filt_routes;
721

    
722
      if (all_routes >= l->limit)
723
        proto_notify_limit(ah, l, PLD_RX, all_routes);
724

    
725
      if (l->state == PLS_BLOCKED)
726
        {
727
          /* In receive limit the situation is simple, old is NULL so
728
             we just free new and exit like nothing happened */
729

    
730
          stats->imp_updates_ignored++;
731
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
732
          rte_free_quick(new);
733
          return;
734
        }
735
    }
736

    
737
  l = ah->in_limit;
738
  if (l && !old_ok && new_ok)
739
    {
740
      if (stats->imp_routes >= l->limit)
741
        proto_notify_limit(ah, l, PLD_IN, stats->imp_routes);
742

    
743
      if (l->state == PLS_BLOCKED)
744
        {
745
          /* In import limit the situation is more complicated. We
746
             shouldn't just drop the route, we should handle it like
747
             it was filtered. We also have to continue the route
748
             processing if old or new is non-NULL, but we should exit
749
             if both are NULL as this case is probably assumed to be
750
             already handled. */
751

    
752
          stats->imp_updates_ignored++;
753
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
754

    
755
          if (ah->in_keep_filtered)
756
            new->flags |= REF_FILTERED;
757
          else
758
            { rte_free_quick(new); new = NULL; }
759

    
760
          /* Note that old && !new could be possible when
761
             ah->in_keep_filtered changed in the recent past. */
762

    
763
          if (!old && !new)
764
            return;
765

    
766
          new_ok = 0;
767
          goto skip_stats1;
768
        }
769
    }
770

    
771
  if (new_ok)
772
    stats->imp_updates_accepted++;
773
  else if (old_ok)
774
    stats->imp_withdraws_accepted++;
775
  else
776
    stats->imp_withdraws_ignored++;
777

    
778
 skip_stats1:
779

    
780
  if (new)
781
    rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
782
  if (old)
783
    rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
784

    
785
  if (table->config->sorted)
786
    {
787
      /* If routes are sorted, just insert new route to appropriate position */
788
      if (new)
789
        {
790
          if (before_old && !rte_better(new, before_old))
791
            k = &before_old->next;
792
          else
793
            k = &net->routes;
794

    
795
          for (; *k; k=&(*k)->next)
796
            if (rte_better(new, *k))
797
              break;
798

    
799
          new->next = *k;
800
          *k = new;
801
        }
802
    }
803
  else
804
    {
805
      /* If routes are not sorted, find the best route and move it on
806
         the first position. There are several optimized cases. */
807

    
808
      if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
809
        goto do_recalculate;
810

    
811
      if (new && rte_better(new, old_best))
812
        {
813
          /* The first case - the new route is cleary optimal,
814
             we link it at the first position */
815

    
816
          new->next = net->routes;
817
          net->routes = new;
818
        }
819
      else if (old == old_best)
820
        {
821
          /* The second case - the old best route disappeared, we add the
822
             new route (if we have any) to the list (we don't care about
823
             position) and then we elect the new optimal route and relink
824
             that route at the first position and announce it. New optimal
825
             route might be NULL if there is no more routes */
826

    
827
        do_recalculate:
828
          /* Add the new route to the list */
829
          if (new)
830
            {
831
              new->next = net->routes;
832
              net->routes = new;
833
            }
834

    
835
          /* Find a new optimal route (if there is any) */
836
          if (net->routes)
837
            {
838
              rte **bp = &net->routes;
839
              for (k=&(*bp)->next; *k; k=&(*k)->next)
840
                if (rte_better(*k, *bp))
841
                  bp = k;
842

    
843
              /* And relink it */
844
              rte *best = *bp;
845
              *bp = best->next;
846
              best->next = net->routes;
847
              net->routes = best;
848
            }
849
        }
850
      else if (new)
851
        {
852
          /* The third case - the new route is not better than the old
853
             best route (therefore old_best != NULL) and the old best
854
             route was not removed (therefore old_best == net->routes).
855
             We just link the new route after the old best route. */
856

    
857
          ASSERT(net->routes != NULL);
858
          new->next = net->routes->next;
859
          net->routes->next = new;
860
        }
861
      /* The fourth (empty) case - suboptimal route was removed, nothing to do */
862
    }
863

    
864
  if (new)
865
    new->lastmod = now;
866

    
867
  /* Log the route change */
868
  if (p->debug & D_ROUTES)
869
    {
870
      if (new_ok)
871
        rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added");
872
      else if (old_ok)
873
        {
874
          if (old != old_best)
875
            rte_trace(p, old, '>', "removed");
876
          else if (rte_is_ok(net->routes))
877
            rte_trace(p, old, '>', "removed [replaced]");
878
          else
879
            rte_trace(p, old, '>', "removed [sole]");
880
        }
881
    }
882

    
883
  /* Propagate the route change */
884
  rte_announce(table, RA_ANY, net, new, old, NULL, tmpa);
885
  if (net->routes != old_best)
886
    rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, tmpa);
887
  if (table->config->sorted)
888
    rte_announce(table, RA_ACCEPTED, net, new, old, before_old, tmpa);
889

    
890
  if (!net->routes &&
891
      (table->gc_counter++ >= table->config->gc_max_ops) &&
892
      (table->gc_time + table->config->gc_min_time <= now))
893
    rt_schedule_gc(table);
894

    
895
  if (old_ok && p->rte_remove)
896
    p->rte_remove(net, old);
897
  if (new_ok && p->rte_insert)
898
    p->rte_insert(net, new);
899

    
900
  if (old)
901
    rte_free_quick(old);
902
}
903

    
904
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
905

    
906
static inline void
907
rte_update_lock(void)
908
{
909
  rte_update_nest_cnt++;
910
}
911

    
912
static inline void
913
rte_update_unlock(void)
914
{
915
  if (!--rte_update_nest_cnt)
916
    lp_flush(rte_update_pool);
917
}
918

    
919
static inline void
920
rte_hide_dummy_routes(net *net, rte **dummy)
921
{
922
  if (net->routes && net->routes->attrs->source == RTS_DUMMY)
923
  {
924
    *dummy = net->routes;
925
    net->routes = (*dummy)->next;
926
  }
927
}
928

    
929
static inline void
930
rte_unhide_dummy_routes(net *net, rte **dummy)
931
{
932
  if (*dummy)
933
  {
934
    (*dummy)->next = net->routes;
935
    net->routes = *dummy;
936
  }
937
}
938

    
939
/**
940
 * rte_update - enter a new update to a routing table
941
 * @table: table to be updated
942
 * @ah: pointer to table announce hook
943
 * @net: network node
944
 * @p: protocol submitting the update
945
 * @src: protocol originating the update
946
 * @new: a &rte representing the new route or %NULL for route removal.
947
 *
948
 * This function is called by the routing protocols whenever they discover
949
 * a new route or wish to update/remove an existing route. The right announcement
950
 * sequence is to build route attributes first (either un-cached with @aflags set
951
 * to zero or a cached one using rta_lookup(); in this case please note that
952
 * you need to increase the use count of the attributes yourself by calling
953
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
954
 * the appropriate data and finally submit the new &rte by calling rte_update().
955
 *
956
 * @src specifies the protocol that originally created the route and the meaning
957
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
958
 * same value as @new->attrs->proto. @p specifies the protocol that called
959
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
960
 * stores @p in @new->sender;
961
 *
962
 * When rte_update() gets any route, it automatically validates it (checks,
963
 * whether the network and next hop address are valid IP addresses and also
964
 * whether a normal routing protocol doesn't try to smuggle a host or link
965
 * scope route to the table), converts all protocol dependent attributes stored
966
 * in the &rte to temporary extended attributes, consults import filters of the
967
 * protocol to see if the route should be accepted and/or its attributes modified,
968
 * stores the temporary attributes back to the &rte.
969
 *
970
 * Now, having a "public" version of the route, we
971
 * automatically find any old route defined by the protocol @src
972
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
973
 * recalculate the optimal route for this destination and finally broadcast
974
 * the change (if any) to all routing protocols by calling rte_announce().
975
 *
976
 * All memory used for attribute lists and other temporary allocations is taken
977
 * from a special linear pool @rte_update_pool and freed when rte_update()
978
 * finishes.
979
 */
980

    
981
void
982
rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
983
{
984
  struct proto *p = ah->proto;
985
  struct proto_stats *stats = ah->stats;
986
  struct filter *filter = ah->in_filter;
987
  ea_list *tmpa = NULL;
988
  rte *dummy = NULL;
989

    
990
  rte_update_lock();
991
  if (new)
992
    {
993
      new->sender = ah;
994

    
995
      stats->imp_updates_received++;
996
      if (!rte_validate(new))
997
        {
998
          rte_trace_in(D_FILTERS, p, new, "invalid");
999
          stats->imp_updates_invalid++;
1000
          goto drop;
1001
        }
1002

    
1003
      if (filter == FILTER_REJECT)
1004
        {
1005
          stats->imp_updates_filtered++;
1006
          rte_trace_in(D_FILTERS, p, new, "filtered out");
1007

    
1008
          if (! ah->in_keep_filtered)
1009
            goto drop;
1010

    
1011
          /* new is a private copy, i could modify it */
1012
          new->flags |= REF_FILTERED;
1013
        }
1014
      else
1015
        {
1016
          tmpa = make_tmp_attrs(new, rte_update_pool);
1017
          if (filter && (filter != FILTER_REJECT))
1018
            {
1019
              ea_list *old_tmpa = tmpa;
1020
              int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
1021
              if (fr > F_ACCEPT)
1022
                {
1023
                  stats->imp_updates_filtered++;
1024
                  rte_trace_in(D_FILTERS, p, new, "filtered out");
1025

    
1026
                  if (! ah->in_keep_filtered)
1027
                    goto drop;
1028

    
1029
                  new->flags |= REF_FILTERED;
1030
                }
1031
              if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
1032
                src->proto->store_tmp_attrs(new, tmpa);
1033
            }
1034
        }
1035
      if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1036
        new->attrs = rta_lookup(new->attrs);
1037
      new->flags |= REF_COW;
1038
    }
1039
  else
1040
    {
1041
      stats->imp_withdraws_received++;
1042

    
1043
      if (!net || !src)
1044
        {
1045
          stats->imp_withdraws_ignored++;
1046
          rte_update_unlock();
1047
          return;
1048
        }
1049
    }
1050

    
1051
 recalc:
1052
  rte_hide_dummy_routes(net, &dummy);
1053
  rte_recalculate(ah, net, new, tmpa, src);
1054
  rte_unhide_dummy_routes(net, &dummy);
1055
  rte_update_unlock();
1056
  return;
1057

    
1058
 drop:
1059
  rte_free(new);
1060
  new = NULL;
1061
  tmpa = NULL;
1062
  goto recalc;
1063
}
1064

    
1065
/* Independent call to rte_announce(), used from next hop
1066
   recalculation, outside of rte_update(). new must be non-NULL */
1067
static inline void 
1068
rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old)
1069
{
1070
  ea_list *tmpa;
1071

    
1072
  rte_update_lock();
1073
  tmpa = make_tmp_attrs(new, rte_update_pool);
1074
  rte_announce(tab, type, n, new, old, NULL, tmpa);
1075
  rte_update_unlock();
1076
}
1077

    
1078
void
1079
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
1080
{
1081
  rte_update_lock();
1082
  rte_recalculate(old->sender, old->net, NULL, NULL, old->attrs->src);
1083
  rte_update_unlock();
1084
}
1085

    
1086
/* Check rtable for best route to given net whether it would be exported do p */
1087
int
1088
rt_examine(rtable *t, ip_addr prefix, int pxlen, struct proto *p, struct filter *filter)
1089
{
1090
  net *n = net_find(t, prefix, pxlen);
1091
  rte *rt = n ? n->routes : NULL;
1092

    
1093
  if (!rte_is_valid(rt))
1094
    return 0;
1095

    
1096
  rte_update_lock();
1097

    
1098
  /* Rest is stripped down export_filter() */
1099
  ea_list *tmpa = make_tmp_attrs(rt, rte_update_pool);
1100
  int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0;
1101
  if (v == RIC_PROCESS)
1102
    v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1103

    
1104
   /* Discard temporary rte */
1105
  if (rt != n->routes)
1106
    rte_free(rt);
1107

    
1108
  rte_update_unlock();
1109

    
1110
  return v > 0;
1111
}
1112

    
1113

    
1114
/**
1115
 * rt_refresh_begin - start a refresh cycle
1116
 * @t: related routing table
1117
 * @ah: related announce hook 
1118
 *
1119
 * This function starts a refresh cycle for given routing table and announce
1120
 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1121
 * routes to the routing table (by rte_update()). After that, all protocol
1122
 * routes (more precisely routes with @ah as @sender) not sent during the
1123
 * refresh cycle but still in the table from the past are pruned. This is
1124
 * implemented by marking all related routes as stale by REF_STALE flag in
1125
 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1126
 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1127
 */
1128
void
1129
rt_refresh_begin(rtable *t, struct announce_hook *ah)
1130
{
1131
  net *n;
1132
  rte *e;
1133

    
1134
  FIB_WALK(&t->fib, fn)
1135
    {
1136
      n = (net *) fn;
1137
      for (e = n->routes; e; e = e->next)
1138
        if (e->sender == ah)
1139
          e->flags |= REF_STALE;
1140
    }
1141
  FIB_WALK_END;
1142
}
1143

    
1144
/**
1145
 * rt_refresh_end - end a refresh cycle
1146
 * @t: related routing table
1147
 * @ah: related announce hook 
1148
 *
1149
 * This function starts a refresh cycle for given routing table and announce
1150
 * hook. See rt_refresh_begin() for description of refresh cycles.
1151
 */
1152
void
1153
rt_refresh_end(rtable *t, struct announce_hook *ah)
1154
{
1155
  int prune = 0;
1156
  net *n;
1157
  rte *e;
1158

    
1159
  FIB_WALK(&t->fib, fn)
1160
    {
1161
      n = (net *) fn;
1162
      for (e = n->routes; e; e = e->next)
1163
        if ((e->sender == ah) && (e->flags & REF_STALE))
1164
          {
1165
            e->flags |= REF_DISCARD;
1166
            prune = 1;
1167
          }
1168
    }
1169
  FIB_WALK_END;
1170

    
1171
  if (prune)
1172
    rt_schedule_prune(t);
1173
}
1174

    
1175

    
1176
/**
1177
 * rte_dump - dump a route
1178
 * @e: &rte to be dumped
1179
 *
1180
 * This functions dumps contents of a &rte to debug output.
1181
 */
1182
void
1183
rte_dump(rte *e)
1184
{
1185
  net *n = e->net;
1186
  debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
1187
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
1188
  rta_dump(e->attrs);
1189
  if (e->attrs->src->proto->proto->dump_attrs)
1190
    e->attrs->src->proto->proto->dump_attrs(e);
1191
  debug("\n");
1192
}
1193

    
1194
/**
1195
 * rt_dump - dump a routing table
1196
 * @t: routing table to be dumped
1197
 *
1198
 * This function dumps contents of a given routing table to debug output.
1199
 */
1200
void
1201
rt_dump(rtable *t)
1202
{
1203
  rte *e;
1204
  net *n;
1205
  struct announce_hook *a;
1206

    
1207
  debug("Dump of routing table <%s>\n", t->name);
1208
#ifdef DEBUGGING
1209
  fib_check(&t->fib);
1210
#endif
1211
  FIB_WALK(&t->fib, fn)
1212
    {
1213
      n = (net *) fn;
1214
      for(e=n->routes; e; e=e->next)
1215
        rte_dump(e);
1216
    }
1217
  FIB_WALK_END;
1218
  WALK_LIST(a, t->hooks)
1219
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
1220
  debug("\n");
1221
}
1222

    
1223
/**
1224
 * rt_dump_all - dump all routing tables
1225
 *
1226
 * This function dumps contents of all routing tables to debug output.
1227
 */
1228
void
1229
rt_dump_all(void)
1230
{
1231
  rtable *t;
1232

    
1233
  WALK_LIST(t, routing_tables)
1234
    rt_dump(t);
1235
}
1236

    
1237
static inline void
1238
rt_schedule_prune(rtable *tab)
1239
{
1240
  rt_mark_for_prune(tab);
1241
  ev_schedule(tab->rt_event);
1242
}
1243

    
1244
static inline void
1245
rt_schedule_gc(rtable *tab)
1246
{
1247
  if (tab->gc_scheduled)
1248
    return;
1249

    
1250
  tab->gc_scheduled = 1;
1251
  ev_schedule(tab->rt_event);
1252
}
1253

    
1254
static inline void
1255
rt_schedule_hcu(rtable *tab)
1256
{
1257
  if (tab->hcu_scheduled)
1258
    return;
1259

    
1260
  tab->hcu_scheduled = 1;
1261
  ev_schedule(tab->rt_event);
1262
}
1263

    
1264
static inline void
1265
rt_schedule_nhu(rtable *tab)
1266
{
1267
  if (tab->nhu_state == 0)
1268
    ev_schedule(tab->rt_event);
1269

    
1270
  /* state change 0->1, 2->3 */
1271
  tab->nhu_state |= 1;
1272
}
1273

    
1274

    
1275
static void
1276
rt_prune_nets(rtable *tab)
1277
{
1278
  struct fib_iterator fit;
1279
  int ncnt = 0, ndel = 0;
1280

    
1281
#ifdef DEBUGGING
1282
  fib_check(&tab->fib);
1283
#endif
1284

    
1285
  FIB_ITERATE_INIT(&fit, &tab->fib);
1286
again:
1287
  FIB_ITERATE_START(&tab->fib, &fit, f)
1288
    {
1289
      net *n = (net *) f;
1290
      ncnt++;
1291
      if (!n->routes)                /* Orphaned FIB entry */
1292
        {
1293
          FIB_ITERATE_PUT(&fit, f);
1294
          fib_delete(&tab->fib, f);
1295
          ndel++;
1296
          goto again;
1297
        }
1298
    }
1299
  FIB_ITERATE_END(f);
1300
  DBG("Pruned %d of %d networks\n", ndel, ncnt);
1301

    
1302
  tab->gc_counter = 0;
1303
  tab->gc_time = now;
1304
  tab->gc_scheduled = 0;
1305
}
1306

    
1307
static void
1308
rt_event(void *ptr)
1309
{
1310
  rtable *tab = ptr;
1311

    
1312
  if (tab->hcu_scheduled)
1313
    rt_update_hostcache(tab);
1314

    
1315
  if (tab->nhu_state)
1316
    rt_next_hop_update(tab);
1317

    
1318
  if (tab->prune_state)
1319
    if (!rt_prune_table(tab))
1320
      {
1321
        /* Table prune unfinished */
1322
        ev_schedule(tab->rt_event);
1323
        return;
1324
      }
1325

    
1326
  if (tab->gc_scheduled)
1327
    {
1328
      rt_prune_nets(tab);
1329
      rt_prune_sources(); // FIXME this should be moved to independent event
1330
    }
1331
}
1332

    
1333
void
1334
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
1335
{
1336
  bzero(t, sizeof(*t));
1337
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
1338
  t->name = name;
1339
  t->config = cf;
1340
  init_list(&t->hooks);
1341
  if (cf)
1342
    {
1343
      t->rt_event = ev_new(p);
1344
      t->rt_event->hook = rt_event;
1345
      t->rt_event->data = t;
1346
      t->gc_time = now;
1347
    }
1348
}
1349

    
1350
/**
1351
 * rt_init - initialize routing tables
1352
 *
1353
 * This function is called during BIRD startup. It initializes the
1354
 * routing table module.
1355
 */
1356
void
1357
rt_init(void)
1358
{
1359
  rta_init();
1360
  rt_table_pool = rp_new(&root_pool, "Routing tables");
1361
  rte_update_pool = lp_new(rt_table_pool, 4080);
1362
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
1363
  init_list(&routing_tables);
1364
}
1365

    
1366

    
1367
static int
1368
rt_prune_step(rtable *tab, int step, int *limit)
1369
{
1370
  static struct tbf rl_flush = TBF_DEFAULT_LOG_LIMITS;
1371
  struct fib_iterator *fit = &tab->prune_fit;
1372

    
1373
  DBG("Pruning route table %s\n", tab->name);
1374
#ifdef DEBUGGING
1375
  fib_check(&tab->fib);
1376
#endif
1377

    
1378
  if (tab->prune_state == RPS_NONE)
1379
    return 1;
1380

    
1381
  if (tab->prune_state == RPS_SCHEDULED)
1382
    {
1383
      FIB_ITERATE_INIT(fit, &tab->fib);
1384
      tab->prune_state = RPS_RUNNING;
1385
    }
1386

    
1387
again:
1388
  FIB_ITERATE_START(&tab->fib, fit, fn)
1389
    {
1390
      net *n = (net *) fn;
1391
      rte *e;
1392

    
1393
    rescan:
1394
      for (e=n->routes; e; e=e->next)
1395
        if (e->sender->proto->flushing ||
1396
            (e->flags & REF_DISCARD) ||
1397
            (step && e->attrs->src->proto->flushing))
1398
          {
1399
            if (*limit <= 0)
1400
              {
1401
                FIB_ITERATE_PUT(fit, fn);
1402
                return 0;
1403
              }
1404

    
1405
            if (step)
1406
              log_rl(&rl_flush, L_WARN "Route %I/%d from %s still in %s after flush",
1407
                  n->n.prefix, n->n.pxlen, e->attrs->src->proto->name, tab->name);
1408

    
1409
            rte_discard(tab, e);
1410
            (*limit)--;
1411

    
1412
            goto rescan;
1413
          }
1414
      if (!n->routes)                /* Orphaned FIB entry */
1415
        {
1416
          FIB_ITERATE_PUT(fit, fn);
1417
          fib_delete(&tab->fib, fn);
1418
          goto again;
1419
        }
1420
    }
1421
  FIB_ITERATE_END(fn);
1422

    
1423
#ifdef DEBUGGING
1424
  fib_check(&tab->fib);
1425
#endif
1426

    
1427
  tab->prune_state = RPS_NONE;
1428
  return 1;
1429
}
1430

    
1431
/**
1432
 * rt_prune_table - prune a routing table
1433
 *
1434
 * This function scans the routing table @tab and removes routes belonging to
1435
 * flushing protocols, discarded routes and also stale network entries, in a
1436
 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1437
 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1438
 * protocol flushing loop, but it is called from rt_event() for just one routing
1439
 * table.
1440
 *
1441
 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1442
 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1443
 */
1444
static inline int
1445
rt_prune_table(rtable *tab)
1446
{
1447
  int limit = 512;
1448
  return rt_prune_step(tab, 0, &limit);
1449
}
1450

    
1451
/**
1452
 * rt_prune_loop - prune routing tables
1453
 *
1454
 * The prune loop scans routing tables and removes routes belonging to flushing
1455
 * protocols, discarded routes and also stale network entries. Returns 1 when
1456
 * all such routes are pruned. It is a part of the protocol flushing loop.
1457
 *
1458
 * The prune loop runs in two steps. In the first step it prunes just the routes
1459
 * with flushing senders (in explicitly marked tables) so the route removal is
1460
 * propagated as usual. In the second step, all remaining relevant routes are
1461
 * removed. Ideally, there shouldn't be any, but it happens when pipe filters
1462
 * are changed.
1463
 */
1464
int
1465
rt_prune_loop(void)
1466
{
1467
  static int step = 0;
1468
  int limit = 512;
1469
  rtable *t;
1470

    
1471
 again:
1472
  WALK_LIST(t, routing_tables)
1473
    if (! rt_prune_step(t, step, &limit))
1474
      return 0;
1475

    
1476
  if (step == 0)
1477
    {
1478
      /* Prepare for the second step */
1479
      WALK_LIST(t, routing_tables)
1480
        t->prune_state = RPS_SCHEDULED;
1481

    
1482
      step = 1;
1483
      goto again;
1484
    }
1485

    
1486
  /* Done */
1487
  step = 0;
1488
  return 1;
1489
}
1490

    
1491
void
1492
rt_preconfig(struct config *c)
1493
{
1494
  struct symbol *s = cf_find_symbol("master");
1495

    
1496
  init_list(&c->tables);
1497
  c->master_rtc = rt_new_table(s);
1498
}
1499

    
1500

    
1501
/* 
1502
 * Some functions for handing internal next hop updates
1503
 * triggered by rt_schedule_nhu().
1504
 */
1505

    
1506
static inline int
1507
rta_next_hop_outdated(rta *a)
1508
{
1509
  struct hostentry *he = a->hostentry;
1510

    
1511
  if (!he)
1512
    return 0;
1513

    
1514
  if (!he->src)
1515
    return a->dest != RTD_UNREACHABLE;
1516

    
1517
  return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) ||
1518
    (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
1519
    !mpnh_same(a->nexthops, he->src->nexthops);
1520
}
1521

    
1522
static inline void
1523
rta_apply_hostentry(rta *a, struct hostentry *he)
1524
{
1525
  a->hostentry = he;
1526
  a->iface = he->src ? he->src->iface : NULL;
1527
  a->gw = he->gw;
1528
  a->dest = he->dest;
1529
  a->igp_metric = he->igp_metric;
1530
  a->nexthops = he->src ? he->src->nexthops : NULL;
1531
}
1532

    
1533
static inline rte *
1534
rt_next_hop_update_rte(rtable *tab, rte *old)
1535
{
1536
  rta a;
1537
  memcpy(&a, old->attrs, sizeof(rta));
1538
  rta_apply_hostentry(&a, old->attrs->hostentry);
1539
  a.aflags = 0;
1540

    
1541
  rte *e = sl_alloc(rte_slab);
1542
  memcpy(e, old, sizeof(rte));
1543
  e->attrs = rta_lookup(&a);
1544

    
1545
  return e;
1546
}
1547

    
1548
static inline int
1549
rt_next_hop_update_net(rtable *tab, net *n)
1550
{
1551
  rte **k, *e, *new, *old_best, **new_best;
1552
  int count = 0;
1553
  int free_old_best = 0;
1554

    
1555
  old_best = n->routes;
1556
  if (!old_best)
1557
    return 0;
1558

    
1559
  for (k = &n->routes; e = *k; k = &e->next)
1560
    if (rta_next_hop_outdated(e->attrs))
1561
      {
1562
        new = rt_next_hop_update_rte(tab, e);
1563
        *k = new;
1564

    
1565
        rte_announce_i(tab, RA_ANY, n, new, e);
1566
        rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
1567

    
1568
        /* Call a pre-comparison hook */
1569
        /* Not really an efficient way to compute this */
1570
        if (e->attrs->src->proto->rte_recalculate)
1571
          e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
1572

    
1573
        if (e != old_best)
1574
          rte_free_quick(e);
1575
        else /* Freeing of the old best rte is postponed */
1576
          free_old_best = 1;
1577

    
1578
        e = new;
1579
        count++;
1580
      }
1581

    
1582
  if (!count)
1583
    return 0;
1584

    
1585
  /* Find the new best route */
1586
  new_best = NULL;
1587
  for (k = &n->routes; e = *k; k = &e->next)
1588
    {
1589
      if (!new_best || rte_better(e, *new_best))
1590
        new_best = k;
1591
    }
1592

    
1593
  /* Relink the new best route to the first position */
1594
  new = *new_best;
1595
  if (new != n->routes)
1596
    {
1597
      *new_best = new->next;
1598
      new->next = n->routes;
1599
      n->routes = new;
1600
    }
1601

    
1602
  /* Announce the new best route */
1603
  if (new != old_best)
1604
    {
1605
      rte_announce_i(tab, RA_OPTIMAL, n, new, old_best);
1606
      rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
1607
    }
1608

    
1609
   if (free_old_best)
1610
    rte_free_quick(old_best);
1611

    
1612
  return count;
1613
}
1614

    
1615
static void
1616
rt_next_hop_update(rtable *tab)
1617
{
1618
  struct fib_iterator *fit = &tab->nhu_fit;
1619
  int max_feed = 32;
1620

    
1621
  if (tab->nhu_state == 0)
1622
    return;
1623

    
1624
  if (tab->nhu_state == 1)
1625
    {
1626
      FIB_ITERATE_INIT(fit, &tab->fib);
1627
      tab->nhu_state = 2;
1628
    }
1629

    
1630
  FIB_ITERATE_START(&tab->fib, fit, fn)
1631
    {
1632
      if (max_feed <= 0)
1633
        {
1634
          FIB_ITERATE_PUT(fit, fn);
1635
          ev_schedule(tab->rt_event);
1636
          return;
1637
        }
1638
      max_feed -= rt_next_hop_update_net(tab, (net *) fn);
1639
    }
1640
  FIB_ITERATE_END(fn);
1641

    
1642
  /* state change 2->0, 3->1 */
1643
  tab->nhu_state &= 1;
1644

    
1645
  if (tab->nhu_state > 0)
1646
    ev_schedule(tab->rt_event);
1647
}
1648

    
1649

    
1650
struct rtable_config *
1651
rt_new_table(struct symbol *s)
1652
{
1653
  /* Hack that allows to 'redefine' the master table */
1654
  if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc))
1655
    return s->def;
1656

    
1657
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
1658

    
1659
  cf_define_symbol(s, SYM_TABLE, c);
1660
  c->name = s->name;
1661
  add_tail(&new_config->tables, &c->n);
1662
  c->gc_max_ops = 1000;
1663
  c->gc_min_time = 5;
1664
  return c;
1665
}
1666

    
1667
/**
1668
 * rt_lock_table - lock a routing table
1669
 * @r: routing table to be locked
1670
 *
1671
 * Lock a routing table, because it's in use by a protocol,
1672
 * preventing it from being freed when it gets undefined in a new
1673
 * configuration.
1674
 */
1675
void
1676
rt_lock_table(rtable *r)
1677
{
1678
  r->use_count++;
1679
}
1680

    
1681
/**
1682
 * rt_unlock_table - unlock a routing table
1683
 * @r: routing table to be unlocked
1684
 *
1685
 * Unlock a routing table formerly locked by rt_lock_table(),
1686
 * that is decrease its use count and delete it if it's scheduled
1687
 * for deletion by configuration changes.
1688
 */
1689
void
1690
rt_unlock_table(rtable *r)
1691
{
1692
  if (!--r->use_count && r->deleted)
1693
    {
1694
      struct config *conf = r->deleted;
1695
      DBG("Deleting routing table %s\n", r->name);
1696
      if (r->hostcache)
1697
        rt_free_hostcache(r);
1698
      rem_node(&r->n);
1699
      fib_free(&r->fib);
1700
      rfree(r->rt_event);
1701
      mb_free(r);
1702
      config_del_obstacle(conf);
1703
    }
1704
}
1705

    
1706
/**
1707
 * rt_commit - commit new routing table configuration
1708
 * @new: new configuration
1709
 * @old: original configuration or %NULL if it's boot time config
1710
 *
1711
 * Scan differences between @old and @new configuration and modify
1712
 * the routing tables according to these changes. If @new defines a
1713
 * previously unknown table, create it, if it omits a table existing
1714
 * in @old, schedule it for deletion (it gets deleted when all protocols
1715
 * disconnect from it by calling rt_unlock_table()), if it exists
1716
 * in both configurations, leave it unchanged.
1717
 */
1718
void
1719
rt_commit(struct config *new, struct config *old)
1720
{
1721
  struct rtable_config *o, *r;
1722

    
1723
  DBG("rt_commit:\n");
1724
  if (old)
1725
    {
1726
      WALK_LIST(o, old->tables)
1727
        {
1728
          rtable *ot = o->table;
1729
          if (!ot->deleted)
1730
            {
1731
              struct symbol *sym = cf_find_symbol(o->name);
1732
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
1733
                {
1734
                  DBG("\t%s: same\n", o->name);
1735
                  r = sym->def;
1736
                  r->table = ot;
1737
                  ot->name = r->name;
1738
                  ot->config = r;
1739
                  if (o->sorted != r->sorted)
1740
                    log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
1741
                }
1742
              else
1743
                {
1744
                  DBG("\t%s: deleted\n", o->name);
1745
                  ot->deleted = old;
1746
                  config_add_obstacle(old);
1747
                  rt_lock_table(ot);
1748
                  rt_unlock_table(ot);
1749
                }
1750
            }
1751
        }
1752
    }
1753

    
1754
  WALK_LIST(r, new->tables)
1755
    if (!r->table)
1756
      {
1757
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
1758
        DBG("\t%s: created\n", r->name);
1759
        rt_setup(rt_table_pool, t, r->name, r);
1760
        add_tail(&routing_tables, &t->n);
1761
        r->table = t;
1762
      }
1763
  DBG("\tdone\n");
1764
}
1765

    
1766
static inline void
1767
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
1768
{
1769
  ea_list *tmpa;
1770

    
1771
  rte_update_lock();
1772
  tmpa = make_tmp_attrs(e, rte_update_pool);
1773
  if (type == RA_ACCEPTED)
1774
    rt_notify_accepted(h, n, e, NULL, NULL, tmpa, p->refeeding ? 2 : 1);
1775
  else
1776
    rt_notify_basic(h, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding);
1777
  rte_update_unlock();
1778
}
1779

    
1780
/**
1781
 * rt_feed_baby - advertise routes to a new protocol
1782
 * @p: protocol to be fed
1783
 *
1784
 * This function performs one pass of advertisement of routes to a newly
1785
 * initialized protocol. It's called by the protocol code as long as it
1786
 * has something to do. (We avoid transferring all the routes in single
1787
 * pass in order not to monopolize CPU time.)
1788
 */
1789
int
1790
rt_feed_baby(struct proto *p)
1791
{
1792
  struct announce_hook *h;
1793
  struct fib_iterator *fit;
1794
  int max_feed = 256;
1795

    
1796
  if (!p->feed_ahook)                        /* Need to initialize first */
1797
    {
1798
      if (!p->ahooks)
1799
        return 1;
1800
      DBG("Announcing routes to new protocol %s\n", p->name);
1801
      p->feed_ahook = p->ahooks;
1802
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1803
      goto next_hook;
1804
    }
1805
  fit = p->feed_iterator;
1806

    
1807
again:
1808
  h = p->feed_ahook;
1809
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1810
    {
1811
      net *n = (net *) fn;
1812
      rte *e = n->routes;
1813
      if (max_feed <= 0)
1814
        {
1815
          FIB_ITERATE_PUT(fit, fn);
1816
          return 0;
1817
        }
1818

    
1819
      /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1820

    
1821
      if ((p->accept_ra_types == RA_OPTIMAL) ||
1822
          (p->accept_ra_types == RA_ACCEPTED))
1823
        if (rte_is_valid(e))
1824
          {
1825
            if (p->export_state != ES_FEEDING)
1826
              return 1;  /* In the meantime, the protocol fell down. */
1827
            do_feed_baby(p, p->accept_ra_types, h, n, e);
1828
            max_feed--;
1829
          }
1830

    
1831
      if (p->accept_ra_types == RA_ANY)
1832
        for(e = n->routes; rte_is_valid(e); e = e->next)
1833
          {
1834
            if (p->export_state != ES_FEEDING)
1835
              return 1;  /* In the meantime, the protocol fell down. */
1836
            do_feed_baby(p, RA_ANY, h, n, e);
1837
            max_feed--;
1838
          }
1839
    }
1840
  FIB_ITERATE_END(fn);
1841
  p->feed_ahook = h->next;
1842
  if (!p->feed_ahook)
1843
    {
1844
      mb_free(p->feed_iterator);
1845
      p->feed_iterator = NULL;
1846
      return 1;
1847
    }
1848

    
1849
next_hook:
1850
  h = p->feed_ahook;
1851
  FIB_ITERATE_INIT(fit, &h->table->fib);
1852
  goto again;
1853
}
1854

    
1855
/**
1856
 * rt_feed_baby_abort - abort protocol feeding
1857
 * @p: protocol
1858
 *
1859
 * This function is called by the protocol code when the protocol
1860
 * stops or ceases to exist before the last iteration of rt_feed_baby()
1861
 * has finished.
1862
 */
1863
void
1864
rt_feed_baby_abort(struct proto *p)
1865
{
1866
  if (p->feed_ahook)
1867
    {
1868
      /* Unlink the iterator and exit */
1869
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
1870
      p->feed_ahook = NULL;
1871
    }
1872
}
1873

    
1874

    
1875
static inline unsigned
1876
ptr_hash(void *ptr)
1877
{
1878
  uintptr_t p = (uintptr_t) ptr;
1879
  return p ^ (p << 8) ^ (p >> 16);
1880
}
1881

    
1882
static inline unsigned
1883
hc_hash(ip_addr a, rtable *dep)
1884
{
1885
  return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff;
1886
}
1887

    
1888
static inline void
1889
hc_insert(struct hostcache *hc, struct hostentry *he)
1890
{
1891
  unsigned int k = he->hash_key >> hc->hash_shift;
1892
  he->next = hc->hash_table[k];
1893
  hc->hash_table[k] = he;
1894
}
1895

    
1896
static inline void
1897
hc_remove(struct hostcache *hc, struct hostentry *he)
1898
{
1899
  struct hostentry **hep;
1900
  unsigned int k = he->hash_key >> hc->hash_shift;
1901

    
1902
  for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
1903
  *hep = he->next;
1904
}
1905

    
1906
#define HC_DEF_ORDER 10
1907
#define HC_HI_MARK *4
1908
#define HC_HI_STEP 2
1909
#define HC_HI_ORDER 16                        /* Must be at most 16 */
1910
#define HC_LO_MARK /5
1911
#define HC_LO_STEP 2
1912
#define HC_LO_ORDER 10
1913

    
1914
static void
1915
hc_alloc_table(struct hostcache *hc, unsigned order)
1916
{
1917
  unsigned hsize = 1 << order;
1918
  hc->hash_order = order;
1919
  hc->hash_shift = 16 - order;
1920
  hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
1921
  hc->hash_min = (order <= HC_LO_ORDER) ?  0 : (hsize HC_LO_MARK);
1922

    
1923
  hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
1924
}
1925

    
1926
static void
1927
hc_resize(struct hostcache *hc, unsigned new_order)
1928
{
1929
  unsigned old_size = 1 << hc->hash_order;
1930
  struct hostentry **old_table = hc->hash_table;
1931
  struct hostentry *he, *hen;
1932
  int i;
1933

    
1934
  hc_alloc_table(hc, new_order);
1935
  for (i = 0; i < old_size; i++)
1936
    for (he = old_table[i]; he != NULL; he=hen)
1937
      {
1938
        hen = he->next;
1939
        hc_insert(hc, he);
1940
      }
1941
  mb_free(old_table);
1942
}
1943

    
1944
static struct hostentry *
1945
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
1946
{
1947
  struct hostentry *he = sl_alloc(hc->slab);
1948

    
1949
  he->addr = a;
1950
  he->link = ll;
1951
  he->tab = dep;
1952
  he->hash_key = k;
1953
  he->uc = 0;
1954
  he->src = NULL;
1955

    
1956
  add_tail(&hc->hostentries, &he->ln);
1957
  hc_insert(hc, he);
1958

    
1959
  hc->hash_items++;
1960
  if (hc->hash_items > hc->hash_max)
1961
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
1962

    
1963
  return he;
1964
}
1965

    
1966
static void
1967
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
1968
{
1969
  rta_free(he->src);
1970

    
1971
  rem_node(&he->ln);
1972
  hc_remove(hc, he);
1973
  sl_free(hc->slab, he);
1974

    
1975
  hc->hash_items--;
1976
  if (hc->hash_items < hc->hash_min)
1977
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
1978
}
1979

    
1980
static void
1981
rt_init_hostcache(rtable *tab)
1982
{
1983
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
1984
  init_list(&hc->hostentries);
1985

    
1986
  hc->hash_items = 0;
1987
  hc_alloc_table(hc, HC_DEF_ORDER);
1988
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
1989

    
1990
  hc->lp = lp_new(rt_table_pool, 1008);
1991
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
1992

    
1993
  tab->hostcache = hc;
1994
}
1995

    
1996
static void
1997
rt_free_hostcache(rtable *tab)
1998
{
1999
  struct hostcache *hc = tab->hostcache;
2000

    
2001
  node *n;
2002
  WALK_LIST(n, hc->hostentries)
2003
    {
2004
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
2005
      rta_free(he->src);
2006

    
2007
      if (he->uc)
2008
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
2009
    }
2010

    
2011
  rfree(hc->slab);
2012
  rfree(hc->lp);
2013
  mb_free(hc->hash_table);
2014
  mb_free(hc);
2015
}
2016

    
2017
static void
2018
rt_notify_hostcache(rtable *tab, net *net)
2019
{
2020
  struct hostcache *hc = tab->hostcache;
2021

    
2022
  if (tab->hcu_scheduled)
2023
    return;
2024

    
2025
  if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
2026
    rt_schedule_hcu(tab);
2027
}
2028

    
2029
static int
2030
if_local_addr(ip_addr a, struct iface *i)
2031
{
2032
  struct ifa *b;
2033

    
2034
  WALK_LIST(b, i->addrs)
2035
    if (ipa_equal(a, b->ip))
2036
      return 1;
2037

    
2038
  return 0;
2039
}
2040

    
2041
static u32 
2042
rt_get_igp_metric(rte *rt)
2043
{
2044
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
2045

    
2046
  if (ea)
2047
    return ea->u.data;
2048

    
2049
  rta *a = rt->attrs;
2050

    
2051
#ifdef CONFIG_OSPF
2052
  if ((a->source == RTS_OSPF) ||
2053
      (a->source == RTS_OSPF_IA) ||
2054
      (a->source == RTS_OSPF_EXT1))
2055
    return rt->u.ospf.metric1;
2056
#endif
2057

    
2058
#ifdef CONFIG_RIP
2059
  if (a->source == RTS_RIP)
2060
    return rt->u.rip.metric;
2061
#endif
2062

    
2063
  /* Device routes */
2064
  if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
2065
    return 0;
2066

    
2067
  return IGP_METRIC_UNKNOWN;
2068
}
2069

    
2070
static int
2071
rt_update_hostentry(rtable *tab, struct hostentry *he)
2072
{
2073
  rta *old_src = he->src;
2074
  int pxlen = 0;
2075

    
2076
  /* Reset the hostentry */ 
2077
  he->src = NULL;
2078
  he->gw = IPA_NONE;
2079
  he->dest = RTD_UNREACHABLE;
2080
  he->igp_metric = 0;
2081

    
2082
  net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
2083
  if (n)
2084
    {
2085
      rte *e = n->routes;
2086
      rta *a = e->attrs;
2087
      pxlen = n->n.pxlen;
2088

    
2089
      if (a->hostentry)
2090
        {
2091
          /* Recursive route should not depend on another recursive route */
2092
          log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d",
2093
              he->addr, n->n.prefix, pxlen);
2094
          goto done;
2095
        }
2096

    
2097
      if (a->dest == RTD_DEVICE)
2098
        {
2099
          if (if_local_addr(he->addr, a->iface))
2100
            {
2101
              /* The host address is a local address, this is not valid */
2102
              log(L_WARN "Next hop address %I is a local address of iface %s",
2103
                  he->addr, a->iface->name);
2104
              goto done;
2105
                  }
2106

    
2107
          /* The host is directly reachable, use link as a gateway */
2108
          he->gw = he->link;
2109
          he->dest = RTD_ROUTER;
2110
        }
2111
      else
2112
        {
2113
          /* The host is reachable through some route entry */
2114
          he->gw = a->gw;
2115
          he->dest = a->dest;
2116
        }
2117

    
2118
      he->src = rta_clone(a);
2119
      he->igp_metric = rt_get_igp_metric(e);
2120
    }
2121

    
2122
 done:
2123
  /* Add a prefix range to the trie */
2124
  trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH);
2125

    
2126
  rta_free(old_src);
2127
  return old_src != he->src;
2128
}
2129

    
2130
static void
2131
rt_update_hostcache(rtable *tab)
2132
{
2133
  struct hostcache *hc = tab->hostcache;
2134
  struct hostentry *he;
2135
  node *n, *x;
2136

    
2137
  /* Reset the trie */
2138
  lp_flush(hc->lp);
2139
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2140

    
2141
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
2142
    {
2143
      he = SKIP_BACK(struct hostentry, ln, n);
2144
      if (!he->uc)
2145
        {
2146
          hc_delete_hostentry(hc, he);
2147
          continue;
2148
        }
2149

    
2150
      if (rt_update_hostentry(tab, he))
2151
        rt_schedule_nhu(he->tab);
2152
    }
2153

    
2154
  tab->hcu_scheduled = 0;
2155
}
2156

    
2157
static struct hostentry *
2158
rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
2159
{
2160
  struct hostentry *he;
2161

    
2162
  if (!tab->hostcache)
2163
    rt_init_hostcache(tab);
2164

    
2165
  unsigned int k = hc_hash(a, dep);
2166
  struct hostcache *hc = tab->hostcache;
2167
  for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
2168
    if (ipa_equal(he->addr, a) && (he->tab == dep))
2169
      return he;
2170

    
2171
  he = hc_new_hostentry(hc, a, ll, dep, k);
2172
  rt_update_hostentry(tab, he);
2173
  return he;
2174
}
2175

    
2176
void
2177
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll)
2178
{
2179
  rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep));
2180
}
2181

    
2182

    
2183
/*
2184
 *  CLI commands
2185
 */
2186

    
2187
static void
2188
rt_format_via(rte *e, byte *via)
2189
{
2190
  rta *a = e->attrs;
2191

    
2192
  switch (a->dest)
2193
    {
2194
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
2195
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
2196
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
2197
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
2198
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
2199
    case RTD_MULTIPATH:        bsprintf(via, "multipath"); break;
2200
    default:                bsprintf(via, "???");
2201
    }
2202
}
2203

    
2204
static void
2205
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
2206
{
2207
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8];
2208
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
2209
  rta *a = e->attrs;
2210
  int primary = (e->net->routes == e);
2211
  int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
2212
  void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs);
2213
  struct mpnh *nh;
2214

    
2215
  rt_format_via(e, via);
2216
  tm_format_datetime(tm, &config->tf_route, e->lastmod);
2217
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
2218
    bsprintf(from, " from %I", a->from);
2219
  else
2220
    from[0] = 0;
2221

    
2222
  get_route_info = a->src->proto->proto->get_route_info;
2223
  if (get_route_info || d->verbose)
2224
    {
2225
      /* Need to normalize the extended attributes */
2226
      ea_list *t = tmpa;
2227
      t = ea_append(t, a->eattrs);
2228
      tmpa = alloca(ea_scan(t));
2229
      ea_merge(t, tmpa);
2230
      ea_sort(tmpa);
2231
    }
2232
  if (get_route_info)
2233
    get_route_info(e, info, tmpa);
2234
  else
2235
    bsprintf(info, " (%d)", e->pref);
2236
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->src->proto->name,
2237
             tm, from, primary ? (sync_error ? " !" : " *") : "", info);
2238
  for (nh = a->nexthops; nh; nh = nh->next)
2239
    cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1);
2240
  if (d->verbose)
2241
    rta_show(c, a, tmpa);
2242
}
2243

    
2244
static void
2245
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
2246
{
2247
  rte *e, *ee;
2248
  byte ia[STD_ADDRESS_P_LENGTH+8];
2249
  struct ea_list *tmpa;
2250
  struct announce_hook *a = NULL;
2251
  int first = 1;
2252
  int pass = 0;
2253

    
2254
  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
2255

    
2256
  if (d->export_mode)
2257
    {
2258
      if (! d->export_protocol->rt_notify)
2259
        return;
2260

    
2261
      a = proto_find_announce_hook(d->export_protocol, d->table);
2262
      if (!a)
2263
        return;
2264
    }
2265

    
2266
  for (e = n->routes; e; e = e->next)
2267
    {
2268
      if (rte_is_filtered(e) != d->filtered)
2269
        continue;
2270

    
2271
      d->rt_counter++;
2272
      d->net_counter += first;
2273
      first = 0;
2274

    
2275
      if (pass)
2276
        continue;
2277

    
2278
      ee = e;
2279
      rte_update_lock();                /* We use the update buffer for filtering */
2280
      tmpa = make_tmp_attrs(e, rte_update_pool);
2281

    
2282
      if (d->export_mode)
2283
        {
2284
          struct proto *ep = d->export_protocol;
2285
          int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0;
2286

    
2287
          if (ep->accept_ra_types == RA_OPTIMAL)
2288
            pass = 1;
2289

    
2290
          if (ic < 0)
2291
            goto skip;
2292

    
2293
          if (d->export_mode > RSEM_PREEXPORT)
2294
            {
2295
              /*
2296
               * FIXME - This shows what should be exported according to current
2297
               * filters, but not what was really exported. 'configure soft'
2298
               * command may change the export filter and do not update routes.
2299
               */
2300
              int do_export = (ic > 0) ||
2301
                (f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
2302

    
2303
              if (do_export != (d->export_mode == RSEM_EXPORT))
2304
                goto skip;
2305

    
2306
              if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED))
2307
                pass = 1;
2308
            }
2309
        }
2310

    
2311
      if (d->show_protocol && (d->show_protocol != e->attrs->src->proto))
2312
        goto skip;
2313

    
2314
      if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
2315
        goto skip;
2316

    
2317
      d->show_counter++;
2318
      if (d->stats < 2)
2319
        rt_show_rte(c, ia, e, d, tmpa);
2320
      ia[0] = 0;
2321

    
2322
    skip:
2323
      if (e != ee)
2324
      {
2325
        rte_free(e);
2326
        e = ee;
2327
      }
2328
      rte_update_unlock();
2329

    
2330
      if (d->primary_only)
2331
        break;
2332
    }
2333
}
2334

    
2335
static void
2336
rt_show_cont(struct cli *c)
2337
{
2338
  struct rt_show_data *d = c->rover;
2339
#ifdef DEBUGGING
2340
  unsigned max = 4;
2341
#else
2342
  unsigned max = 64;
2343
#endif
2344
  struct fib *fib = &d->table->fib;
2345
  struct fib_iterator *it = &d->fit;
2346

    
2347
  FIB_ITERATE_START(fib, it, f)
2348
    {
2349
      net *n = (net *) f;
2350
      if (d->running_on_config && d->running_on_config != config)
2351
        {
2352
          cli_printf(c, 8004, "Stopped due to reconfiguration");
2353
          goto done;
2354
        }
2355
      if (d->export_protocol && (d->export_protocol->export_state == ES_DOWN))
2356
        {
2357
          cli_printf(c, 8005, "Protocol is down");
2358
          goto done;
2359
        }
2360
      if (!max--)
2361
        {
2362
          FIB_ITERATE_PUT(it, f);
2363
          return;
2364
        }
2365
      rt_show_net(c, n, d);
2366
    }
2367
  FIB_ITERATE_END(f);
2368
  if (d->stats)
2369
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
2370
  else
2371
    cli_printf(c, 0, "");
2372
done:
2373
  c->cont = c->cleanup = NULL;
2374
}
2375

    
2376
static void
2377
rt_show_cleanup(struct cli *c)
2378
{
2379
  struct rt_show_data *d = c->rover;
2380

    
2381
  /* Unlink the iterator */
2382
  fit_get(&d->table->fib, &d->fit);
2383
}
2384

    
2385
void
2386
rt_show(struct rt_show_data *d)
2387
{
2388
  net *n;
2389

    
2390
  /* Default is either a master table or a table related to a respective protocol */
2391
  if (!d->table && d->export_protocol) d->table = d->export_protocol->table;
2392
  if (!d->table && d->show_protocol) d->table = d->show_protocol->table;
2393
  if (!d->table) d->table = config->master_rtc->table;
2394

    
2395
  /* Filtered routes are neither exported nor have sensible ordering */
2396
  if (d->filtered && (d->export_mode || d->primary_only))
2397
    cli_msg(0, "");
2398

    
2399
  if (d->pxlen == 256)
2400
    {
2401
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
2402
      this_cli->cont = rt_show_cont;
2403
      this_cli->cleanup = rt_show_cleanup;
2404
      this_cli->rover = d;
2405
    }
2406
  else
2407
    {
2408
      if (d->show_for)
2409
        n = net_route(d->table, d->prefix, d->pxlen);
2410
      else
2411
        n = net_find(d->table, d->prefix, d->pxlen);
2412

    
2413
      if (n)
2414
        rt_show_net(this_cli, n, d);
2415

    
2416
      if (d->rt_counter)
2417
        cli_msg(0, "");
2418
      else
2419
        cli_msg(8001, "Network not in table");
2420
    }
2421
}
2422

    
2423
/*
2424
 *  Documentation for functions declared inline in route.h
2425
 */
2426
#if 0
2427

2428
/**
2429
 * net_find - find a network entry
2430
 * @tab: a routing table
2431
 * @addr: address of the network
2432
 * @len: length of the network prefix
2433
 *
2434
 * net_find() looks up the given network in routing table @tab and
2435
 * returns a pointer to its &net entry or %NULL if no such network
2436
 * exists.
2437
 */
2438
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
2439
{ DUMMY; }
2440

2441
/**
2442
 * net_get - obtain a network entry
2443
 * @tab: a routing table
2444
 * @addr: address of the network
2445
 * @len: length of the network prefix
2446
 *
2447
 * net_get() looks up the given network in routing table @tab and
2448
 * returns a pointer to its &net entry. If no such entry exists, it's
2449
 * created.
2450
 */
2451
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
2452
{ DUMMY; }
2453

2454
/**
2455
 * rte_cow - copy a route for writing
2456
 * @r: a route entry to be copied
2457
 *
2458
 * rte_cow() takes a &rte and prepares it for modification. The exact action
2459
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2460
 * just returned unchanged, else a new temporary entry with the same contents
2461
 * is created.
2462
 *
2463
 * The primary use of this function is inside the filter machinery -- when
2464
 * a filter wants to modify &rte contents (to change the preference or to
2465
 * attach another set of attributes), it must ensure that the &rte is not
2466
 * shared with anyone else (and especially that it isn't stored in any routing
2467
 * table).
2468
 *
2469
 * Result: a pointer to the new writable &rte.
2470
 */
2471
static inline rte * rte_cow(rte *r)
2472
{ DUMMY; }
2473

2474
#endif