Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (59.7 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(uint 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(uint 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 *new0, rte *old0, ea_list *tmpa, int refeed)
351
{
352
  struct proto *p = ah->proto;
353
  struct proto_stats *stats = ah->stats;
354

    
355
  rte *new = new0;
356
  rte *old = old0;
357
  rte *new_free = NULL;
358
  rte *old_free = NULL;
359

    
360
  if (new)
361
    stats->exp_updates_received++;
362
  else
363
    stats->exp_withdraws_received++;
364

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

    
385
  if (new)
386
    new = export_filter(ah, new, &new_free, &tmpa, 0);
387

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

    
391
  if (!new && !old)
392
  {
393
    /*
394
     * As mentioned above, 'old' value may be incorrect in some race conditions.
395
     * We generally ignore it with the exception of withdraw to pipe protocol.
396
     * In that case we rather propagate unfiltered withdraws regardless of
397
     * export filters to ensure that when a protocol is flushed, its routes are
398
     * removed from all tables. Possible spurious unfiltered withdraws are not
399
     * problem here as they are ignored if there is no corresponding route at
400
     * the other end of the pipe. We directly call rt_notify() hook instead of
401
     * do_rt_notify() to avoid logging and stat counters.
402
     */
403

    
404
#ifdef CONFIG_PIPE
405
    if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto))
406
      p->rt_notify(p, ah->table, net, NULL, old0, NULL);
407
#endif
408

    
409
    return;
410
  }
411

    
412
  do_rt_notify(ah, net, new, old, tmpa, refeed);
413

    
414
  /* Discard temporary rte's */
415
  if (new_free)
416
    rte_free(new_free);
417
  if (old_free)
418
    rte_free(old_free);
419
}
420

    
421
static void
422
rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old,
423
                   ea_list *tmpa, int feed)
424
{
425
  // struct proto *p = ah->proto;
426
  struct proto_stats *stats = ah->stats;
427

    
428
  rte *new_best = NULL;
429
  rte *old_best = NULL;
430
  rte *new_free = NULL;
431
  rte *old_free = NULL;
432
  rte *r;
433

    
434
  /* Used to track whether we met old_changed position. If before_old is NULL
435
     old_changed was the first and we met it implicitly before current best route. */
436
  int old_meet = old_changed && !before_old;
437

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

    
442
  if (new_changed)
443
    stats->exp_updates_received++;
444
  else
445
    stats->exp_withdraws_received++;
446

    
447
  /* First, find the new_best route - first accepted by filters */
448
  for (r=net->routes; rte_is_valid(r); r=r->next)
449
    {
450
      if (new_best = export_filter(ah, r, &new_free, &tmpa, 0))
451
        break;
452

    
453
      /* Note if we walked around the position of old_changed route */
454
      if (r == before_old)
455
        old_meet = 1;
456
    }
457

    
458
  /* 
459
   * Second, handle the feed case. That means we do not care for
460
   * old_best. It is NULL for feed, and the new_best for refeed. 
461
   * For refeed, there is a hack similar to one in rt_notify_basic()
462
   * to ensure withdraws in case of changed filters
463
   */
464
  if (feed)
465
    {
466
      if (feed == 2)        /* refeed */
467
        old_best = new_best ? new_best :
468
          (rte_is_valid(net->routes) ? net->routes : NULL);
469
      else
470
        old_best = NULL;
471

    
472
      if (!new_best && !old_best)
473
        return;
474

    
475
      goto found;
476
    }
477

    
478
  /*
479
   * Now, we find the old_best route. Generally, it is the same as the
480
   * new_best, unless new_best is the same as new_changed or
481
   * old_changed is accepted before new_best.
482
   *
483
   * There are four cases:
484
   *
485
   * - We would find and accept old_changed before new_best, therefore
486
   *   old_changed is old_best. In remaining cases we suppose this
487
   *   is not true.
488
   *
489
   * - We found no new_best, therefore there is also no old_best and
490
   *   we ignore this withdraw.
491
   *
492
   * - We found new_best different than new_changed, therefore
493
   *   old_best is the same as new_best and we ignore this update.
494
   *
495
   * - We found new_best the same as new_changed, therefore it cannot
496
   *   be old_best and we have to continue search for old_best.
497
   */
498

    
499
  /* First case */
500
  if (old_meet)
501
    if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
502
      goto found;
503

    
504
  /* Second case */
505
  if (!new_best)
506
    return;
507

    
508
  /* Third case, we use r instead of new_best, because export_filter() could change it */
509
  if (r != new_changed)
510
    {
511
      if (new_free)
512
        rte_free(new_free);
513
      return;
514
    }
515

    
516
  /* Fourth case */
517
  for (r=r->next; rte_is_valid(r); r=r->next)
518
    {
519
      if (old_best = export_filter(ah, r, &old_free, NULL, 1))
520
        goto found;
521

    
522
      if (r == before_old)
523
        if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
524
          goto found;
525
    }
526

    
527
  /* Implicitly, old_best is NULL and new_best is non-NULL */
528

    
529
 found:
530
  do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2));
531

    
532
  /* Discard temporary rte's */
533
  if (new_free)
534
    rte_free(new_free);
535
  if (old_free)
536
    rte_free(old_free);
537
}
538

    
539
/**
540
 * rte_announce - announce a routing table change
541
 * @tab: table the route has been added to
542
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
543
 * @net: network in question
544
 * @new: the new route to be announced
545
 * @old: the previous route for the same network
546
 * @tmpa: a list of temporary attributes belonging to the new route
547
 *
548
 * This function gets a routing table update and announces it
549
 * to all protocols that acccepts given type of route announcement
550
 * and are connected to the same table by their announcement hooks.
551
 *
552
 * Route announcement of type RA_OPTIMAL si generated when optimal
553
 * route (in routing table @tab) changes. In that case @old stores the
554
 * old optimal route.
555
 *
556
 * Route announcement of type RA_ANY si generated when any route (in
557
 * routing table @tab) changes In that case @old stores the old route
558
 * from the same protocol.
559
 *
560
 * For each appropriate protocol, we first call its import_control()
561
 * hook which performs basic checks on the route (each protocol has a
562
 * right to veto or force accept of the route before any filter is
563
 * asked) and adds default values of attributes specific to the new
564
 * protocol (metrics, tags etc.).  Then it consults the protocol's
565
 * export filter and if it accepts the route, the rt_notify() hook of
566
 * the protocol gets called.
567
 */
568
static void
569
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *before_old, ea_list *tmpa)
570
{
571
  if (!rte_is_valid(old))
572
    old = before_old = NULL;
573

    
574
  if (!rte_is_valid(new))
575
    new = NULL;
576

    
577
  if (!old && !new)
578
    return;
579

    
580
  if (type == RA_OPTIMAL)
581
    {
582
      if (new)
583
        new->attrs->src->proto->stats.pref_routes++;
584
      if (old)
585
        old->attrs->src->proto->stats.pref_routes--;
586

    
587
      if (tab->hostcache)
588
        rt_notify_hostcache(tab, net);
589
    }
590

    
591
  struct announce_hook *a;
592
  WALK_LIST(a, tab->hooks)
593
    {
594
      ASSERT(a->proto->export_state != ES_DOWN);
595
      if (a->proto->accept_ra_types == type)
596
        if (type == RA_ACCEPTED)
597
          rt_notify_accepted(a, net, new, old, before_old, tmpa, 0);
598
        else
599
          rt_notify_basic(a, net, new, old, tmpa, 0);
600
    }
601
}
602

    
603
static inline int
604
rte_validate(rte *e)
605
{
606
  int c;
607
  net *n = e->net;
608

    
609
  if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
610
    {
611
      log(L_WARN "Ignoring bogus prefix %I/%d received via %s",
612
          n->n.prefix, n->n.pxlen, e->sender->proto->name);
613
      return 0;
614
    }
615

    
616
  c = ipa_classify_net(n->n.prefix);
617
  if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
618
    {
619
      log(L_WARN "Ignoring bogus route %I/%d received via %s",
620
          n->n.prefix, n->n.pxlen, e->sender->proto->name);
621
      return 0;
622
    }
623

    
624
  return 1;
625
}
626

    
627
/**
628
 * rte_free - delete a &rte
629
 * @e: &rte to be deleted
630
 *
631
 * rte_free() deletes the given &rte from the routing table it's linked to.
632
 */
633
void
634
rte_free(rte *e)
635
{
636
  if (rta_is_cached(e->attrs))
637
    rta_free(e->attrs);
638
  sl_free(rte_slab, e);
639
}
640

    
641
static inline void
642
rte_free_quick(rte *e)
643
{
644
  rta_free(e->attrs);
645
  sl_free(rte_slab, e);
646
}
647

    
648
static int
649
rte_same(rte *x, rte *y)
650
{
651
  return
652
    x->attrs == y->attrs &&
653
    x->flags == y->flags &&
654
    x->pflags == y->pflags &&
655
    x->pref == y->pref &&
656
    (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y));
657
}
658

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

    
661
static void
662
rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, struct rte_src *src)
663
{
664
  struct proto *p = ah->proto;
665
  struct rtable *table = ah->table;
666
  struct proto_stats *stats = ah->stats;
667
  static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
668
  rte *before_old = NULL;
669
  rte *old_best = net->routes;
670
  rte *old = NULL;
671
  rte **k;
672

    
673
  k = &net->routes;                        /* Find and remove original route from the same protocol */
674
  while (old = *k)
675
    {
676
      if (old->attrs->src == src)
677
        {
678
          /* If there is the same route in the routing table but from
679
           * a different sender, then there are two paths from the
680
           * source protocol to this routing table through transparent
681
           * pipes, which is not allowed.
682
           *
683
           * We log that and ignore the route. If it is withdraw, we
684
           * ignore it completely (there might be 'spurious withdraws',
685
           * see FIXME in do_rte_announce())
686
           */
687
          if (old->sender->proto != p)
688
            {
689
              if (new)
690
                {
691
                  log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %I/%d to table %s",
692
                      net->n.prefix, net->n.pxlen, table->name);
693
                  rte_free_quick(new);
694
                }
695
              return;
696
            }
697

    
698
          if (new && rte_same(old, new))
699
            {
700
              /* No changes, ignore the new route */
701

    
702
              if (!rte_is_filtered(new))
703
                {
704
                  stats->imp_updates_ignored++;
705
                  rte_trace_in(D_ROUTES, p, new, "ignored");
706
                }
707

    
708
              rte_free_quick(new);
709
#ifdef CONFIG_RIP
710
              /* lastmod is used internally by RIP as the last time
711
                 when the route was received. */
712
              if (src->proto->proto == &proto_rip)
713
                old->lastmod = now;
714
#endif
715
              return;
716
            }
717
          *k = old->next;
718
          break;
719
        }
720
      k = &old->next;
721
      before_old = old;
722
    }
723

    
724
  if (!old)
725
    before_old = NULL;
726

    
727
  if (!old && !new)
728
    {
729
      stats->imp_withdraws_ignored++;
730
      return;
731
    }
732

    
733
  int new_ok = rte_is_ok(new);
734
  int old_ok = rte_is_ok(old);
735

    
736
  struct proto_limit *l = ah->rx_limit;
737
  if (l && !old && new)
738
    {
739
      u32 all_routes = stats->imp_routes + stats->filt_routes;
740

    
741
      if (all_routes >= l->limit)
742
        proto_notify_limit(ah, l, PLD_RX, all_routes);
743

    
744
      if (l->state == PLS_BLOCKED)
745
        {
746
          /* In receive limit the situation is simple, old is NULL so
747
             we just free new and exit like nothing happened */
748

    
749
          stats->imp_updates_ignored++;
750
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
751
          rte_free_quick(new);
752
          return;
753
        }
754
    }
755

    
756
  l = ah->in_limit;
757
  if (l && !old_ok && new_ok)
758
    {
759
      if (stats->imp_routes >= l->limit)
760
        proto_notify_limit(ah, l, PLD_IN, stats->imp_routes);
761

    
762
      if (l->state == PLS_BLOCKED)
763
        {
764
          /* In import limit the situation is more complicated. We
765
             shouldn't just drop the route, we should handle it like
766
             it was filtered. We also have to continue the route
767
             processing if old or new is non-NULL, but we should exit
768
             if both are NULL as this case is probably assumed to be
769
             already handled. */
770

    
771
          stats->imp_updates_ignored++;
772
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
773

    
774
          if (ah->in_keep_filtered)
775
            new->flags |= REF_FILTERED;
776
          else
777
            { rte_free_quick(new); new = NULL; }
778

    
779
          /* Note that old && !new could be possible when
780
             ah->in_keep_filtered changed in the recent past. */
781

    
782
          if (!old && !new)
783
            return;
784

    
785
          new_ok = 0;
786
          goto skip_stats1;
787
        }
788
    }
789

    
790
  if (new_ok)
791
    stats->imp_updates_accepted++;
792
  else if (old_ok)
793
    stats->imp_withdraws_accepted++;
794
  else
795
    stats->imp_withdraws_ignored++;
796

    
797
 skip_stats1:
798

    
799
  if (new)
800
    rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
801
  if (old)
802
    rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
803

    
804
  if (table->config->sorted)
805
    {
806
      /* If routes are sorted, just insert new route to appropriate position */
807
      if (new)
808
        {
809
          if (before_old && !rte_better(new, before_old))
810
            k = &before_old->next;
811
          else
812
            k = &net->routes;
813

    
814
          for (; *k; k=&(*k)->next)
815
            if (rte_better(new, *k))
816
              break;
817

    
818
          new->next = *k;
819
          *k = new;
820
        }
821
    }
822
  else
823
    {
824
      /* If routes are not sorted, find the best route and move it on
825
         the first position. There are several optimized cases. */
826

    
827
      if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
828
        goto do_recalculate;
829

    
830
      if (new && rte_better(new, old_best))
831
        {
832
          /* The first case - the new route is cleary optimal,
833
             we link it at the first position */
834

    
835
          new->next = net->routes;
836
          net->routes = new;
837
        }
838
      else if (old == old_best)
839
        {
840
          /* The second case - the old best route disappeared, we add the
841
             new route (if we have any) to the list (we don't care about
842
             position) and then we elect the new optimal route and relink
843
             that route at the first position and announce it. New optimal
844
             route might be NULL if there is no more routes */
845

    
846
        do_recalculate:
847
          /* Add the new route to the list */
848
          if (new)
849
            {
850
              new->next = net->routes;
851
              net->routes = new;
852
            }
853

    
854
          /* Find a new optimal route (if there is any) */
855
          if (net->routes)
856
            {
857
              rte **bp = &net->routes;
858
              for (k=&(*bp)->next; *k; k=&(*k)->next)
859
                if (rte_better(*k, *bp))
860
                  bp = k;
861

    
862
              /* And relink it */
863
              rte *best = *bp;
864
              *bp = best->next;
865
              best->next = net->routes;
866
              net->routes = best;
867
            }
868
        }
869
      else if (new)
870
        {
871
          /* The third case - the new route is not better than the old
872
             best route (therefore old_best != NULL) and the old best
873
             route was not removed (therefore old_best == net->routes).
874
             We just link the new route after the old best route. */
875

    
876
          ASSERT(net->routes != NULL);
877
          new->next = net->routes->next;
878
          net->routes->next = new;
879
        }
880
      /* The fourth (empty) case - suboptimal route was removed, nothing to do */
881
    }
882

    
883
  if (new)
884
    new->lastmod = now;
885

    
886
  /* Log the route change */
887
  if (p->debug & D_ROUTES)
888
    {
889
      if (new_ok)
890
        rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added");
891
      else if (old_ok)
892
        {
893
          if (old != old_best)
894
            rte_trace(p, old, '>', "removed");
895
          else if (rte_is_ok(net->routes))
896
            rte_trace(p, old, '>', "removed [replaced]");
897
          else
898
            rte_trace(p, old, '>', "removed [sole]");
899
        }
900
    }
901

    
902
  /* Propagate the route change */
903
  rte_announce(table, RA_ANY, net, new, old, NULL, tmpa);
904
  if (net->routes != old_best)
905
    rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, tmpa);
906
  if (table->config->sorted)
907
    rte_announce(table, RA_ACCEPTED, net, new, old, before_old, tmpa);
908

    
909
  if (!net->routes &&
910
      (table->gc_counter++ >= table->config->gc_max_ops) &&
911
      (table->gc_time + table->config->gc_min_time <= now))
912
    rt_schedule_gc(table);
913

    
914
  if (old_ok && p->rte_remove)
915
    p->rte_remove(net, old);
916
  if (new_ok && p->rte_insert)
917
    p->rte_insert(net, new);
918

    
919
  if (old)
920
    rte_free_quick(old);
921
}
922

    
923
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
924

    
925
static inline void
926
rte_update_lock(void)
927
{
928
  rte_update_nest_cnt++;
929
}
930

    
931
static inline void
932
rte_update_unlock(void)
933
{
934
  if (!--rte_update_nest_cnt)
935
    lp_flush(rte_update_pool);
936
}
937

    
938
static inline void
939
rte_hide_dummy_routes(net *net, rte **dummy)
940
{
941
  if (net->routes && net->routes->attrs->source == RTS_DUMMY)
942
  {
943
    *dummy = net->routes;
944
    net->routes = (*dummy)->next;
945
  }
946
}
947

    
948
static inline void
949
rte_unhide_dummy_routes(net *net, rte **dummy)
950
{
951
  if (*dummy)
952
  {
953
    (*dummy)->next = net->routes;
954
    net->routes = *dummy;
955
  }
956
}
957

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

    
1000
void
1001
rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
1002
{
1003
  struct proto *p = ah->proto;
1004
  struct proto_stats *stats = ah->stats;
1005
  struct filter *filter = ah->in_filter;
1006
  ea_list *tmpa = NULL;
1007
  rte *dummy = NULL;
1008

    
1009
  rte_update_lock();
1010
  if (new)
1011
    {
1012
      new->sender = ah;
1013

    
1014
      stats->imp_updates_received++;
1015
      if (!rte_validate(new))
1016
        {
1017
          rte_trace_in(D_FILTERS, p, new, "invalid");
1018
          stats->imp_updates_invalid++;
1019
          goto drop;
1020
        }
1021

    
1022
      if (filter == FILTER_REJECT)
1023
        {
1024
          stats->imp_updates_filtered++;
1025
          rte_trace_in(D_FILTERS, p, new, "filtered out");
1026

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

    
1030
          /* new is a private copy, i could modify it */
1031
          new->flags |= REF_FILTERED;
1032
        }
1033
      else
1034
        {
1035
          tmpa = make_tmp_attrs(new, rte_update_pool);
1036
          if (filter && (filter != FILTER_REJECT))
1037
            {
1038
              ea_list *old_tmpa = tmpa;
1039
              int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
1040
              if (fr > F_ACCEPT)
1041
                {
1042
                  stats->imp_updates_filtered++;
1043
                  rte_trace_in(D_FILTERS, p, new, "filtered out");
1044

    
1045
                  if (! ah->in_keep_filtered)
1046
                    goto drop;
1047

    
1048
                  new->flags |= REF_FILTERED;
1049
                }
1050
              if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
1051
                src->proto->store_tmp_attrs(new, tmpa);
1052
            }
1053
        }
1054
      if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1055
        new->attrs = rta_lookup(new->attrs);
1056
      new->flags |= REF_COW;
1057
    }
1058
  else
1059
    {
1060
      stats->imp_withdraws_received++;
1061

    
1062
      if (!net || !src)
1063
        {
1064
          stats->imp_withdraws_ignored++;
1065
          rte_update_unlock();
1066
          return;
1067
        }
1068
    }
1069

    
1070
 recalc:
1071
  rte_hide_dummy_routes(net, &dummy);
1072
  rte_recalculate(ah, net, new, tmpa, src);
1073
  rte_unhide_dummy_routes(net, &dummy);
1074
  rte_update_unlock();
1075
  return;
1076

    
1077
 drop:
1078
  rte_free(new);
1079
  new = NULL;
1080
  tmpa = NULL;
1081
  goto recalc;
1082
}
1083

    
1084
/* Independent call to rte_announce(), used from next hop
1085
   recalculation, outside of rte_update(). new must be non-NULL */
1086
static inline void 
1087
rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old)
1088
{
1089
  ea_list *tmpa;
1090

    
1091
  rte_update_lock();
1092
  tmpa = make_tmp_attrs(new, rte_update_pool);
1093
  rte_announce(tab, type, n, new, old, NULL, tmpa);
1094
  rte_update_unlock();
1095
}
1096

    
1097
void
1098
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
1099
{
1100
  rte_update_lock();
1101
  rte_recalculate(old->sender, old->net, NULL, NULL, old->attrs->src);
1102
  rte_update_unlock();
1103
}
1104

    
1105
/* Check rtable for best route to given net whether it would be exported do p */
1106
int
1107
rt_examine(rtable *t, ip_addr prefix, int pxlen, struct proto *p, struct filter *filter)
1108
{
1109
  net *n = net_find(t, prefix, pxlen);
1110
  rte *rt = n ? n->routes : NULL;
1111

    
1112
  if (!rte_is_valid(rt))
1113
    return 0;
1114

    
1115
  rte_update_lock();
1116

    
1117
  /* Rest is stripped down export_filter() */
1118
  ea_list *tmpa = make_tmp_attrs(rt, rte_update_pool);
1119
  int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0;
1120
  if (v == RIC_PROCESS)
1121
    v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1122

    
1123
   /* Discard temporary rte */
1124
  if (rt != n->routes)
1125
    rte_free(rt);
1126

    
1127
  rte_update_unlock();
1128

    
1129
  return v > 0;
1130
}
1131

    
1132

    
1133
/**
1134
 * rt_refresh_begin - start a refresh cycle
1135
 * @t: related routing table
1136
 * @ah: related announce hook 
1137
 *
1138
 * This function starts a refresh cycle for given routing table and announce
1139
 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1140
 * routes to the routing table (by rte_update()). After that, all protocol
1141
 * routes (more precisely routes with @ah as @sender) not sent during the
1142
 * refresh cycle but still in the table from the past are pruned. This is
1143
 * implemented by marking all related routes as stale by REF_STALE flag in
1144
 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1145
 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1146
 */
1147
void
1148
rt_refresh_begin(rtable *t, struct announce_hook *ah)
1149
{
1150
  net *n;
1151
  rte *e;
1152

    
1153
  FIB_WALK(&t->fib, fn)
1154
    {
1155
      n = (net *) fn;
1156
      for (e = n->routes; e; e = e->next)
1157
        if (e->sender == ah)
1158
          e->flags |= REF_STALE;
1159
    }
1160
  FIB_WALK_END;
1161
}
1162

    
1163
/**
1164
 * rt_refresh_end - end a refresh cycle
1165
 * @t: related routing table
1166
 * @ah: related announce hook 
1167
 *
1168
 * This function starts a refresh cycle for given routing table and announce
1169
 * hook. See rt_refresh_begin() for description of refresh cycles.
1170
 */
1171
void
1172
rt_refresh_end(rtable *t, struct announce_hook *ah)
1173
{
1174
  int prune = 0;
1175
  net *n;
1176
  rte *e;
1177

    
1178
  FIB_WALK(&t->fib, fn)
1179
    {
1180
      n = (net *) fn;
1181
      for (e = n->routes; e; e = e->next)
1182
        if ((e->sender == ah) && (e->flags & REF_STALE))
1183
          {
1184
            e->flags |= REF_DISCARD;
1185
            prune = 1;
1186
          }
1187
    }
1188
  FIB_WALK_END;
1189

    
1190
  if (prune)
1191
    rt_schedule_prune(t);
1192
}
1193

    
1194

    
1195
/**
1196
 * rte_dump - dump a route
1197
 * @e: &rte to be dumped
1198
 *
1199
 * This functions dumps contents of a &rte to debug output.
1200
 */
1201
void
1202
rte_dump(rte *e)
1203
{
1204
  net *n = e->net;
1205
  debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
1206
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
1207
  rta_dump(e->attrs);
1208
  if (e->attrs->src->proto->proto->dump_attrs)
1209
    e->attrs->src->proto->proto->dump_attrs(e);
1210
  debug("\n");
1211
}
1212

    
1213
/**
1214
 * rt_dump - dump a routing table
1215
 * @t: routing table to be dumped
1216
 *
1217
 * This function dumps contents of a given routing table to debug output.
1218
 */
1219
void
1220
rt_dump(rtable *t)
1221
{
1222
  rte *e;
1223
  net *n;
1224
  struct announce_hook *a;
1225

    
1226
  debug("Dump of routing table <%s>\n", t->name);
1227
#ifdef DEBUGGING
1228
  fib_check(&t->fib);
1229
#endif
1230
  FIB_WALK(&t->fib, fn)
1231
    {
1232
      n = (net *) fn;
1233
      for(e=n->routes; e; e=e->next)
1234
        rte_dump(e);
1235
    }
1236
  FIB_WALK_END;
1237
  WALK_LIST(a, t->hooks)
1238
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
1239
  debug("\n");
1240
}
1241

    
1242
/**
1243
 * rt_dump_all - dump all routing tables
1244
 *
1245
 * This function dumps contents of all routing tables to debug output.
1246
 */
1247
void
1248
rt_dump_all(void)
1249
{
1250
  rtable *t;
1251

    
1252
  WALK_LIST(t, routing_tables)
1253
    rt_dump(t);
1254
}
1255

    
1256
static inline void
1257
rt_schedule_prune(rtable *tab)
1258
{
1259
  rt_mark_for_prune(tab);
1260
  ev_schedule(tab->rt_event);
1261
}
1262

    
1263
static inline void
1264
rt_schedule_gc(rtable *tab)
1265
{
1266
  if (tab->gc_scheduled)
1267
    return;
1268

    
1269
  tab->gc_scheduled = 1;
1270
  ev_schedule(tab->rt_event);
1271
}
1272

    
1273
static inline void
1274
rt_schedule_hcu(rtable *tab)
1275
{
1276
  if (tab->hcu_scheduled)
1277
    return;
1278

    
1279
  tab->hcu_scheduled = 1;
1280
  ev_schedule(tab->rt_event);
1281
}
1282

    
1283
static inline void
1284
rt_schedule_nhu(rtable *tab)
1285
{
1286
  if (tab->nhu_state == 0)
1287
    ev_schedule(tab->rt_event);
1288

    
1289
  /* state change 0->1, 2->3 */
1290
  tab->nhu_state |= 1;
1291
}
1292

    
1293

    
1294
static void
1295
rt_prune_nets(rtable *tab)
1296
{
1297
  struct fib_iterator fit;
1298
  int ncnt = 0, ndel = 0;
1299

    
1300
#ifdef DEBUGGING
1301
  fib_check(&tab->fib);
1302
#endif
1303

    
1304
  FIB_ITERATE_INIT(&fit, &tab->fib);
1305
again:
1306
  FIB_ITERATE_START(&tab->fib, &fit, f)
1307
    {
1308
      net *n = (net *) f;
1309
      ncnt++;
1310
      if (!n->routes)                /* Orphaned FIB entry */
1311
        {
1312
          FIB_ITERATE_PUT(&fit, f);
1313
          fib_delete(&tab->fib, f);
1314
          ndel++;
1315
          goto again;
1316
        }
1317
    }
1318
  FIB_ITERATE_END(f);
1319
  DBG("Pruned %d of %d networks\n", ndel, ncnt);
1320

    
1321
  tab->gc_counter = 0;
1322
  tab->gc_time = now;
1323
  tab->gc_scheduled = 0;
1324
}
1325

    
1326
static void
1327
rt_event(void *ptr)
1328
{
1329
  rtable *tab = ptr;
1330

    
1331
  if (tab->hcu_scheduled)
1332
    rt_update_hostcache(tab);
1333

    
1334
  if (tab->nhu_state)
1335
    rt_next_hop_update(tab);
1336

    
1337
  if (tab->prune_state)
1338
    if (!rt_prune_table(tab))
1339
      {
1340
        /* Table prune unfinished */
1341
        ev_schedule(tab->rt_event);
1342
        return;
1343
      }
1344

    
1345
  if (tab->gc_scheduled)
1346
    {
1347
      rt_prune_nets(tab);
1348
      rt_prune_sources(); // FIXME this should be moved to independent event
1349
    }
1350
}
1351

    
1352
void
1353
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
1354
{
1355
  bzero(t, sizeof(*t));
1356
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
1357
  t->name = name;
1358
  t->config = cf;
1359
  init_list(&t->hooks);
1360
  if (cf)
1361
    {
1362
      t->rt_event = ev_new(p);
1363
      t->rt_event->hook = rt_event;
1364
      t->rt_event->data = t;
1365
      t->gc_time = now;
1366
    }
1367
}
1368

    
1369
/**
1370
 * rt_init - initialize routing tables
1371
 *
1372
 * This function is called during BIRD startup. It initializes the
1373
 * routing table module.
1374
 */
1375
void
1376
rt_init(void)
1377
{
1378
  rta_init();
1379
  rt_table_pool = rp_new(&root_pool, "Routing tables");
1380
  rte_update_pool = lp_new(rt_table_pool, 4080);
1381
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
1382
  init_list(&routing_tables);
1383
}
1384

    
1385

    
1386
static int
1387
rt_prune_step(rtable *tab, int *limit)
1388
{
1389
  struct fib_iterator *fit = &tab->prune_fit;
1390

    
1391
  DBG("Pruning route table %s\n", tab->name);
1392
#ifdef DEBUGGING
1393
  fib_check(&tab->fib);
1394
#endif
1395

    
1396
  if (tab->prune_state == RPS_NONE)
1397
    return 1;
1398

    
1399
  if (tab->prune_state == RPS_SCHEDULED)
1400
    {
1401
      FIB_ITERATE_INIT(fit, &tab->fib);
1402
      tab->prune_state = RPS_RUNNING;
1403
    }
1404

    
1405
again:
1406
  FIB_ITERATE_START(&tab->fib, fit, fn)
1407
    {
1408
      net *n = (net *) fn;
1409
      rte *e;
1410

    
1411
    rescan:
1412
      for (e=n->routes; e; e=e->next)
1413
        if (e->sender->proto->flushing || (e->flags & REF_DISCARD))
1414
          {
1415
            if (*limit <= 0)
1416
              {
1417
                FIB_ITERATE_PUT(fit, fn);
1418
                return 0;
1419
              }
1420

    
1421
            rte_discard(tab, e);
1422
            (*limit)--;
1423

    
1424
            goto rescan;
1425
          }
1426
      if (!n->routes)                /* Orphaned FIB entry */
1427
        {
1428
          FIB_ITERATE_PUT(fit, fn);
1429
          fib_delete(&tab->fib, fn);
1430
          goto again;
1431
        }
1432
    }
1433
  FIB_ITERATE_END(fn);
1434

    
1435
#ifdef DEBUGGING
1436
  fib_check(&tab->fib);
1437
#endif
1438

    
1439
  tab->prune_state = RPS_NONE;
1440
  return 1;
1441
}
1442

    
1443
/**
1444
 * rt_prune_table - prune a routing table
1445
 *
1446
 * This function scans the routing table @tab and removes routes belonging to
1447
 * flushing protocols, discarded routes and also stale network entries, in a
1448
 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1449
 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1450
 * protocol flushing loop, but it is called from rt_event() for just one routing
1451
 * table.
1452
 *
1453
 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1454
 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1455
 */
1456
static inline int
1457
rt_prune_table(rtable *tab)
1458
{
1459
  int limit = 512;
1460
  return rt_prune_step(tab, &limit);
1461
}
1462

    
1463
/**
1464
 * rt_prune_loop - prune routing tables
1465
 *
1466
 * The prune loop scans routing tables and removes routes belonging to flushing
1467
 * protocols, discarded routes and also stale network entries. Returns 1 when
1468
 * all such routes are pruned. It is a part of the protocol flushing loop.
1469
 */
1470
int
1471
rt_prune_loop(void)
1472
{
1473
  int limit = 512;
1474
  rtable *t;
1475

    
1476
  WALK_LIST(t, routing_tables)
1477
    if (! rt_prune_step(t, &limit))
1478
      return 0;
1479

    
1480
  return 1;
1481
}
1482

    
1483
void
1484
rt_preconfig(struct config *c)
1485
{
1486
  struct symbol *s = cf_find_symbol("master");
1487

    
1488
  init_list(&c->tables);
1489
  c->master_rtc = rt_new_table(s);
1490
}
1491

    
1492

    
1493
/* 
1494
 * Some functions for handing internal next hop updates
1495
 * triggered by rt_schedule_nhu().
1496
 */
1497

    
1498
static inline int
1499
rta_next_hop_outdated(rta *a)
1500
{
1501
  struct hostentry *he = a->hostentry;
1502

    
1503
  if (!he)
1504
    return 0;
1505

    
1506
  if (!he->src)
1507
    return a->dest != RTD_UNREACHABLE;
1508

    
1509
  return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) ||
1510
    (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
1511
    !mpnh_same(a->nexthops, he->src->nexthops);
1512
}
1513

    
1514
static inline void
1515
rta_apply_hostentry(rta *a, struct hostentry *he)
1516
{
1517
  a->hostentry = he;
1518
  a->iface = he->src ? he->src->iface : NULL;
1519
  a->gw = he->gw;
1520
  a->dest = he->dest;
1521
  a->igp_metric = he->igp_metric;
1522
  a->nexthops = he->src ? he->src->nexthops : NULL;
1523
}
1524

    
1525
static inline rte *
1526
rt_next_hop_update_rte(rtable *tab, rte *old)
1527
{
1528
  rta a;
1529
  memcpy(&a, old->attrs, sizeof(rta));
1530
  rta_apply_hostentry(&a, old->attrs->hostentry);
1531
  a.aflags = 0;
1532

    
1533
  rte *e = sl_alloc(rte_slab);
1534
  memcpy(e, old, sizeof(rte));
1535
  e->attrs = rta_lookup(&a);
1536

    
1537
  return e;
1538
}
1539

    
1540
static inline int
1541
rt_next_hop_update_net(rtable *tab, net *n)
1542
{
1543
  rte **k, *e, *new, *old_best, **new_best;
1544
  int count = 0;
1545
  int free_old_best = 0;
1546

    
1547
  old_best = n->routes;
1548
  if (!old_best)
1549
    return 0;
1550

    
1551
  for (k = &n->routes; e = *k; k = &e->next)
1552
    if (rta_next_hop_outdated(e->attrs))
1553
      {
1554
        new = rt_next_hop_update_rte(tab, e);
1555
        *k = new;
1556

    
1557
        rte_announce_i(tab, RA_ANY, n, new, e);
1558
        rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
1559

    
1560
        /* Call a pre-comparison hook */
1561
        /* Not really an efficient way to compute this */
1562
        if (e->attrs->src->proto->rte_recalculate)
1563
          e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
1564

    
1565
        if (e != old_best)
1566
          rte_free_quick(e);
1567
        else /* Freeing of the old best rte is postponed */
1568
          free_old_best = 1;
1569

    
1570
        e = new;
1571
        count++;
1572
      }
1573

    
1574
  if (!count)
1575
    return 0;
1576

    
1577
  /* Find the new best route */
1578
  new_best = NULL;
1579
  for (k = &n->routes; e = *k; k = &e->next)
1580
    {
1581
      if (!new_best || rte_better(e, *new_best))
1582
        new_best = k;
1583
    }
1584

    
1585
  /* Relink the new best route to the first position */
1586
  new = *new_best;
1587
  if (new != n->routes)
1588
    {
1589
      *new_best = new->next;
1590
      new->next = n->routes;
1591
      n->routes = new;
1592
    }
1593

    
1594
  /* Announce the new best route */
1595
  if (new != old_best)
1596
    {
1597
      rte_announce_i(tab, RA_OPTIMAL, n, new, old_best);
1598
      rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
1599
    }
1600

    
1601
   if (free_old_best)
1602
    rte_free_quick(old_best);
1603

    
1604
  return count;
1605
}
1606

    
1607
static void
1608
rt_next_hop_update(rtable *tab)
1609
{
1610
  struct fib_iterator *fit = &tab->nhu_fit;
1611
  int max_feed = 32;
1612

    
1613
  if (tab->nhu_state == 0)
1614
    return;
1615

    
1616
  if (tab->nhu_state == 1)
1617
    {
1618
      FIB_ITERATE_INIT(fit, &tab->fib);
1619
      tab->nhu_state = 2;
1620
    }
1621

    
1622
  FIB_ITERATE_START(&tab->fib, fit, fn)
1623
    {
1624
      if (max_feed <= 0)
1625
        {
1626
          FIB_ITERATE_PUT(fit, fn);
1627
          ev_schedule(tab->rt_event);
1628
          return;
1629
        }
1630
      max_feed -= rt_next_hop_update_net(tab, (net *) fn);
1631
    }
1632
  FIB_ITERATE_END(fn);
1633

    
1634
  /* state change 2->0, 3->1 */
1635
  tab->nhu_state &= 1;
1636

    
1637
  if (tab->nhu_state > 0)
1638
    ev_schedule(tab->rt_event);
1639
}
1640

    
1641

    
1642
struct rtable_config *
1643
rt_new_table(struct symbol *s)
1644
{
1645
  /* Hack that allows to 'redefine' the master table */
1646
  if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc))
1647
    return s->def;
1648

    
1649
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
1650

    
1651
  cf_define_symbol(s, SYM_TABLE, c);
1652
  c->name = s->name;
1653
  add_tail(&new_config->tables, &c->n);
1654
  c->gc_max_ops = 1000;
1655
  c->gc_min_time = 5;
1656
  return c;
1657
}
1658

    
1659
/**
1660
 * rt_lock_table - lock a routing table
1661
 * @r: routing table to be locked
1662
 *
1663
 * Lock a routing table, because it's in use by a protocol,
1664
 * preventing it from being freed when it gets undefined in a new
1665
 * configuration.
1666
 */
1667
void
1668
rt_lock_table(rtable *r)
1669
{
1670
  r->use_count++;
1671
}
1672

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

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

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

    
1746
  WALK_LIST(r, new->tables)
1747
    if (!r->table)
1748
      {
1749
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
1750
        DBG("\t%s: created\n", r->name);
1751
        rt_setup(rt_table_pool, t, r->name, r);
1752
        add_tail(&routing_tables, &t->n);
1753
        r->table = t;
1754
      }
1755
  DBG("\tdone\n");
1756
}
1757

    
1758
static inline void
1759
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
1760
{
1761
  ea_list *tmpa;
1762

    
1763
  rte_update_lock();
1764
  tmpa = make_tmp_attrs(e, rte_update_pool);
1765
  if (type == RA_ACCEPTED)
1766
    rt_notify_accepted(h, n, e, NULL, NULL, tmpa, p->refeeding ? 2 : 1);
1767
  else
1768
    rt_notify_basic(h, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding);
1769
  rte_update_unlock();
1770
}
1771

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

    
1788
  if (!p->feed_ahook)                        /* Need to initialize first */
1789
    {
1790
      if (!p->ahooks)
1791
        return 1;
1792
      DBG("Announcing routes to new protocol %s\n", p->name);
1793
      p->feed_ahook = p->ahooks;
1794
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1795
      goto next_hook;
1796
    }
1797
  fit = p->feed_iterator;
1798

    
1799
again:
1800
  h = p->feed_ahook;
1801
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1802
    {
1803
      net *n = (net *) fn;
1804
      rte *e = n->routes;
1805
      if (max_feed <= 0)
1806
        {
1807
          FIB_ITERATE_PUT(fit, fn);
1808
          return 0;
1809
        }
1810

    
1811
      /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1812

    
1813
      if ((p->accept_ra_types == RA_OPTIMAL) ||
1814
          (p->accept_ra_types == RA_ACCEPTED))
1815
        if (rte_is_valid(e))
1816
          {
1817
            if (p->export_state != ES_FEEDING)
1818
              return 1;  /* In the meantime, the protocol fell down. */
1819
            do_feed_baby(p, p->accept_ra_types, h, n, e);
1820
            max_feed--;
1821
          }
1822

    
1823
      if (p->accept_ra_types == RA_ANY)
1824
        for(e = n->routes; rte_is_valid(e); e = e->next)
1825
          {
1826
            if (p->export_state != ES_FEEDING)
1827
              return 1;  /* In the meantime, the protocol fell down. */
1828
            do_feed_baby(p, RA_ANY, h, n, e);
1829
            max_feed--;
1830
          }
1831
    }
1832
  FIB_ITERATE_END(fn);
1833
  p->feed_ahook = h->next;
1834
  if (!p->feed_ahook)
1835
    {
1836
      mb_free(p->feed_iterator);
1837
      p->feed_iterator = NULL;
1838
      return 1;
1839
    }
1840

    
1841
next_hook:
1842
  h = p->feed_ahook;
1843
  FIB_ITERATE_INIT(fit, &h->table->fib);
1844
  goto again;
1845
}
1846

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

    
1866

    
1867
static inline unsigned
1868
ptr_hash(void *ptr)
1869
{
1870
  uintptr_t p = (uintptr_t) ptr;
1871
  return p ^ (p << 8) ^ (p >> 16);
1872
}
1873

    
1874
static inline unsigned
1875
hc_hash(ip_addr a, rtable *dep)
1876
{
1877
  return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff;
1878
}
1879

    
1880
static inline void
1881
hc_insert(struct hostcache *hc, struct hostentry *he)
1882
{
1883
  uint k = he->hash_key >> hc->hash_shift;
1884
  he->next = hc->hash_table[k];
1885
  hc->hash_table[k] = he;
1886
}
1887

    
1888
static inline void
1889
hc_remove(struct hostcache *hc, struct hostentry *he)
1890
{
1891
  struct hostentry **hep;
1892
  uint k = he->hash_key >> hc->hash_shift;
1893

    
1894
  for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
1895
  *hep = he->next;
1896
}
1897

    
1898
#define HC_DEF_ORDER 10
1899
#define HC_HI_MARK *4
1900
#define HC_HI_STEP 2
1901
#define HC_HI_ORDER 16                        /* Must be at most 16 */
1902
#define HC_LO_MARK /5
1903
#define HC_LO_STEP 2
1904
#define HC_LO_ORDER 10
1905

    
1906
static void
1907
hc_alloc_table(struct hostcache *hc, unsigned order)
1908
{
1909
  unsigned hsize = 1 << order;
1910
  hc->hash_order = order;
1911
  hc->hash_shift = 16 - order;
1912
  hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
1913
  hc->hash_min = (order <= HC_LO_ORDER) ?  0 : (hsize HC_LO_MARK);
1914

    
1915
  hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
1916
}
1917

    
1918
static void
1919
hc_resize(struct hostcache *hc, unsigned new_order)
1920
{
1921
  unsigned old_size = 1 << hc->hash_order;
1922
  struct hostentry **old_table = hc->hash_table;
1923
  struct hostentry *he, *hen;
1924
  int i;
1925

    
1926
  hc_alloc_table(hc, new_order);
1927
  for (i = 0; i < old_size; i++)
1928
    for (he = old_table[i]; he != NULL; he=hen)
1929
      {
1930
        hen = he->next;
1931
        hc_insert(hc, he);
1932
      }
1933
  mb_free(old_table);
1934
}
1935

    
1936
static struct hostentry *
1937
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
1938
{
1939
  struct hostentry *he = sl_alloc(hc->slab);
1940

    
1941
  he->addr = a;
1942
  he->link = ll;
1943
  he->tab = dep;
1944
  he->hash_key = k;
1945
  he->uc = 0;
1946
  he->src = NULL;
1947

    
1948
  add_tail(&hc->hostentries, &he->ln);
1949
  hc_insert(hc, he);
1950

    
1951
  hc->hash_items++;
1952
  if (hc->hash_items > hc->hash_max)
1953
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
1954

    
1955
  return he;
1956
}
1957

    
1958
static void
1959
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
1960
{
1961
  rta_free(he->src);
1962

    
1963
  rem_node(&he->ln);
1964
  hc_remove(hc, he);
1965
  sl_free(hc->slab, he);
1966

    
1967
  hc->hash_items--;
1968
  if (hc->hash_items < hc->hash_min)
1969
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
1970
}
1971

    
1972
static void
1973
rt_init_hostcache(rtable *tab)
1974
{
1975
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
1976
  init_list(&hc->hostentries);
1977

    
1978
  hc->hash_items = 0;
1979
  hc_alloc_table(hc, HC_DEF_ORDER);
1980
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
1981

    
1982
  hc->lp = lp_new(rt_table_pool, 1008);
1983
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
1984

    
1985
  tab->hostcache = hc;
1986
}
1987

    
1988
static void
1989
rt_free_hostcache(rtable *tab)
1990
{
1991
  struct hostcache *hc = tab->hostcache;
1992

    
1993
  node *n;
1994
  WALK_LIST(n, hc->hostentries)
1995
    {
1996
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
1997
      rta_free(he->src);
1998

    
1999
      if (he->uc)
2000
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
2001
    }
2002

    
2003
  rfree(hc->slab);
2004
  rfree(hc->lp);
2005
  mb_free(hc->hash_table);
2006
  mb_free(hc);
2007
}
2008

    
2009
static void
2010
rt_notify_hostcache(rtable *tab, net *net)
2011
{
2012
  struct hostcache *hc = tab->hostcache;
2013

    
2014
  if (tab->hcu_scheduled)
2015
    return;
2016

    
2017
  if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
2018
    rt_schedule_hcu(tab);
2019
}
2020

    
2021
static int
2022
if_local_addr(ip_addr a, struct iface *i)
2023
{
2024
  struct ifa *b;
2025

    
2026
  WALK_LIST(b, i->addrs)
2027
    if (ipa_equal(a, b->ip))
2028
      return 1;
2029

    
2030
  return 0;
2031
}
2032

    
2033
static u32 
2034
rt_get_igp_metric(rte *rt)
2035
{
2036
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
2037

    
2038
  if (ea)
2039
    return ea->u.data;
2040

    
2041
  rta *a = rt->attrs;
2042

    
2043
#ifdef CONFIG_OSPF
2044
  if ((a->source == RTS_OSPF) ||
2045
      (a->source == RTS_OSPF_IA) ||
2046
      (a->source == RTS_OSPF_EXT1))
2047
    return rt->u.ospf.metric1;
2048
#endif
2049

    
2050
#ifdef CONFIG_RIP
2051
  if (a->source == RTS_RIP)
2052
    return rt->u.rip.metric;
2053
#endif
2054

    
2055
  /* Device routes */
2056
  if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
2057
    return 0;
2058

    
2059
  return IGP_METRIC_UNKNOWN;
2060
}
2061

    
2062
static int
2063
rt_update_hostentry(rtable *tab, struct hostentry *he)
2064
{
2065
  rta *old_src = he->src;
2066
  int pxlen = 0;
2067

    
2068
  /* Reset the hostentry */ 
2069
  he->src = NULL;
2070
  he->gw = IPA_NONE;
2071
  he->dest = RTD_UNREACHABLE;
2072
  he->igp_metric = 0;
2073

    
2074
  net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
2075
  if (n)
2076
    {
2077
      rte *e = n->routes;
2078
      rta *a = e->attrs;
2079
      pxlen = n->n.pxlen;
2080

    
2081
      if (a->hostentry)
2082
        {
2083
          /* Recursive route should not depend on another recursive route */
2084
          log(L_WARN "Next hop address %I resolvable through recursive route for %I/%d",
2085
              he->addr, n->n.prefix, pxlen);
2086
          goto done;
2087
        }
2088

    
2089
      if (a->dest == RTD_DEVICE)
2090
        {
2091
          if (if_local_addr(he->addr, a->iface))
2092
            {
2093
              /* The host address is a local address, this is not valid */
2094
              log(L_WARN "Next hop address %I is a local address of iface %s",
2095
                  he->addr, a->iface->name);
2096
              goto done;
2097
                  }
2098

    
2099
          /* The host is directly reachable, use link as a gateway */
2100
          he->gw = he->link;
2101
          he->dest = RTD_ROUTER;
2102
        }
2103
      else
2104
        {
2105
          /* The host is reachable through some route entry */
2106
          he->gw = a->gw;
2107
          he->dest = a->dest;
2108
        }
2109

    
2110
      he->src = rta_clone(a);
2111
      he->igp_metric = rt_get_igp_metric(e);
2112
    }
2113

    
2114
 done:
2115
  /* Add a prefix range to the trie */
2116
  trie_add_prefix(tab->hostcache->trie, he->addr, MAX_PREFIX_LENGTH, pxlen, MAX_PREFIX_LENGTH);
2117

    
2118
  rta_free(old_src);
2119
  return old_src != he->src;
2120
}
2121

    
2122
static void
2123
rt_update_hostcache(rtable *tab)
2124
{
2125
  struct hostcache *hc = tab->hostcache;
2126
  struct hostentry *he;
2127
  node *n, *x;
2128

    
2129
  /* Reset the trie */
2130
  lp_flush(hc->lp);
2131
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2132

    
2133
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
2134
    {
2135
      he = SKIP_BACK(struct hostentry, ln, n);
2136
      if (!he->uc)
2137
        {
2138
          hc_delete_hostentry(hc, he);
2139
          continue;
2140
        }
2141

    
2142
      if (rt_update_hostentry(tab, he))
2143
        rt_schedule_nhu(he->tab);
2144
    }
2145

    
2146
  tab->hcu_scheduled = 0;
2147
}
2148

    
2149
static struct hostentry *
2150
rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
2151
{
2152
  struct hostentry *he;
2153

    
2154
  if (!tab->hostcache)
2155
    rt_init_hostcache(tab);
2156

    
2157
  uint k = hc_hash(a, dep);
2158
  struct hostcache *hc = tab->hostcache;
2159
  for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
2160
    if (ipa_equal(he->addr, a) && (he->tab == dep))
2161
      return he;
2162

    
2163
  he = hc_new_hostentry(hc, a, ll, dep, k);
2164
  rt_update_hostentry(tab, he);
2165
  return he;
2166
}
2167

    
2168
void
2169
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll)
2170
{
2171
  rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep));
2172
}
2173

    
2174

    
2175
/*
2176
 *  CLI commands
2177
 */
2178

    
2179
static void
2180
rt_format_via(rte *e, byte *via)
2181
{
2182
  rta *a = e->attrs;
2183

    
2184
  switch (a->dest)
2185
    {
2186
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
2187
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
2188
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
2189
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
2190
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
2191
    case RTD_MULTIPATH:        bsprintf(via, "multipath"); break;
2192
    default:                bsprintf(via, "???");
2193
    }
2194
}
2195

    
2196
static void
2197
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
2198
{
2199
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8];
2200
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
2201
  rta *a = e->attrs;
2202
  int primary = (e->net->routes == e);
2203
  int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
2204
  void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs);
2205
  struct mpnh *nh;
2206

    
2207
  rt_format_via(e, via);
2208
  tm_format_datetime(tm, &config->tf_route, e->lastmod);
2209
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
2210
    bsprintf(from, " from %I", a->from);
2211
  else
2212
    from[0] = 0;
2213

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

    
2236
static void
2237
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
2238
{
2239
  rte *e, *ee;
2240
  byte ia[STD_ADDRESS_P_LENGTH+8];
2241
  struct ea_list *tmpa;
2242
  struct announce_hook *a = NULL;
2243
  int first = 1;
2244
  int pass = 0;
2245

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

    
2248
  if (d->export_mode)
2249
    {
2250
      if (! d->export_protocol->rt_notify)
2251
        return;
2252

    
2253
      a = proto_find_announce_hook(d->export_protocol, d->table);
2254
      if (!a)
2255
        return;
2256
    }
2257

    
2258
  for (e = n->routes; e; e = e->next)
2259
    {
2260
      if (rte_is_filtered(e) != d->filtered)
2261
        continue;
2262

    
2263
      d->rt_counter++;
2264
      d->net_counter += first;
2265
      first = 0;
2266

    
2267
      if (pass)
2268
        continue;
2269

    
2270
      ee = e;
2271
      rte_update_lock();                /* We use the update buffer for filtering */
2272
      tmpa = make_tmp_attrs(e, rte_update_pool);
2273

    
2274
      if (d->export_mode)
2275
        {
2276
          struct proto *ep = d->export_protocol;
2277
          int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0;
2278

    
2279
          if (ep->accept_ra_types == RA_OPTIMAL)
2280
            pass = 1;
2281

    
2282
          if (ic < 0)
2283
            goto skip;
2284

    
2285
          if (d->export_mode > RSEM_PREEXPORT)
2286
            {
2287
              /*
2288
               * FIXME - This shows what should be exported according to current
2289
               * filters, but not what was really exported. 'configure soft'
2290
               * command may change the export filter and do not update routes.
2291
               */
2292
              int do_export = (ic > 0) ||
2293
                (f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
2294

    
2295
              if (do_export != (d->export_mode == RSEM_EXPORT))
2296
                goto skip;
2297

    
2298
              if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED))
2299
                pass = 1;
2300
            }
2301
        }
2302

    
2303
      if (d->show_protocol && (d->show_protocol != e->attrs->src->proto))
2304
        goto skip;
2305

    
2306
      if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
2307
        goto skip;
2308

    
2309
      d->show_counter++;
2310
      if (d->stats < 2)
2311
        rt_show_rte(c, ia, e, d, tmpa);
2312
      ia[0] = 0;
2313

    
2314
    skip:
2315
      if (e != ee)
2316
      {
2317
        rte_free(e);
2318
        e = ee;
2319
      }
2320
      rte_update_unlock();
2321

    
2322
      if (d->primary_only)
2323
        break;
2324
    }
2325
}
2326

    
2327
static void
2328
rt_show_cont(struct cli *c)
2329
{
2330
  struct rt_show_data *d = c->rover;
2331
#ifdef DEBUGGING
2332
  unsigned max = 4;
2333
#else
2334
  unsigned max = 64;
2335
#endif
2336
  struct fib *fib = &d->table->fib;
2337
  struct fib_iterator *it = &d->fit;
2338

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

    
2368
static void
2369
rt_show_cleanup(struct cli *c)
2370
{
2371
  struct rt_show_data *d = c->rover;
2372

    
2373
  /* Unlink the iterator */
2374
  fit_get(&d->table->fib, &d->fit);
2375
}
2376

    
2377
void
2378
rt_show(struct rt_show_data *d)
2379
{
2380
  net *n;
2381

    
2382
  /* Default is either a master table or a table related to a respective protocol */
2383
  if (!d->table && d->export_protocol) d->table = d->export_protocol->table;
2384
  if (!d->table && d->show_protocol) d->table = d->show_protocol->table;
2385
  if (!d->table) d->table = config->master_rtc->table;
2386

    
2387
  /* Filtered routes are neither exported nor have sensible ordering */
2388
  if (d->filtered && (d->export_mode || d->primary_only))
2389
    cli_msg(0, "");
2390

    
2391
  if (d->pxlen == 256)
2392
    {
2393
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
2394
      this_cli->cont = rt_show_cont;
2395
      this_cli->cleanup = rt_show_cleanup;
2396
      this_cli->rover = d;
2397
    }
2398
  else
2399
    {
2400
      if (d->show_for)
2401
        n = net_route(d->table, d->prefix, d->pxlen);
2402
      else
2403
        n = net_find(d->table, d->prefix, d->pxlen);
2404

    
2405
      if (n)
2406
        rt_show_net(this_cli, n, d);
2407

    
2408
      if (d->rt_counter)
2409
        cli_msg(0, "");
2410
      else
2411
        cli_msg(8001, "Network not in table");
2412
    }
2413
}
2414

    
2415
/*
2416
 *  Documentation for functions declared inline in route.h
2417
 */
2418
#if 0
2419

2420
/**
2421
 * net_find - find a network entry
2422
 * @tab: a routing table
2423
 * @addr: address of the network
2424
 * @len: length of the network prefix
2425
 *
2426
 * net_find() looks up the given network in routing table @tab and
2427
 * returns a pointer to its &net entry or %NULL if no such network
2428
 * exists.
2429
 */
2430
static inline net *net_find(rtable *tab, ip_addr addr, unsigned len)
2431
{ DUMMY; }
2432

2433
/**
2434
 * net_get - obtain a network entry
2435
 * @tab: a routing table
2436
 * @addr: address of the network
2437
 * @len: length of the network prefix
2438
 *
2439
 * net_get() looks up the given network in routing table @tab and
2440
 * returns a pointer to its &net entry. If no such entry exists, it's
2441
 * created.
2442
 */
2443
static inline net *net_get(rtable *tab, ip_addr addr, unsigned len)
2444
{ DUMMY; }
2445

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

2466
#endif