Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / nest / rt-table.c @ 6b3f1a54

History | View | Annotate | Download (67.1 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/iface.h"
37
#include "lib/resource.h"
38
#include "lib/event.h"
39
#include "lib/string.h"
40
#include "conf/conf.h"
41
#include "filter/filter.h"
42
#include "lib/string.h"
43
#include "lib/alloca.h"
44

    
45
pool *rt_table_pool;
46

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

    
50
static list routing_tables;
51

    
52
static void rt_free_hostcache(rtable *tab);
53
static void rt_notify_hostcache(rtable *tab, net *net);
54
static void rt_update_hostcache(rtable *tab);
55
static void rt_next_hop_update(rtable *tab);
56
static inline void rt_prune_table(rtable *tab);
57

    
58

    
59
/* Like fib_route(), but skips empty net entries */
60
static inline void *
61
net_route_ip4(rtable *t, net_addr_ip4 *n)
62
{
63
  net *r;
64

    
65
  while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
66
  {
67
    n->pxlen--;
68
    ip4_clrbit(&n->prefix, n->pxlen);
69
  }
70

    
71
  return r;
72
}
73

    
74
static inline void *
75
net_route_ip6(rtable *t, net_addr_ip6 *n)
76
{
77
  net *r;
78

    
79
  while (r = net_find_valid(t, (net_addr *) n), (!r) && (n->pxlen > 0))
80
  {
81
    n->pxlen--;
82
    ip6_clrbit(&n->prefix, n->pxlen);
83
  }
84

    
85
  return r;
86
}
87

    
88
void *
89
net_route(rtable *tab, const net_addr *n)
90
{
91
  ASSERT(tab->addr_type == n->type);
92

    
93
  net_addr *n0 = alloca(n->length);
94
  net_copy(n0, n);
95

    
96
  switch (n->type)
97
  {
98
  case NET_IP4:
99
  case NET_VPN4:
100
  case NET_ROA4:
101
    return net_route_ip4(tab, (net_addr_ip4 *) n0);
102

    
103
  case NET_IP6:
104
  case NET_VPN6:
105
  case NET_ROA6:
106
    return net_route_ip6(tab, (net_addr_ip6 *) n0);
107

    
108
  default:
109
    return NULL;
110
  }
111
}
112

    
113

    
114
static int
115
net_roa_check_ip4(rtable *tab, const net_addr_ip4 *px, u32 asn)
116
{
117
  struct net_addr_roa4 n = NET_ADDR_ROA4(px->prefix, px->pxlen, 0, 0);
118
  struct fib_node *fn;
119
  int anything = 0;
120

    
121
  while (1)
122
  {
123
    for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next)
124
    {
125
      net_addr_roa4 *roa = (void *) fn->addr;
126
      net *r = fib_node_to_user(&tab->fib, fn);
127

    
128
      if (net_equal_prefix_roa4(roa, &n) && rte_is_valid(r->routes))
129
      {
130
        anything = 1;
131
        if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
132
          return ROA_VALID;
133
      }
134
    }
135

    
136
    if (n.pxlen == 0)
137
      break;
138

    
139
    n.pxlen--;
140
    ip4_clrbit(&n.prefix, n.pxlen);
141
  }
142

    
143
  return anything ? ROA_INVALID : ROA_UNKNOWN;
144
}
145

    
146
static int
147
net_roa_check_ip6(rtable *tab, const net_addr_ip6 *px, u32 asn)
148
{
149
  struct net_addr_roa6 n = NET_ADDR_ROA6(px->prefix, px->pxlen, 0, 0);
150
  struct fib_node *fn;
151
  int anything = 0;
152

    
153
  while (1)
154
  {
155
    for (fn = fib_get_chain(&tab->fib, (net_addr *) &n); fn; fn = fn->next)
156
    {
157
      net_addr_roa6 *roa = (void *) fn->addr;
158
      net *r = fib_node_to_user(&tab->fib, fn);
159

    
160
      if (net_equal_prefix_roa6(roa, &n) && rte_is_valid(r->routes))
161
      {
162
        anything = 1;
163
        if (asn && (roa->asn == asn) && (roa->max_pxlen >= px->pxlen))
164
          return ROA_VALID;
165
      }
166
    }
167

    
168
    if (n.pxlen == 0)
169
      break;
170

    
171
    n.pxlen--;
172
    ip6_clrbit(&n.prefix, n.pxlen);
173
  }
174

    
175
  return anything ? ROA_INVALID : ROA_UNKNOWN;
176
}
177

    
178
/**
179
 * roa_check - check validity of route origination in a ROA table
180
 * @tab: ROA table
181
 * @n: network prefix to check
182
 * @asn: AS number of network prefix
183
 *
184
 * Implements RFC 6483 route validation for the given network prefix. The
185
 * procedure is to find all candidate ROAs - ROAs whose prefixes cover the given
186
 * network prefix. If there is no candidate ROA, return ROA_UNKNOWN. If there is
187
 * a candidate ROA with matching ASN and maxlen field greater than or equal to
188
 * the given prefix length, return ROA_VALID. Otherwise, return ROA_INVALID. If
189
 * caller cannot determine origin AS, 0 could be used (in that case ROA_VALID
190
 * cannot happen). Table @tab must have type NET_ROA4 or NET_ROA6, network @n
191
 * must have type NET_IP4 or NET_IP6, respectively.
192
 */
193
int
194
net_roa_check(rtable *tab, const net_addr *n, u32 asn)
195
{
196
  if ((tab->addr_type == NET_ROA4) && (n->type == NET_IP4))
197
    return net_roa_check_ip4(tab, (const net_addr_ip4 *) n, asn);
198
  else if ((tab->addr_type == NET_ROA6) && (n->type == NET_IP6))
199
    return net_roa_check_ip6(tab, (const net_addr_ip6 *) n, asn);
200
  else
201
    return ROA_UNKNOWN;        /* Should not happen */
202
}
203

    
204
/**
205
 * rte_find - find a route
206
 * @net: network node
207
 * @src: route source
208
 *
209
 * The rte_find() function returns a route for destination @net
210
 * which is from route source @src.
211
 */
212
rte *
213
rte_find(net *net, struct rte_src *src)
214
{
215
  rte *e = net->routes;
216

    
217
  while (e && e->attrs->src != src)
218
    e = e->next;
219
  return e;
220
}
221

    
222
/**
223
 * rte_get_temp - get a temporary &rte
224
 * @a: attributes to assign to the new route (a &rta; in case it's
225
 * un-cached, rte_update() will create a cached copy automatically)
226
 *
227
 * Create a temporary &rte and bind it with the attributes @a.
228
 * Also set route preference to the default preference set for
229
 * the protocol.
230
 */
231
rte *
232
rte_get_temp(rta *a)
233
{
234
  rte *e = sl_alloc(rte_slab);
235

    
236
  e->attrs = a;
237
  e->flags = 0;
238
  e->pref = 0;
239
  return e;
240
}
241

    
242
rte *
243
rte_do_cow(rte *r)
244
{
245
  rte *e = sl_alloc(rte_slab);
246

    
247
  memcpy(e, r, sizeof(rte));
248
  e->attrs = rta_clone(r->attrs);
249
  e->flags = 0;
250
  return e;
251
}
252

    
253
/**
254
 * rte_cow_rta - get a private writable copy of &rte with writable &rta
255
 * @r: a route entry to be copied
256
 * @lp: a linpool from which to allocate &rta
257
 *
258
 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
259
 * modification. There are three possibilities: First, both &rte and &rta are
260
 * private copies, in that case they are returned unchanged.  Second, &rte is
261
 * private copy, but &rta is cached, in that case &rta is duplicated using
262
 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
263
 * both structures are duplicated by rte_do_cow() and rta_do_cow().
264
 *
265
 * Note that in the second case, cached &rta loses one reference, while private
266
 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
267
 * nexthops, ...) with it. To work properly, original shared &rta should have
268
 * another reference during the life of created private copy.
269
 *
270
 * Result: a pointer to the new writable &rte with writable &rta.
271
 */
272
rte *
273
rte_cow_rta(rte *r, linpool *lp)
274
{
275
  if (!rta_is_cached(r->attrs))
276
    return r;
277

    
278
  rte *e = rte_cow(r);
279
  rta *a = rta_do_cow(r->attrs, lp);
280
  rta_free(e->attrs);
281
  e->attrs = a;
282
  return e;
283
}
284

    
285
static int                                /* Actually better or at least as good as */
286
rte_better(rte *new, rte *old)
287
{
288
  int (*better)(rte *, rte *);
289

    
290
  if (!rte_is_valid(old))
291
    return 1;
292
  if (!rte_is_valid(new))
293
    return 0;
294

    
295
  if (new->pref > old->pref)
296
    return 1;
297
  if (new->pref < old->pref)
298
    return 0;
299
  if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
300
    {
301
      /*
302
       *  If the user has configured protocol preferences, so that two different protocols
303
       *  have the same preference, try to break the tie by comparing addresses. Not too
304
       *  useful, but keeps the ordering of routes unambiguous.
305
       */
306
      return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
307
    }
308
  if (better = new->attrs->src->proto->rte_better)
309
    return better(new, old);
310
  return 0;
311
}
312

    
313
static int
314
rte_mergable(rte *pri, rte *sec)
315
{
316
  int (*mergable)(rte *, rte *);
317

    
318
  if (!rte_is_valid(pri) || !rte_is_valid(sec))
319
    return 0;
320

    
321
  if (pri->pref != sec->pref)
322
    return 0;
323

    
324
  if (pri->attrs->src->proto->proto != sec->attrs->src->proto->proto)
325
    return 0;
326

    
327
  if (mergable = pri->attrs->src->proto->rte_mergable)
328
    return mergable(pri, sec);
329

    
330
  return 0;
331
}
332

    
333
static void
334
rte_trace(struct proto *p, rte *e, int dir, char *msg)
335
{
336
  log(L_TRACE "%s %c %s %N %s", p->name, dir, msg, e->net->n.addr, rta_dest_name(e->attrs->dest));
337
}
338

    
339
static inline void
340
rte_trace_in(uint flag, struct proto *p, rte *e, char *msg)
341
{
342
  if (p->debug & flag)
343
    rte_trace(p, e, '>', msg);
344
}
345

    
346
static inline void
347
rte_trace_out(uint flag, struct proto *p, rte *e, char *msg)
348
{
349
  if (p->debug & flag)
350
    rte_trace(p, e, '<', msg);
351
}
352

    
353
static rte *
354
export_filter_(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
355
{
356
  struct proto *p = c->proto;
357
  struct filter *filter = c->out_filter;
358
  struct proto_stats *stats = &c->stats;
359
  ea_list *tmpb = NULL;
360
  rte *rt;
361
  int v;
362

    
363
  rt = rt0;
364
  *rt_free = NULL;
365

    
366
  if (!tmpa)
367
    tmpa = &tmpb;
368

    
369
  *tmpa = rte_make_tmp_attrs(rt, pool);
370

    
371
  v = p->import_control ? p->import_control(p, &rt, tmpa, pool) : 0;
372
  if (v < 0)
373
    {
374
      if (silent)
375
        goto reject;
376

    
377
      stats->exp_updates_rejected++;
378
      if (v == RIC_REJECT)
379
        rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
380
      goto reject;
381
    }
382
  if (v > 0)
383
    {
384
      if (!silent)
385
        rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
386
      goto accept;
387
    }
388

    
389
  v = filter && ((filter == FILTER_REJECT) ||
390
                 (f_run(filter, &rt, tmpa, pool, FF_FORCE_TMPATTR) > F_ACCEPT));
391
  if (v)
392
    {
393
      if (silent)
394
        goto reject;
395

    
396
      stats->exp_updates_filtered++;
397
      rte_trace_out(D_FILTERS, p, rt, "filtered out");
398
      goto reject;
399
    }
400

    
401
 accept:
402
  if (rt != rt0)
403
    *rt_free = rt;
404
  return rt;
405

    
406
 reject:
407
  /* Discard temporary rte */
408
  if (rt != rt0)
409
    rte_free(rt);
410
  return NULL;
411
}
412

    
413
static inline rte *
414
export_filter(struct channel *c, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
415
{
416
  return export_filter_(c, rt0, rt_free, tmpa, rte_update_pool, silent);
417
}
418

    
419
static void
420
do_rt_notify(struct channel *c, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
421
{
422
    //log(L_INFO "SONO IN DO_RT_NOTIFY");
423
  struct proto *p = c->proto;
424
  struct proto_stats *stats = &c->stats;
425

    
426

    
427
  /*
428
   * First, apply export limit.
429
   *
430
   * Export route limits has several problems. Because exp_routes
431
   * counter is reset before refeed, we don't really know whether
432
   * limit is breached and whether the update is new or not. Therefore
433
   * the number of really exported routes may exceed the limit
434
   * temporarily (routes exported before and new routes in refeed).
435
   *
436
   * Minor advantage is that if the limit is decreased and refeed is
437
   * requested, the number of exported routes really decrease.
438
   *
439
   * Second problem is that with export limits, we don't know whether
440
   * old was really exported (it might be blocked by limit). When a
441
   * withdraw is exported, we announce it even when the previous
442
   * update was blocked. This is not a big issue, but the same problem
443
   * is in updating exp_routes counter. Therefore, to be consistent in
444
   * increases and decreases of exp_routes, we count exported routes
445
   * regardless of blocking by limits.
446
   *
447
   * Similar problem is in handling updates - when a new route is
448
   * received and blocking is active, the route would be blocked, but
449
   * when an update for the route will be received later, the update
450
   * would be propagated (as old != NULL). Therefore, we have to block
451
   * also non-new updates (contrary to import blocking).
452
   */
453

    
454
  struct channel_limit *l = &c->out_limit;
455
  if (l->action && new)
456
    {
457
      if ((!old || refeed) && (stats->exp_routes >= l->limit))
458
        channel_notify_limit(c, l, PLD_OUT, stats->exp_routes);
459

    
460
      if (l->state == PLS_BLOCKED)
461
        {
462
          stats->exp_routes++;        /* see note above */
463
          stats->exp_updates_rejected++;
464
          rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
465
          new = NULL;
466

    
467
          if (!old)
468
            return;
469
        }
470
    }
471

    
472

    
473
  if (new)
474
    stats->exp_updates_accepted++;
475
  else
476
    stats->exp_withdraws_accepted++;
477

    
478
  /* Hack: We do not decrease exp_routes during refeed, we instead
479
     reset exp_routes at the start of refeed. */
480
  if (new)
481
    stats->exp_routes++;
482
  if (old && !refeed)
483
    stats->exp_routes--;
484

    
485
  if (p->debug & D_ROUTES)
486
    {
487
    //TODO modificati i commenti alle seguenti righe
488
      if (new && old)
489
        rte_trace_out(D_ROUTES, p, new, "replaced yeah");
490
      else if (new)
491
        rte_trace_out(D_ROUTES, p, new, "added yess");
492
      else if (old)
493
        rte_trace_out(D_ROUTES, p, old, "removed");
494
    }
495
  if (!new)
496
    p->rt_notify(p, c, net, NULL, old, NULL);
497
  else if (tmpa)
498
    {
499
      ea_list *t = tmpa;
500
      while (t->next)
501
        t = t->next;
502
      t->next = new->attrs->eattrs;
503
      p->rt_notify(p, c, net, new, old, tmpa);
504
      t->next = NULL;
505
    }
506
  else
507
    p->rt_notify(p, c, net, new, old, new->attrs->eattrs);
508
}
509

    
510
static void
511
rt_notify_basic(struct channel *c, net *net, rte *new0, rte *old0, int refeed)
512
{
513
  //log(L_INFO "HEI SONO IN RT_NOTIFY BASIC");
514
  struct proto *p = c->proto;
515

    
516
  rte *new = new0;
517
  rte *old = old0;
518
  rte *new_free = NULL;
519
  rte *old_free = NULL;
520
  ea_list *tmpa = NULL;
521

    
522
  if (new)
523
    c->stats.exp_updates_received++;
524
  else
525
    c->stats.exp_withdraws_received++;
526

    
527
  /*
528
   * This is a tricky part - we don't know whether route 'old' was
529
   * exported to protocol 'p' or was filtered by the export filter.
530
   * We try to run the export filter to know this to have a correct
531
   * value in 'old' argument of rte_update (and proper filter value)
532
   *
533
   * FIXME - this is broken because 'configure soft' may change
534
   * filters but keep routes. Refeed is expected to be called after
535
   * change of the filters and with old == new, therefore we do not
536
   * even try to run the filter on an old route, This may lead to
537
   * 'spurious withdraws' but ensure that there are no 'missing
538
   * withdraws'.
539
   *
540
   * This is not completely safe as there is a window between
541
   * reconfiguration and the end of refeed - if a newly filtered
542
   * route disappears during this period, proper withdraw is not
543
   * sent (because old would be also filtered) and the route is
544
   * not refeeded (because it disappeared before that).
545
   */
546

    
547
  if (new)
548
    new = export_filter(c, new, &new_free, &tmpa, 0);
549

    
550
  if (old && !refeed)
551
    old = export_filter(c, old, &old_free, NULL, 1);
552

    
553
  if (!new && !old)
554
  {
555
    /*
556
     * As mentioned above, 'old' value may be incorrect in some race conditions.
557
     * We generally ignore it with the exception of withdraw to pipe protocol.
558
     * In that case we rather propagate unfiltered withdraws regardless of
559
     * export filters to ensure that when a protocol is flushed, its routes are
560
     * removed from all tables. Possible spurious unfiltered withdraws are not
561
     * problem here as they are ignored if there is no corresponding route at
562
     * the other end of the pipe. We directly call rt_notify() hook instead of
563
     * do_rt_notify() to avoid logging and stat counters.
564
     */
565

    
566
#ifdef CONFIG_PIPE
567
    if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto))
568
      p->rt_notify(p, c, net, NULL, old0, NULL);
569
#endif
570

    
571
    return;
572
  }
573

    
574
  do_rt_notify(c, net, new, old, tmpa, refeed);
575

    
576
  /* Discard temporary rte's */
577
  if (new_free)
578
    rte_free(new_free);
579
  if (old_free)
580
    rte_free(old_free);
581
}
582

    
583
static void
584
rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_changed, rte *before_old, int feed)
585
{
586
  // struct proto *p = c->proto;
587

    
588
  rte *r;
589
  rte *new_best = NULL;
590
  rte *old_best = NULL;
591
  rte *new_free = NULL;
592
  rte *old_free = NULL;
593
  ea_list *tmpa = NULL;
594

    
595
  /* Used to track whether we met old_changed position. If before_old is NULL
596
     old_changed was the first and we met it implicitly before current best route. */
597
  int old_meet = old_changed && !before_old;
598

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

    
603
  if (new_changed)
604
    c->stats.exp_updates_received++;
605
  else
606
    c->stats.exp_withdraws_received++;
607

    
608
  /* First, find the new_best route - first accepted by filters */
609
  for (r=net->routes; rte_is_valid(r); r=r->next)
610
    {
611
      if (new_best = export_filter(c, r, &new_free, &tmpa, 0))
612
        break;
613

    
614
      /* Note if we walked around the position of old_changed route */
615
      if (r == before_old)
616
        old_meet = 1;
617
    }
618

    
619
  /*
620
   * Second, handle the feed case. That means we do not care for
621
   * old_best. It is NULL for feed, and the new_best for refeed.
622
   * For refeed, there is a hack similar to one in rt_notify_basic()
623
   * to ensure withdraws in case of changed filters
624
   */
625
  if (feed)
626
    {
627
      if (feed == 2)        /* refeed */
628
        old_best = new_best ? new_best :
629
          (rte_is_valid(net->routes) ? net->routes : NULL);
630
      else
631
        old_best = NULL;
632

    
633
      if (!new_best && !old_best)
634
        return;
635

    
636
      goto found;
637
    }
638

    
639
  /*
640
   * Now, we find the old_best route. Generally, it is the same as the
641
   * new_best, unless new_best is the same as new_changed or
642
   * old_changed is accepted before new_best.
643
   *
644
   * There are four cases:
645
   *
646
   * - We would find and accept old_changed before new_best, therefore
647
   *   old_changed is old_best. In remaining cases we suppose this
648
   *   is not true.
649
   *
650
   * - We found no new_best, therefore there is also no old_best and
651
   *   we ignore this withdraw.
652
   *
653
   * - We found new_best different than new_changed, therefore
654
   *   old_best is the same as new_best and we ignore this update.
655
   *
656
   * - We found new_best the same as new_changed, therefore it cannot
657
   *   be old_best and we have to continue search for old_best.
658
   */
659

    
660
  /* First case */
661
  if (old_meet)
662
    if (old_best = export_filter(c, old_changed, &old_free, NULL, 1))
663
      goto found;
664

    
665
  /* Second case */
666
  if (!new_best)
667
    return;
668

    
669
  /* Third case, we use r instead of new_best, because export_filter() could change it */
670
  if (r != new_changed)
671
    {
672
      if (new_free)
673
        rte_free(new_free);
674
      return;
675
    }
676

    
677
  /* Fourth case */
678
  for (r=r->next; rte_is_valid(r); r=r->next)
679
    {
680
      if (old_best = export_filter(c, r, &old_free, NULL, 1))
681
        goto found;
682

    
683
      if (r == before_old)
684
        if (old_best = export_filter(c, old_changed, &old_free, NULL, 1))
685
          goto found;
686
    }
687

    
688
  /* Implicitly, old_best is NULL and new_best is non-NULL */
689

    
690
 found:
691
  do_rt_notify(c, net, new_best, old_best, tmpa, (feed == 2));
692

    
693
  /* Discard temporary rte's */
694
  if (new_free)
695
    rte_free(new_free);
696
  if (old_free)
697
    rte_free(old_free);
698
}
699

    
700

    
701
static struct nexthop *
702
nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max)
703
{
704
  return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool);
705
}
706

    
707
rte *
708
rt_export_merged(struct channel *c, net *net, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
709
{
710
  // struct proto *p = c->proto;
711
  struct nexthop *nhs = NULL;
712
  rte *best0, *best, *rt0, *rt, *tmp;
713

    
714
  best0 = net->routes;
715
  *rt_free = NULL;
716

    
717
  if (!rte_is_valid(best0))
718
    return NULL;
719

    
720
  best = export_filter_(c, best0, rt_free, tmpa, pool, silent);
721

    
722
  if (!best || !rte_is_reachable(best))
723
    return best;
724

    
725
  for (rt0 = best0->next; rt0; rt0 = rt0->next)
726
  {
727
    if (!rte_mergable(best0, rt0))
728
      continue;
729

    
730
    rt = export_filter_(c, rt0, &tmp, NULL, pool, 1);
731

    
732
    if (!rt)
733
      continue;
734

    
735
    if (rte_is_reachable(rt))
736
      nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit);
737

    
738
    if (tmp)
739
      rte_free(tmp);
740
  }
741

    
742
  if (nhs)
743
  {
744
    nhs = nexthop_merge_rta(nhs, best->attrs, pool, c->merge_limit);
745

    
746
    if (nhs->next)
747
    {
748
      best = rte_cow_rta(best, pool);
749
      nexthop_link(best->attrs, nhs);
750
    }
751
  }
752

    
753
  if (best != best0)
754
    *rt_free = best;
755

    
756
  return best;
757
}
758

    
759

    
760
static void
761
rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed,
762
                 rte *new_best, rte*old_best, int refeed)
763
{
764
  // struct proto *p = c->proto;
765

    
766
  rte *new_best_free = NULL;
767
  rte *old_best_free = NULL;
768
  rte *new_changed_free = NULL;
769
  rte *old_changed_free = NULL;
770
  ea_list *tmpa = NULL;
771

    
772
  /* We assume that all rte arguments are either NULL or rte_is_valid() */
773

    
774
  /* This check should be done by the caller */
775
  if (!new_best && !old_best)
776
    return;
777

    
778
  /* Check whether the change is relevant to the merged route */
779
  if ((new_best == old_best) && !refeed)
780
  {
781
    new_changed = rte_mergable(new_best, new_changed) ?
782
      export_filter(c, new_changed, &new_changed_free, NULL, 1) : NULL;
783

    
784
    old_changed = rte_mergable(old_best, old_changed) ?
785
      export_filter(c, old_changed, &old_changed_free, NULL, 1) : NULL;
786

    
787
    if (!new_changed && !old_changed)
788
      return;
789
  }
790

    
791
  if (new_best)
792
    c->stats.exp_updates_received++;
793
  else
794
    c->stats.exp_withdraws_received++;
795

    
796
  /* Prepare new merged route */
797
  if (new_best)
798
    new_best = rt_export_merged(c, net, &new_best_free, &tmpa, rte_update_pool, 0);
799

    
800
  /* Prepare old merged route (without proper merged next hops) */
801
  /* There are some issues with running filter on old route - see rt_notify_basic() */
802
  if (old_best && !refeed)
803
    old_best = export_filter(c, old_best, &old_best_free, NULL, 1);
804

    
805
  if (new_best || old_best)
806
    do_rt_notify(c, net, new_best, old_best, tmpa, refeed);
807

    
808
  /* Discard temporary rte's */
809
  if (new_best_free)
810
    rte_free(new_best_free);
811
  if (old_best_free)
812
    rte_free(old_best_free);
813
  if (new_changed_free)
814
    rte_free(new_changed_free);
815
  if (old_changed_free)
816
    rte_free(old_changed_free);
817
}
818

    
819

    
820
/**
821
 * rte_announce - announce a routing table change
822
 * @tab: table the route has been added to
823
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
824
 * @net: network in question
825
 * @new: the new route to be announced
826
 * @old: the previous route for the same network
827
 * @new_best: the new best route for the same network
828
 * @old_best: the previous best route for the same network
829
 * @before_old: The previous route before @old for the same network.
830
 *                 If @before_old is NULL @old was the first.
831
 *
832
 * This function gets a routing table update and announces it
833
 * to all protocols that acccepts given type of route announcement
834
 * and are connected to the same table by their announcement hooks.
835
 *
836
 * Route announcement of type %RA_OPTIMAL si generated when optimal
837
 * route (in routing table @tab) changes. In that case @old stores the
838
 * old optimal route.
839
 *
840
 * Route announcement of type %RA_ANY si generated when any route (in
841
 * routing table @tab) changes In that case @old stores the old route
842
 * from the same protocol.
843
 *
844
 * For each appropriate protocol, we first call its import_control()
845
 * hook which performs basic checks on the route (each protocol has a
846
 * right to veto or force accept of the route before any filter is
847
 * asked) and adds default values of attributes specific to the new
848
 * protocol (metrics, tags etc.).  Then it consults the protocol's
849
 * export filter and if it accepts the route, the rt_notify() hook of
850
 * the protocol gets called.
851
 */
852
static void
853
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old,
854
             rte *new_best, rte *old_best, rte *before_old)
855
{
856
  //log(L_INFO "HEI SONO IN RTE_ANNOUNCE");
857
  if (!rte_is_valid(new)){
858
    //log(L_INFO "rotta new non valida");
859
    new = NULL;
860
  }
861

    
862
  if (!rte_is_valid(old)){
863
    //log(L_INFO "rotta old non valida");
864
    old = before_old = NULL;
865
  }
866

    
867
  if (!rte_is_valid(new_best)){
868
    //log(L_INFO "rotta new_best non valida");
869
    new_best = NULL;
870
  }
871

    
872
  if (!rte_is_valid(old_best)){
873
    //log(L_INFO "rotta old_best non valida");
874
    old_best = NULL;
875
  }
876

    
877
  if (!old && !new)
878
    return;
879

    
880
  if ((type == RA_OPTIMAL) && tab->hostcache)
881
    rt_notify_hostcache(tab, net);
882

    
883
  struct channel *c; node *n;
884
  WALK_LIST2(c, n, tab->channels, table_node)
885
    {
886
      if (c->export_state == ES_DOWN)
887
        continue;
888

    
889
      if (c->ra_mode == type)
890
        if (type == RA_ACCEPTED)
891
          rt_notify_accepted(c, net, new, old, before_old, 0);
892
        else if (type == RA_MERGED)
893
          rt_notify_merged(c, net, new, old, new_best, old_best, 0);
894
        else
895
          rt_notify_basic(c, net, new, old, 0);
896
    }
897
}
898

    
899
void
900
rte_announce_mine(rtable *tab, unsigned type, net *net, rte *new, rte *old,
901
        rte *new_best, rte *old_best, rte *before_old)
902
{
903
  //log(L_INFO "HEI SONO IN RTE_ANNOUNCE");
904
  if (!rte_is_valid(new))
905
    new = NULL;
906

    
907
  if (!rte_is_valid(old))
908
    old = before_old = NULL;
909

    
910
  if (!rte_is_valid(new_best))
911
    new_best = NULL;
912

    
913
  if (!rte_is_valid(old_best))
914
    old_best = NULL;
915

    
916
  if (!old && !new){
917
      //log(L_INFO "HO paura di uscire qui :scared:");
918
      return;
919
  }
920

    
921
  if ((type == RA_OPTIMAL) && tab->hostcache)
922
    rt_notify_hostcache(tab, net);
923

    
924
  struct channel *c; node *n;
925
  WALK_LIST2(c, n, tab->channels, table_node)
926
  {
927
    if (c->export_state == ES_DOWN)
928
      continue;
929

    
930
    if (c->ra_mode == type)
931
      if (type == RA_ACCEPTED)
932
        rt_notify_accepted(c, net, new, old, before_old, 0);
933
      else if (type == RA_MERGED)
934
        rt_notify_merged(c, net, new, old, new_best, old_best, 0);
935
      else
936
        rt_notify_basic(c, net, new, old, 0);
937
  }
938
}
939

    
940
static inline int
941
rte_validate(rte *e)
942
{
943
  int c;
944
  net *n = e->net;
945

    
946
  if (!net_validate(n->n.addr))
947
  {
948
    log(L_WARN "Ignoring bogus prefix %N received via %s",
949
        n->n.addr, e->sender->proto->name);
950
    return 0;
951
  }
952

    
953
  /* FIXME: better handling different nettypes */
954
  c = !net_is_flow(n->n.addr) ?
955
    net_classify(n->n.addr): (IADDR_HOST | SCOPE_UNIVERSE);
956
  if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
957
  {
958
    log(L_WARN "Ignoring bogus route %N received via %s",
959
        n->n.addr, e->sender->proto->name);
960
    return 0;
961
  }
962

    
963
  if (net_type_match(n->n.addr, NB_DEST) == !e->attrs->dest)
964
  {
965
    log(L_WARN "Ignoring route %N with invalid dest %d received via %s",
966
        n->n.addr, e->attrs->dest, e->sender->proto->name);
967
    return 0;
968
  }
969

    
970
  if ((e->attrs->dest == RTD_UNICAST) && !nexthop_is_sorted(&(e->attrs->nh)))
971
  {
972
    log(L_WARN "Ignoring unsorted multipath route %N received via %s",
973
        n->n.addr, e->sender->proto->name);
974
    return 0;
975
  }
976

    
977
  return 1;
978
}
979

    
980
/**
981
 * rte_free - delete a &rte
982
 * @e: &rte to be deleted
983
 *
984
 * rte_free() deletes the given &rte from the routing table it's linked to.
985
 */
986
void
987
rte_free(rte *e)
988
{
989
  if (rta_is_cached(e->attrs))
990
    rta_free(e->attrs);
991
  sl_free(rte_slab, e);
992
}
993

    
994
static inline void
995
rte_free_quick(rte *e)
996
{
997
  rta_free(e->attrs);
998
  sl_free(rte_slab, e);
999
}
1000

    
1001
static int
1002
rte_same(rte *x, rte *y)
1003
{
1004
  return
1005
    x->attrs == y->attrs &&
1006
    x->flags == y->flags &&
1007
    x->pflags == y->pflags &&
1008
    x->pref == y->pref &&
1009
    (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y));
1010
}
1011

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

    
1014
static void
1015
rte_recalculate(struct channel *c, net *net, rte *new, struct rte_src *src)
1016
{
1017
  //log(L_INFO "RTE_RECALCULATE - 1");
1018
  struct proto *p = c->proto;
1019
  struct rtable *table = c->table;
1020
  struct proto_stats *stats = &c->stats;
1021
  static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
1022
  rte *before_old = NULL;
1023
  rte *old_best = net->routes;
1024
  rte *old = NULL;
1025
  rte **k;
1026

    
1027
  k = &net->routes;                        /* Find and remove original route from the same protocol */
1028
  while (old = *k)
1029
    {
1030
      if (old->attrs->src == src)
1031
        {
1032
          /* If there is the same route in the routing table but from
1033
           * a different sender, then there are two paths from the
1034
           * source protocol to this routing table through transparent
1035
           * pipes, which is not allowed.
1036
           *
1037
           * We log that and ignore the route. If it is withdraw, we
1038
           * ignore it completely (there might be 'spurious withdraws',
1039
           * see FIXME in do_rte_announce())
1040
           */
1041
          if (old->sender->proto != p)
1042
            {
1043
              if (new)
1044
                {
1045
                  log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %N to table %s",
1046
                      net->n.addr, table->name);
1047
                  rte_free_quick(new);
1048
                }
1049
//log(L_INFO "RTE_RECALCULATE - 2");
1050
              return;
1051
            }
1052

    
1053
          if (new && rte_same(old, new))
1054
            {
1055
              /* No changes, ignore the new route */
1056

    
1057
              if (!rte_is_filtered(new))
1058
                {
1059
                  stats->imp_updates_ignored++;
1060
                  rte_trace_in(D_ROUTES, p, new, "ignored");
1061
          //log(L_INFO "Rotta ignorata, quindi non viene fatta la rivalutazione di old e new");
1062
                }
1063

    
1064
              rte_free_quick(new);
1065
              return;
1066
            }
1067
          *k = old->next;
1068
          break;
1069
        }
1070
      k = &old->next;
1071
      before_old = old;
1072
    }
1073
//log(L_INFO "RTE_RECALCULATE - 3");
1074
  if (!old)
1075
    before_old = NULL;
1076

    
1077
  if (!old && !new)
1078
    {
1079
//log(L_INFO "RTE_RECALCULATE - 4");
1080
      stats->imp_withdraws_ignored++;
1081
      return;
1082
    }
1083

    
1084
  int new_ok = rte_is_ok(new);
1085
  int old_ok = rte_is_ok(old);
1086

    
1087
  struct channel_limit *l = &c->rx_limit;
1088
  if (l->action && !old && new)
1089
    {
1090
      u32 all_routes = stats->imp_routes + stats->filt_routes;
1091

    
1092
      if (all_routes >= l->limit)
1093
        channel_notify_limit(c, l, PLD_RX, all_routes);
1094

    
1095
      if (l->state == PLS_BLOCKED)
1096
        {
1097
          /* In receive limit the situation is simple, old is NULL so
1098
             we just free new and exit like nothing happened */
1099

    
1100
          stats->imp_updates_ignored++;
1101
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
1102
          rte_free_quick(new);
1103
          return;
1104
        }
1105
    }
1106
//log(L_INFO "RTE_RECALCULATE - 5");
1107
  l = &c->in_limit;
1108
  if (l->action && !old_ok && new_ok)
1109
    {
1110
      if (stats->imp_routes >= l->limit)
1111
        channel_notify_limit(c, l, PLD_IN, stats->imp_routes);
1112

    
1113
      if (l->state == PLS_BLOCKED)
1114
        {
1115
          /* In import limit the situation is more complicated. We
1116
             shouldn't just drop the route, we should handle it like
1117
             it was filtered. We also have to continue the route
1118
             processing if old or new is non-NULL, but we should exit
1119
             if both are NULL as this case is probably assumed to be
1120
             already handled. */
1121

    
1122
          stats->imp_updates_ignored++;
1123
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
1124

    
1125
          if (c->in_keep_filtered)
1126
            new->flags |= REF_FILTERED;
1127
          else
1128
            { rte_free_quick(new); new = NULL; }
1129

    
1130
          /* Note that old && !new could be possible when
1131
             c->in_keep_filtered changed in the recent past. */
1132

    
1133
          if (!old && !new)
1134
            return;
1135

    
1136
          new_ok = 0;
1137
          goto skip_stats1;
1138
        }
1139
    }
1140
//log(L_INFO "RTE_RECALCULATE - 6");
1141
  if (new_ok)
1142
    stats->imp_updates_accepted++;
1143
  else if (old_ok)
1144
    stats->imp_withdraws_accepted++;
1145
  else
1146
    stats->imp_withdraws_ignored++;
1147

    
1148
 skip_stats1:
1149
//log(L_INFO "RTE_RECALCULATE - 7");
1150
  if (new)
1151
    rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
1152
  if (old)
1153
    rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
1154

    
1155
  if (table->config->sorted)
1156
    {
1157
      /* If routes are sorted, just insert new route to appropriate position */
1158
      if (new)
1159
        {
1160
          if (before_old && !rte_better(new, before_old))
1161
            k = &before_old->next;
1162
          else
1163
            k = &net->routes;
1164

    
1165
          for (; *k; k=&(*k)->next)
1166
            if (rte_better(new, *k))
1167
              break;
1168

    
1169
          new->next = *k;
1170
          *k = new;
1171
        }
1172
    }
1173
  else
1174
    {
1175
      /* If routes are not sorted, find the best route and move it on
1176
         the first position. There are several optimized cases. */
1177

    
1178
      if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
1179
        goto do_recalculate;
1180

    
1181
      if (new && rte_better(new, old_best))
1182
        {
1183
          /* The first case - the new route is cleary optimal,
1184
             we link it at the first position */
1185

    
1186
          new->next = net->routes;
1187
          net->routes = new;
1188
        }
1189
      else if (old == old_best)
1190
        {
1191
          /* The second case - the old best route disappeared, we add the
1192
             new route (if we have any) to the list (we don't care about
1193
             position) and then we elect the new optimal route and relink
1194
             that route at the first position and announce it. New optimal
1195
             route might be NULL if there is no more routes */
1196

    
1197
        do_recalculate:
1198
          //log(L_INFO "RTE_RECALCULATE - 8");
1199
          /* Add the new route to the list */
1200
          if (new)
1201
            {
1202
//log(L_INFO "RTE_RECALCULATE - 8.1");
1203
              new->next = net->routes;
1204
              net->routes = new;
1205
            } else {
1206
//log(L_INFO "RTE_RECALCULATE - 8.2");
1207
            return;
1208
          }
1209

    
1210
          /* Find a new optimal route (if there is any) */
1211
          if (net->routes)
1212
            {
1213
//log(L_INFO "RTE_RECALCULATE - 8.3");
1214
              rte **bp = &net->routes;
1215
              for (k=&(*bp)->next; *k; k=&(*k)->next)
1216
                if (rte_better(*k, *bp))
1217
                  bp = k;
1218

    
1219
              /* And relink it */
1220
              rte *best = *bp;
1221
              *bp = best->next;
1222
              best->next = net->routes;
1223
              net->routes = best;
1224
            }
1225
        }
1226
      else if (new)
1227
        {
1228
          /* The third case - the new route is not better than the old
1229
best route (therefore old_best != NULL) and the old best
1230
        route was not removed (therefore old_best == net->routes).
1231
We just link the new route after the old best route. */
1232

    
1233
          ASSERT(net->routes != NULL);
1234
          new->next = net->routes->next;
1235
          net->routes->next = new;
1236
        }
1237
      /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1238
    }
1239
//log(L_INFO "RTE_RECALCULATE - 9");
1240
  if (new)
1241
    new->lastmod = current_time();
1242

    
1243
  /* Log the route change */
1244
  if (p->debug & D_ROUTES)
1245
    {
1246
      if (new_ok){
1247
          if(new == net->routes){
1248
                     rte_trace(p, new, '>',  "added [best]");
1249
                 //log(L_INFO "Questo sarà il NH da aggiungere alla lista dei NH");
1250
             }
1251
          else{
1252
              rte_trace(p, new, '>',  "added");
1253
              //log(L_INFO "Lo aggiunto lo stesso alla lista dei NH? :thinking:");
1254
          }
1255
    }
1256
      else if (old_ok)
1257
        {
1258
          if (old != old_best)
1259
            rte_trace(p, old, '>', "removed");
1260
          else if (rte_is_ok(net->routes))
1261
            rte_trace(p, old, '>', "removed [replaced]");
1262
          else
1263
            rte_trace(p, old, '>', "removed [sole]");
1264
        }
1265
    }
1266
  //log(L_INFO "RTE_RECALCULATE - 10");
1267
  /* Propagate the route change */
1268
  rte_announce(table, RA_ANY, net, new, old, NULL, NULL, NULL);
1269
  if (net->routes != old_best)
1270
    rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, NULL, NULL);
1271
  if (table->config->sorted)
1272
    rte_announce(table, RA_ACCEPTED, net, new, old, NULL, NULL, before_old);
1273
  rte_announce(table, RA_MERGED, net, new, old, net->routes, old_best, NULL);
1274

    
1275
  if (!net->routes &&
1276
      (table->gc_counter++ >= table->config->gc_max_ops) &&
1277
      (table->gc_time + table->config->gc_min_time <= current_time()))
1278
    rt_schedule_prune(table);
1279

    
1280
  if (old_ok && p->rte_remove)
1281
    p->rte_remove(net, old);
1282
  if (new_ok && p->rte_insert)
1283
    p->rte_insert(net, new);
1284

    
1285
  if (old)
1286
    rte_free_quick(old);
1287
}
1288

    
1289
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
1290

    
1291
static inline void
1292
rte_update_lock(void)
1293
{
1294
  rte_update_nest_cnt++;
1295
}
1296

    
1297
static inline void
1298
rte_update_unlock(void)
1299
{
1300
  if (!--rte_update_nest_cnt)
1301
    lp_flush(rte_update_pool);
1302
}
1303

    
1304
static inline void
1305
rte_hide_dummy_routes(net *net, rte **dummy)
1306
{
1307
  if (net->routes && net->routes->attrs->source == RTS_DUMMY)
1308
  {
1309
    *dummy = net->routes;
1310
    net->routes = (*dummy)->next;
1311
  }
1312
}
1313

    
1314
static inline void
1315
rte_unhide_dummy_routes(net *net, rte **dummy)
1316
{
1317
  if (*dummy)
1318
  {
1319
    (*dummy)->next = net->routes;
1320
    net->routes = *dummy;
1321
  }
1322
}
1323

    
1324
/**
1325
 * rte_update - enter a new update to a routing table
1326
 * @table: table to be updated
1327
 * @c: channel doing the update
1328
 * @net: network node
1329
 * @p: protocol submitting the update
1330
 * @src: protocol originating the update
1331
 * @new: a &rte representing the new route or %NULL for route removal.
1332
 *
1333
 * This function is called by the routing protocols whenever they discover
1334
 * a new route or wish to update/remove an existing route. The right announcement
1335
 * sequence is to build route attributes first (either un-cached with @aflags set
1336
 * to zero or a cached one using rta_lookup(); in this case please note that
1337
 * you need to increase the use count of the attributes yourself by calling
1338
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1339
 * the appropriate data and finally submit the new &rte by calling rte_update().
1340
 *
1341
 * @src specifies the protocol that originally created the route and the meaning
1342
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1343
 * same value as @new->attrs->proto. @p specifies the protocol that called
1344
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1345
 * stores @p in @new->sender;
1346
 *
1347
 * When rte_update() gets any route, it automatically validates it (checks,
1348
 * whether the network and next hop address are valid IP addresses and also
1349
 * whether a normal routing protocol doesn't try to smuggle a host or link
1350
 * scope route to the table), converts all protocol dependent attributes stored
1351
 * in the &rte to temporary extended attributes, consults import filters of the
1352
 * protocol to see if the route should be accepted and/or its attributes modified,
1353
 * stores the temporary attributes back to the &rte.
1354
 *
1355
 * Now, having a "public" version of the route, we
1356
 * automatically find any old route defined by the protocol @src
1357
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1358
 * recalculate the optimal route for this destination and finally broadcast
1359
 * the change (if any) to all routing protocols by calling rte_announce().
1360
 *
1361
 * All memory used for attribute lists and other temporary allocations is taken
1362
 * from a special linear pool @rte_update_pool and freed when rte_update()
1363
 * finishes.
1364
 */
1365

    
1366
void
1367
rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src)
1368
{
1369
  //log(L_INFO "rte_update2 - 1");
1370
  struct proto *p = c->proto;
1371
  struct proto_stats *stats = &c->stats;
1372
  struct filter *filter = c->in_filter;
1373
  ea_list *tmpa = NULL;
1374
  rte *dummy = NULL;
1375
  net *nn;
1376

    
1377
  ASSERT(c->channel_state == CS_UP);
1378

    
1379
  rte_update_lock();
1380
  //log(L_INFO "rte_update2 - 2");
1381
  if (new)
1382
    {
1383
      //log(L_INFO "rte_update2 - 3");
1384
      nn = net_get(c->table, n);
1385

    
1386
      new->net = nn;
1387
      new->sender = c;
1388

    
1389
      if (!new->pref)
1390
        new->pref = c->preference;
1391

    
1392
      stats->imp_updates_received++;
1393
      if (!rte_validate(new))
1394
        {
1395
          rte_trace_in(D_FILTERS, p, new, "invalid");
1396
          stats->imp_updates_invalid++;
1397
          goto drop;
1398
        }
1399

    
1400
      if (filter == FILTER_REJECT)
1401
        {
1402
          stats->imp_updates_filtered++;
1403
          rte_trace_in(D_FILTERS, p, new, "filtered out");
1404

    
1405
          if (! c->in_keep_filtered)
1406
            goto drop;
1407

    
1408
          /* new is a private copy, i could modify it */
1409
          new->flags |= REF_FILTERED;
1410
        }
1411
      else
1412
        {
1413
          tmpa = rte_make_tmp_attrs(new, rte_update_pool);
1414
          if (filter && (filter != FILTER_REJECT))
1415
            {
1416
              ea_list *old_tmpa = tmpa;
1417
              int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
1418
              if (fr > F_ACCEPT)
1419
                {
1420
                  stats->imp_updates_filtered++;
1421
                  rte_trace_in(D_FILTERS, p, new, "filtered out");
1422

    
1423
                  if (! c->in_keep_filtered)
1424
                    goto drop;
1425

    
1426
                  new->flags |= REF_FILTERED;
1427
                }
1428
              if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
1429
                src->proto->store_tmp_attrs(new, tmpa);
1430
            }
1431
        }
1432
      if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1433
        new->attrs = rta_lookup(new->attrs);
1434
      new->flags |= REF_COW;
1435
    }
1436
  else
1437
    {
1438
      //log(L_INFO "rte_update2 - 4");
1439
      stats->imp_withdraws_received++;
1440

    
1441
      if (!(nn = net_find(c->table, n)) || !src)
1442
        {
1443
          stats->imp_withdraws_ignored++;
1444
          rte_update_unlock();
1445
          return;
1446
        }
1447
    }
1448

    
1449
 recalc:
1450
  //log(L_INFO "rte_update2 - 6");
1451
  rte_hide_dummy_routes(nn, &dummy);
1452
  rte_recalculate(c, nn, new, src);
1453
  rte_unhide_dummy_routes(nn, &dummy);
1454
  rte_update_unlock();
1455
  //log(L_INFO "rte_update2 - 7");
1456
  return;
1457

    
1458
 drop:
1459
  //log(L_INFO "rte_update2 - 5");
1460
  rte_free(new);
1461
  new = NULL;
1462
  goto recalc;
1463
}
1464

    
1465
void
1466
rte_update3(struct channel *c, const net_addr *n, rte *new, struct rte_src *src, int variazione)
1467
{
1468
  if(variazione == 0){
1469
    rte_update2(c,n,new,src);
1470
    return;
1471
  }
1472

    
1473
  //log(L_INFO "il load è variato, è qui che dovrò intervenire");
1474
  //log(L_INFO "rte_update2 - 1");
1475
  struct proto *p = c->proto;
1476
  struct proto_stats *stats = &c->stats;
1477
  struct filter *filter = c->in_filter;
1478
  ea_list *tmpa = NULL;
1479
  rte *dummy = NULL;
1480
  net *nn;
1481

    
1482
  ASSERT(c->channel_state == CS_UP);
1483

    
1484
  rte_update_lock();
1485
  //log(L_INFO "rte_update2 - 2");
1486
  if (new)
1487
  {
1488
    //log(L_INFO "rte_update2 - 3");
1489
    nn = net_get(c->table, n);
1490

    
1491
    new->net = nn;
1492
    new->sender = c;
1493

    
1494
    if (!new->pref)
1495
    new->pref = c->preference;
1496

    
1497
    stats->imp_updates_received++;
1498
    if (!rte_validate(new))
1499
    {
1500
      rte_trace_in(D_FILTERS, p, new, "invalid");
1501
      stats->imp_updates_invalid++;
1502
      goto drop;
1503
    }
1504

    
1505
    if (filter == FILTER_REJECT)
1506
    {
1507
      stats->imp_updates_filtered++;
1508
      rte_trace_in(D_FILTERS, p, new, "filtered out");
1509

    
1510
      if (! c->in_keep_filtered)
1511
      goto drop;
1512

    
1513
      /* new is a private copy, i could modify it */
1514
      new->flags |= REF_FILTERED;
1515
    }
1516
    else
1517
    {
1518
      tmpa = rte_make_tmp_attrs(new, rte_update_pool);
1519
      if (filter && (filter != FILTER_REJECT))
1520
      {
1521
        ea_list *old_tmpa = tmpa;
1522
        int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
1523
        if (fr > F_ACCEPT)
1524
        {
1525
          stats->imp_updates_filtered++;
1526
          rte_trace_in(D_FILTERS, p, new, "filtered out");
1527

    
1528
          if (! c->in_keep_filtered)
1529
          goto drop;
1530

    
1531
          new->flags |= REF_FILTERED;
1532
        }
1533
        if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
1534
          src->proto->store_tmp_attrs(new, tmpa);
1535
      }
1536
    }
1537
    if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1538
      new->attrs = rta_lookup(new->attrs);
1539
    new->flags |= REF_COW;
1540
  }
1541
  else
1542
  {
1543
    //log(L_INFO "rte_update2 - 4");
1544
    stats->imp_withdraws_received++;
1545

    
1546
    if (!(nn = net_find(c->table, n)) || !src)
1547
    {
1548
      stats->imp_withdraws_ignored++;
1549
      rte_update_unlock();
1550
      return;
1551
    }
1552
  }
1553

    
1554
  recalc:
1555
    //log(L_INFO "rte_update2 - 6");
1556
    rte_hide_dummy_routes(nn, &dummy);
1557
    rte_recalculate(c, nn, new, src);
1558
    rte_unhide_dummy_routes(nn, &dummy);
1559
    rte_update_unlock();
1560
    //log(L_INFO "rte_update2 - 7");
1561
    return;
1562

    
1563
  drop:
1564
    //log(L_INFO "rte_update2 - 5");
1565
    rte_free(new);
1566
    new = NULL;
1567
    goto recalc;
1568
}
1569

    
1570
/* Independent call to rte_announce(), used from next hop
1571
   recalculation, outside of rte_update(). new must be non-NULL */
1572
static inline void
1573
rte_announce_i(rtable *tab, unsigned type, net *net, rte *new, rte *old,
1574
               rte *new_best, rte *old_best)
1575
{
1576
  rte_update_lock();
1577
  rte_announce(tab, type, net, new, old, new_best, old_best, NULL);
1578
  rte_update_unlock();
1579
}
1580

    
1581
static inline void
1582
rte_discard(rte *old)        /* Non-filtered route deletion, used during garbage collection */
1583
{
1584
  rte_update_lock();
1585
  rte_recalculate(old->sender, old->net, NULL, old->attrs->src);
1586
  rte_update_unlock();
1587
}
1588

    
1589
/* Check rtable for best route to given net whether it would be exported do p */
1590
int
1591
rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter)
1592
{
1593
  net *n = net_find(t, a);
1594
  rte *rt = n ? n->routes : NULL;
1595

    
1596
  if (!rte_is_valid(rt))
1597
    return 0;
1598

    
1599
  rte_update_lock();
1600

    
1601
  /* Rest is stripped down export_filter() */
1602
  ea_list *tmpa = rte_make_tmp_attrs(rt, rte_update_pool);
1603
  int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0;
1604
  if (v == RIC_PROCESS)
1605
    v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1606

    
1607
   /* Discard temporary rte */
1608
  if (rt != n->routes)
1609
    rte_free(rt);
1610

    
1611
  rte_update_unlock();
1612

    
1613
  return v > 0;
1614
}
1615

    
1616

    
1617
/**
1618
 * rt_refresh_begin - start a refresh cycle
1619
 * @t: related routing table
1620
 * @c related channel
1621
 *
1622
 * This function starts a refresh cycle for given routing table and announce
1623
 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1624
 * routes to the routing table (by rte_update()). After that, all protocol
1625
 * routes (more precisely routes with @c as @sender) not sent during the
1626
 * refresh cycle but still in the table from the past are pruned. This is
1627
 * implemented by marking all related routes as stale by REF_STALE flag in
1628
 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1629
 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1630
 */
1631
void
1632
rt_refresh_begin(rtable *t, struct channel *c)
1633
{
1634
  FIB_WALK(&t->fib, net, n)
1635
    {
1636
      rte *e;
1637
      for (e = n->routes; e; e = e->next)
1638
        if (e->sender == c)
1639
          e->flags |= REF_STALE;
1640
    }
1641
  FIB_WALK_END;
1642
}
1643

    
1644
/**
1645
 * rt_refresh_end - end a refresh cycle
1646
 * @t: related routing table
1647
 * @c: related channel
1648
 *
1649
 * This function ends a refresh cycle for given routing table and announce
1650
 * hook. See rt_refresh_begin() for description of refresh cycles.
1651
 */
1652
void
1653
rt_refresh_end(rtable *t, struct channel *c)
1654
{
1655
  int prune = 0;
1656

    
1657
  FIB_WALK(&t->fib, net, n)
1658
    {
1659
      rte *e;
1660
      for (e = n->routes; e; e = e->next)
1661
        if ((e->sender == c) && (e->flags & REF_STALE))
1662
          {
1663
            e->flags |= REF_DISCARD;
1664
            prune = 1;
1665
          }
1666
    }
1667
  FIB_WALK_END;
1668

    
1669
  if (prune)
1670
    rt_schedule_prune(t);
1671
}
1672

    
1673

    
1674
/**
1675
 * rte_dump - dump a route
1676
 * @e: &rte to be dumped
1677
 *
1678
 * This functions dumps contents of a &rte to debug output.
1679
 */
1680
void
1681
rte_dump(rte *e)
1682
{
1683
  net *n = e->net;
1684
  debug("%-1N ", n->n.addr);
1685
  debug("KF=%02x PF=%02x pref=%d ", n->n.flags, e->pflags, e->pref);
1686
  rta_dump(e->attrs);
1687
  if (e->attrs->src->proto->proto->dump_attrs)
1688
    e->attrs->src->proto->proto->dump_attrs(e);
1689
  debug("\n");
1690
}
1691

    
1692
/**
1693
 * rt_dump - dump a routing table
1694
 * @t: routing table to be dumped
1695
 *
1696
 * This function dumps contents of a given routing table to debug output.
1697
 */
1698
void
1699
rt_dump(rtable *t)
1700
{
1701
  debug("Dump of routing table <%s>\n", t->name);
1702
#ifdef DEBUGGING
1703
  fib_check(&t->fib);
1704
#endif
1705
  FIB_WALK(&t->fib, net, n)
1706
    {
1707
      rte *e;
1708
      for(e=n->routes; e; e=e->next)
1709
        rte_dump(e);
1710
    }
1711
  FIB_WALK_END;
1712
  debug("\n");
1713
}
1714

    
1715
/**
1716
 * rt_dump_all - dump all routing tables
1717
 *
1718
 * This function dumps contents of all routing tables to debug output.
1719
 */
1720
void
1721
rt_dump_all(void)
1722
{
1723
  rtable *t;
1724

    
1725
  WALK_LIST(t, routing_tables)
1726
    rt_dump(t);
1727
}
1728

    
1729
static inline void
1730
rt_schedule_hcu(rtable *tab)
1731
{
1732
  if (tab->hcu_scheduled)
1733
    return;
1734

    
1735
  tab->hcu_scheduled = 1;
1736
  ev_schedule(tab->rt_event);
1737
}
1738

    
1739
static inline void
1740
rt_schedule_nhu(rtable *tab)
1741
{
1742
  if (tab->nhu_state == NHU_CLEAN)
1743
    ev_schedule(tab->rt_event);
1744

    
1745
  /* state change:
1746
   *   NHU_CLEAN   -> NHU_SCHEDULED
1747
   *   NHU_RUNNING -> NHU_DIRTY
1748
   */
1749
  tab->nhu_state |= NHU_SCHEDULED;
1750
}
1751

    
1752
void
1753
rt_schedule_prune(rtable *tab)
1754
{
1755
  if (tab->prune_state == 0)
1756
    ev_schedule(tab->rt_event);
1757

    
1758
  /* state change 0->1, 2->3 */
1759
  tab->prune_state |= 1;
1760
}
1761

    
1762

    
1763
static void
1764
rt_event(void *ptr)
1765
{
1766
  rtable *tab = ptr;
1767

    
1768
  rt_lock_table(tab);
1769

    
1770
  if (tab->hcu_scheduled)
1771
    rt_update_hostcache(tab);
1772

    
1773
  if (tab->nhu_state)
1774
    rt_next_hop_update(tab);
1775

    
1776
  if (tab->prune_state)
1777
    rt_prune_table(tab);
1778

    
1779
  rt_unlock_table(tab);
1780
}
1781

    
1782
void
1783
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
1784
{
1785
  bzero(t, sizeof(*t));
1786
  t->name = name;
1787
  t->config = cf;
1788
  t->addr_type = cf ? cf->addr_type : NET_IP4;
1789
  fib_init(&t->fib, p, t->addr_type, sizeof(net), OFFSETOF(net, n), 0, NULL);
1790
  init_list(&t->channels);
1791

    
1792
  if (cf)
1793
    {
1794
      t->rt_event = ev_new(p);
1795
      t->rt_event->hook = rt_event;
1796
      t->rt_event->data = t;
1797
      t->gc_time = current_time();
1798
    }
1799
}
1800

    
1801
/**
1802
 * rt_init - initialize routing tables
1803
 *
1804
 * This function is called during BIRD startup. It initializes the
1805
 * routing table module.
1806
 */
1807
void
1808
rt_init(void)
1809
{
1810
  rta_init();
1811
  rt_table_pool = rp_new(&root_pool, "Routing tables");
1812
  rte_update_pool = lp_new_default(rt_table_pool);
1813
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
1814
  init_list(&routing_tables);
1815
}
1816

    
1817

    
1818
/**
1819
 * rt_prune_table - prune a routing table
1820
 *
1821
 * The prune loop scans routing tables and removes routes belonging to flushing
1822
 * protocols, discarded routes and also stale network entries. It is called from
1823
 * rt_event(). The event is rescheduled if the current iteration do not finish
1824
 * the table. The pruning is directed by the prune state (@prune_state),
1825
 * specifying whether the prune cycle is scheduled or running, and there
1826
 * is also a persistent pruning iterator (@prune_fit).
1827
 *
1828
 * The prune loop is used also for channel flushing. For this purpose, the
1829
 * channels to flush are marked before the iteration and notified after the
1830
 * iteration.
1831
 */
1832
static void
1833
rt_prune_table(rtable *tab)
1834
{
1835
  struct fib_iterator *fit = &tab->prune_fit;
1836
  int limit = 512;
1837

    
1838
  struct channel *c;
1839
  node *n, *x;
1840

    
1841
  DBG("Pruning route table %s\n", tab->name);
1842
#ifdef DEBUGGING
1843
  fib_check(&tab->fib);
1844
#endif
1845

    
1846
  if (tab->prune_state == 0)
1847
    return;
1848

    
1849
  if (tab->prune_state == 1)
1850
  {
1851
    /* Mark channels to flush */
1852
    WALK_LIST2(c, n, tab->channels, table_node)
1853
      if (c->channel_state == CS_FLUSHING)
1854
        c->flush_active = 1;
1855

    
1856
    FIB_ITERATE_INIT(fit, &tab->fib);
1857
    tab->prune_state = 2;
1858
  }
1859

    
1860
again:
1861
  FIB_ITERATE_START(&tab->fib, fit, net, n)
1862
    {
1863
      rte *e;
1864

    
1865
    rescan:
1866
      for (e=n->routes; e; e=e->next)
1867
        if (e->sender->flush_active || (e->flags & REF_DISCARD))
1868
          {
1869
            if (limit <= 0)
1870
              {
1871
                FIB_ITERATE_PUT(fit);
1872
                ev_schedule(tab->rt_event);
1873
                return;
1874
              }
1875

    
1876
            rte_discard(e);
1877
            limit--;
1878

    
1879
            goto rescan;
1880
          }
1881

    
1882
      if (!n->routes)                /* Orphaned FIB entry */
1883
        {
1884
          FIB_ITERATE_PUT(fit);
1885
          fib_delete(&tab->fib, n);
1886
          goto again;
1887
        }
1888
    }
1889
  FIB_ITERATE_END;
1890

    
1891
#ifdef DEBUGGING
1892
  fib_check(&tab->fib);
1893
#endif
1894

    
1895
  tab->gc_counter = 0;
1896
  tab->gc_time = current_time();
1897

    
1898
  /* state change 2->0, 3->1 */
1899
  tab->prune_state &= 1;
1900

    
1901
  if (tab->prune_state > 0)
1902
    ev_schedule(tab->rt_event);
1903

    
1904
  /* FIXME: This should be handled in a better way */
1905
  rt_prune_sources();
1906

    
1907
  /* Close flushed channels */
1908
  WALK_LIST2_DELSAFE(c, n, x, tab->channels, table_node)
1909
    if (c->flush_active)
1910
      {
1911
        c->flush_active = 0;
1912
        channel_set_state(c, CS_DOWN);
1913
      }
1914

    
1915
  return;
1916
}
1917

    
1918
void
1919
rt_preconfig(struct config *c)
1920
{
1921
  init_list(&c->tables);
1922

    
1923
  rt_new_table(cf_get_symbol("master4"), NET_IP4);
1924
  rt_new_table(cf_get_symbol("master6"), NET_IP6);
1925
}
1926

    
1927

    
1928
/*
1929
 * Some functions for handing internal next hop updates
1930
 * triggered by rt_schedule_nhu().
1931
 */
1932

    
1933
static inline int
1934
rta_next_hop_outdated(rta *a)
1935
{
1936
  struct hostentry *he = a->hostentry;
1937

    
1938
  if (!he)
1939
    return 0;
1940

    
1941
  if (!he->src)
1942
    return a->dest != RTD_UNREACHABLE;
1943

    
1944
  return (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
1945
    (!he->nexthop_linkable) || !nexthop_same(&(a->nh), &(he->src->nh));
1946
}
1947

    
1948
void
1949
rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls)
1950
{
1951
  a->hostentry = he;
1952
  a->dest = he->dest;
1953
  a->igp_metric = he->igp_metric;
1954

    
1955
  if (a->dest != RTD_UNICAST)
1956
  {
1957
    /* No nexthop */
1958
no_nexthop:
1959
    a->nh = (struct nexthop) {};
1960
    if (mls)
1961
    { /* Store the label stack for later changes */
1962
      a->nh.labels_orig = a->nh.labels = mls->len;
1963
      memcpy(a->nh.label, mls->stack, mls->len * sizeof(u32));
1964
    }
1965
    return;
1966
  }
1967

    
1968
  if (((!mls) || (!mls->len)) && he->nexthop_linkable)
1969
  { /* Just link the nexthop chain, no label append happens. */
1970
    memcpy(&(a->nh), &(he->src->nh), nexthop_size(&(he->src->nh)));
1971
    return;
1972
  }
1973

    
1974
  struct nexthop *nhp = NULL, *nhr = NULL;
1975
  int skip_nexthop = 0;
1976

    
1977
  for (struct nexthop *nh = &(he->src->nh); nh; nh = nh->next)
1978
  {
1979
    if (skip_nexthop)
1980
      skip_nexthop--;
1981
    else
1982
    {
1983
      nhr = nhp;
1984
      nhp = (nhp ? (nhp->next = lp_allocz(rte_update_pool, NEXTHOP_MAX_SIZE)) : &(a->nh));
1985
    }
1986

    
1987
    nhp->iface = nh->iface;
1988
    nhp->weight = nh->weight;
1989
    if (mls)
1990
    {
1991
      nhp->labels = nh->labels + mls->len;
1992
      nhp->labels_orig = mls->len;
1993
      if (nhp->labels <= MPLS_MAX_LABEL_STACK)
1994
      {
1995
        memcpy(nhp->label, nh->label, nh->labels * sizeof(u32)); /* First the hostentry labels */
1996
        memcpy(&(nhp->label[nh->labels]), mls->stack, mls->len * sizeof(u32)); /* Then the bottom labels */
1997
      }
1998
      else
1999
      {
2000
        log(L_WARN "Sum of label stack sizes %d + %d = %d exceedes allowed maximum (%d)",
2001
            nh->labels, mls->len, nhp->labels, MPLS_MAX_LABEL_STACK);
2002
        skip_nexthop++;
2003
        continue;
2004
      }
2005
    }
2006
    if (ipa_nonzero(nh->gw))
2007
    {
2008
      nhp->gw = nh->gw;                        /* Router nexthop */
2009
      nhp->flags |= (nh->flags & RNF_ONLINK);
2010
    }
2011
    else if (ipa_nonzero(he->link))
2012
      nhp->gw = he->link;                /* Device nexthop with link-local address known */
2013
    else
2014
      nhp->gw = he->addr;                /* Device nexthop with link-local address unknown */
2015
  }
2016

    
2017
  if (skip_nexthop)
2018
    if (nhr)
2019
      nhr->next = NULL;
2020
    else
2021
    {
2022
      a->dest = RTD_UNREACHABLE;
2023
      log(L_WARN "No valid nexthop remaining, setting route unreachable");
2024
      goto no_nexthop;
2025
    }
2026
}
2027

    
2028
static inline rte *
2029
rt_next_hop_update_rte(rtable *tab UNUSED, rte *old)
2030
{
2031
  rta *a = alloca(RTA_MAX_SIZE);
2032
  memcpy(a, old->attrs, rta_size(old->attrs));
2033

    
2034
  mpls_label_stack mls = { .len = a->nh.labels_orig };
2035
  memcpy(mls.stack, &a->nh.label[a->nh.labels - mls.len], mls.len * sizeof(u32));
2036

    
2037
  rta_apply_hostentry(a, old->attrs->hostentry, &mls);
2038
  a->aflags = 0;
2039

    
2040
  rte *e = sl_alloc(rte_slab);
2041
  memcpy(e, old, sizeof(rte));
2042
  e->attrs = rta_lookup(a);
2043

    
2044
  return e;
2045
}
2046

    
2047
static inline int
2048
rt_next_hop_update_net(rtable *tab, net *n)
2049
{
2050
  rte **k, *e, *new, *old_best, **new_best;
2051
  int count = 0;
2052
  int free_old_best = 0;
2053

    
2054
  old_best = n->routes;
2055
  if (!old_best)
2056
    return 0;
2057

    
2058
  for (k = &n->routes; e = *k; k = &e->next)
2059
    if (rta_next_hop_outdated(e->attrs))
2060
      {
2061
        new = rt_next_hop_update_rte(tab, e);
2062
        *k = new;
2063

    
2064
        rte_announce_i(tab, RA_ANY, n, new, e, NULL, NULL);
2065
        rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
2066

    
2067
        /* Call a pre-comparison hook */
2068
        /* Not really an efficient way to compute this */
2069
        if (e->attrs->src->proto->rte_recalculate)
2070
          e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
2071

    
2072
        if (e != old_best)
2073
          rte_free_quick(e);
2074
        else /* Freeing of the old best rte is postponed */
2075
          free_old_best = 1;
2076

    
2077
        e = new;
2078
        count++;
2079
      }
2080

    
2081
  if (!count)
2082
    return 0;
2083

    
2084
  /* Find the new best route */
2085
  new_best = NULL;
2086
  for (k = &n->routes; e = *k; k = &e->next)
2087
    {
2088
      if (!new_best || rte_better(e, *new_best))
2089
        new_best = k;
2090
    }
2091

    
2092
  /* Relink the new best route to the first position */
2093
  new = *new_best;
2094
  if (new != n->routes)
2095
    {
2096
      *new_best = new->next;
2097
      new->next = n->routes;
2098
      n->routes = new;
2099
    }
2100

    
2101
  /* Announce the new best route */
2102
  if (new != old_best)
2103
    {
2104
      rte_announce_i(tab, RA_OPTIMAL, n, new, old_best, NULL, NULL);
2105
      rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
2106
    }
2107

    
2108
  /* FIXME: Better announcement of merged routes */
2109
  rte_announce_i(tab, RA_MERGED, n, new, old_best, new, old_best);
2110

    
2111
  if (free_old_best)
2112
    rte_free_quick(old_best);
2113

    
2114
  return count;
2115
}
2116

    
2117
static void
2118
rt_next_hop_update(rtable *tab)
2119
{
2120
  struct fib_iterator *fit = &tab->nhu_fit;
2121
  int max_feed = 32;
2122

    
2123
  if (tab->nhu_state == NHU_CLEAN)
2124
    return;
2125

    
2126
  if (tab->nhu_state == NHU_SCHEDULED)
2127
    {
2128
      FIB_ITERATE_INIT(fit, &tab->fib);
2129
      tab->nhu_state = NHU_RUNNING;
2130
    }
2131

    
2132
  FIB_ITERATE_START(&tab->fib, fit, net, n)
2133
    {
2134
      if (max_feed <= 0)
2135
        {
2136
          FIB_ITERATE_PUT(fit);
2137
          ev_schedule(tab->rt_event);
2138
          return;
2139
        }
2140
      max_feed -= rt_next_hop_update_net(tab, n);
2141
    }
2142
  FIB_ITERATE_END;
2143

    
2144
  /* State change:
2145
   *   NHU_DIRTY   -> NHU_SCHEDULED
2146
   *   NHU_RUNNING -> NHU_CLEAN
2147
   */
2148
  tab->nhu_state &= 1;
2149

    
2150
  if (tab->nhu_state != NHU_CLEAN)
2151
    ev_schedule(tab->rt_event);
2152
}
2153

    
2154

    
2155
struct rtable_config *
2156
rt_new_table(struct symbol *s, uint addr_type)
2157
{
2158
  /* Hack that allows to 'redefine' the master table */
2159
  if ((s->class == SYM_TABLE) &&
2160
      (s->def == new_config->def_tables[addr_type]) &&
2161
      ((addr_type == NET_IP4) || (addr_type == NET_IP6)))
2162
    return s->def;
2163

    
2164
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
2165

    
2166
  cf_define_symbol(s, SYM_TABLE, c);
2167
  c->name = s->name;
2168
  c->addr_type = addr_type;
2169
  c->gc_max_ops = 1000;
2170
  c->gc_min_time = 5;
2171

    
2172
  add_tail(&new_config->tables, &c->n);
2173

    
2174
  /* First table of each type is kept as default */
2175
  if (! new_config->def_tables[addr_type])
2176
    new_config->def_tables[addr_type] = c;
2177

    
2178
  return c;
2179
}
2180

    
2181
/**
2182
 * rt_lock_table - lock a routing table
2183
 * @r: routing table to be locked
2184
 *
2185
 * Lock a routing table, because it's in use by a protocol,
2186
 * preventing it from being freed when it gets undefined in a new
2187
 * configuration.
2188
 */
2189
void
2190
rt_lock_table(rtable *r)
2191
{
2192
  r->use_count++;
2193
}
2194

    
2195
/**
2196
 * rt_unlock_table - unlock a routing table
2197
 * @r: routing table to be unlocked
2198
 *
2199
 * Unlock a routing table formerly locked by rt_lock_table(),
2200
 * that is decrease its use count and delete it if it's scheduled
2201
 * for deletion by configuration changes.
2202
 */
2203
void
2204
rt_unlock_table(rtable *r)
2205
{
2206
  if (!--r->use_count && r->deleted)
2207
    {
2208
      struct config *conf = r->deleted;
2209
      DBG("Deleting routing table %s\n", r->name);
2210
      r->config->table = NULL;
2211
      if (r->hostcache)
2212
        rt_free_hostcache(r);
2213
      rem_node(&r->n);
2214
      fib_free(&r->fib);
2215
      rfree(r->rt_event);
2216
      mb_free(r);
2217
      config_del_obstacle(conf);
2218
    }
2219
}
2220

    
2221
/**
2222
 * rt_commit - commit new routing table configuration
2223
 * @new: new configuration
2224
 * @old: original configuration or %NULL if it's boot time config
2225
 *
2226
 * Scan differences between @old and @new configuration and modify
2227
 * the routing tables according to these changes. If @new defines a
2228
 * previously unknown table, create it, if it omits a table existing
2229
 * in @old, schedule it for deletion (it gets deleted when all protocols
2230
 * disconnect from it by calling rt_unlock_table()), if it exists
2231
 * in both configurations, leave it unchanged.
2232
 */
2233
void
2234
rt_commit(struct config *new, struct config *old)
2235
{
2236
  struct rtable_config *o, *r;
2237

    
2238
  DBG("rt_commit:\n");
2239
  if (old)
2240
    {
2241
      WALK_LIST(o, old->tables)
2242
        {
2243
          rtable *ot = o->table;
2244
          if (!ot->deleted)
2245
            {
2246
              struct symbol *sym = cf_find_symbol(new, o->name);
2247
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
2248
                {
2249
                  DBG("\t%s: same\n", o->name);
2250
                  r = sym->def;
2251
                  r->table = ot;
2252
                  ot->name = r->name;
2253
                  ot->config = r;
2254
                  if (o->sorted != r->sorted)
2255
                    log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
2256
                }
2257
              else
2258
                {
2259
                  DBG("\t%s: deleted\n", o->name);
2260
                  ot->deleted = old;
2261
                  config_add_obstacle(old);
2262
                  rt_lock_table(ot);
2263
                  rt_unlock_table(ot);
2264
                }
2265
            }
2266
        }
2267
    }
2268

    
2269
  WALK_LIST(r, new->tables)
2270
    if (!r->table)
2271
      {
2272
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
2273
        DBG("\t%s: created\n", r->name);
2274
        rt_setup(rt_table_pool, t, r->name, r);
2275
        add_tail(&routing_tables, &t->n);
2276
        r->table = t;
2277
      }
2278
  DBG("\tdone\n");
2279
}
2280

    
2281
static inline void
2282
do_feed_channel(struct channel *c, net *n, rte *e)
2283
{
2284
  rte_update_lock();
2285
  if (c->ra_mode == RA_ACCEPTED)
2286
    rt_notify_accepted(c, n, e, NULL, NULL, c->refeeding ? 2 : 1);
2287
  else if (c->ra_mode == RA_MERGED)
2288
    rt_notify_merged(c, n, NULL, NULL, e, c->refeeding ? e : NULL, c->refeeding);
2289
  else /* RA_BASIC */
2290
    rt_notify_basic(c, n, e, c->refeeding ? e : NULL, c->refeeding);
2291
  rte_update_unlock();
2292
}
2293

    
2294
/**
2295
 * rt_feed_channel - advertise all routes to a channel
2296
 * @c: channel to be fed
2297
 *
2298
 * This function performs one pass of advertisement of routes to a channel that
2299
 * is in the ES_FEEDING state. It is called by the protocol code as long as it
2300
 * has something to do. (We avoid transferring all the routes in single pass in
2301
 * order not to monopolize CPU time.)
2302
 */
2303
int
2304
rt_feed_channel(struct channel *c)
2305
{
2306
  struct fib_iterator *fit = &c->feed_fit;
2307
  int max_feed = 256;
2308

    
2309
  ASSERT(c->export_state == ES_FEEDING);
2310

    
2311
  if (!c->feed_active)
2312
    {
2313
      FIB_ITERATE_INIT(fit, &c->table->fib);
2314
      c->feed_active = 1;
2315
    }
2316

    
2317
  FIB_ITERATE_START(&c->table->fib, fit, net, n)
2318
    {
2319
      rte *e = n->routes;
2320
      if (max_feed <= 0)
2321
        {
2322
          FIB_ITERATE_PUT(fit);
2323
          return 0;
2324
        }
2325

    
2326
      /* FIXME: perhaps we should change feed for RA_ACCEPTED to not use 'new' */
2327

    
2328
      if ((c->ra_mode == RA_OPTIMAL) ||
2329
          (c->ra_mode == RA_ACCEPTED) ||
2330
          (c->ra_mode == RA_MERGED))
2331
        if (rte_is_valid(e))
2332
          {
2333
            /* In the meantime, the protocol may fell down */
2334
            if (c->export_state != ES_FEEDING)
2335
              goto done;
2336

    
2337
            do_feed_channel(c, n, e);
2338
            max_feed--;
2339
          }
2340

    
2341
      if (c->ra_mode == RA_ANY)
2342
        for(e = n->routes; e; e = e->next)
2343
          {
2344
            /* In the meantime, the protocol may fell down */
2345
            if (c->export_state != ES_FEEDING)
2346
              goto done;
2347

    
2348
            if (!rte_is_valid(e))
2349
              continue;
2350

    
2351
            do_feed_channel(c, n, e);
2352
            max_feed--;
2353
          }
2354
    }
2355
  FIB_ITERATE_END;
2356

    
2357
done:
2358
  c->feed_active = 0;
2359
  return 1;
2360
}
2361

    
2362
/**
2363
 * rt_feed_baby_abort - abort protocol feeding
2364
 * @c: channel
2365
 *
2366
 * This function is called by the protocol code when the protocol stops or
2367
 * ceases to exist during the feeding.
2368
 */
2369
void
2370
rt_feed_channel_abort(struct channel *c)
2371
{
2372
  if (c->feed_active)
2373
    {
2374
      /* Unlink the iterator */
2375
      fit_get(&c->table->fib, &c->feed_fit);
2376
      c->feed_active = 0;
2377
    }
2378
}
2379

    
2380
static inline unsigned
2381
ptr_hash(void *ptr)
2382
{
2383
  uintptr_t p = (uintptr_t) ptr;
2384
  return p ^ (p << 8) ^ (p >> 16);
2385
}
2386

    
2387
static inline u32
2388
hc_hash(ip_addr a, rtable *dep)
2389
{
2390
  return ipa_hash(a) ^ ptr_hash(dep);
2391
}
2392

    
2393
static inline void
2394
hc_insert(struct hostcache *hc, struct hostentry *he)
2395
{
2396
  uint k = he->hash_key >> hc->hash_shift;
2397
  he->next = hc->hash_table[k];
2398
  hc->hash_table[k] = he;
2399
}
2400

    
2401
static inline void
2402
hc_remove(struct hostcache *hc, struct hostentry *he)
2403
{
2404
  struct hostentry **hep;
2405
  uint k = he->hash_key >> hc->hash_shift;
2406

    
2407
  for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
2408
  *hep = he->next;
2409
}
2410

    
2411
#define HC_DEF_ORDER 10
2412
#define HC_HI_MARK *4
2413
#define HC_HI_STEP 2
2414
#define HC_HI_ORDER 16                        /* Must be at most 16 */
2415
#define HC_LO_MARK /5
2416
#define HC_LO_STEP 2
2417
#define HC_LO_ORDER 10
2418

    
2419
static void
2420
hc_alloc_table(struct hostcache *hc, unsigned order)
2421
{
2422
  uint hsize = 1 << order;
2423
  hc->hash_order = order;
2424
  hc->hash_shift = 32 - order;
2425
  hc->hash_max = (order >= HC_HI_ORDER) ? ~0U : (hsize HC_HI_MARK);
2426
  hc->hash_min = (order <= HC_LO_ORDER) ?  0U : (hsize HC_LO_MARK);
2427

    
2428
  hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
2429
}
2430

    
2431
static void
2432
hc_resize(struct hostcache *hc, unsigned new_order)
2433
{
2434
  struct hostentry **old_table = hc->hash_table;
2435
  struct hostentry *he, *hen;
2436
  uint old_size = 1 << hc->hash_order;
2437
  uint i;
2438

    
2439
  hc_alloc_table(hc, new_order);
2440
  for (i = 0; i < old_size; i++)
2441
    for (he = old_table[i]; he != NULL; he=hen)
2442
      {
2443
        hen = he->next;
2444
        hc_insert(hc, he);
2445
      }
2446
  mb_free(old_table);
2447
}
2448

    
2449
static struct hostentry *
2450
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
2451
{
2452
  struct hostentry *he = sl_alloc(hc->slab);
2453

    
2454
  *he = (struct hostentry) {
2455
    .addr = a,
2456
    .link = ll,
2457
    .tab = dep,
2458
    .hash_key = k,
2459
  };
2460

    
2461
  add_tail(&hc->hostentries, &he->ln);
2462
  hc_insert(hc, he);
2463

    
2464
  hc->hash_items++;
2465
  if (hc->hash_items > hc->hash_max)
2466
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
2467

    
2468
  return he;
2469
}
2470

    
2471
static void
2472
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
2473
{
2474
  rta_free(he->src);
2475

    
2476
  rem_node(&he->ln);
2477
  hc_remove(hc, he);
2478
  sl_free(hc->slab, he);
2479

    
2480
  hc->hash_items--;
2481
  if (hc->hash_items < hc->hash_min)
2482
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
2483
}
2484

    
2485
static void
2486
rt_init_hostcache(rtable *tab)
2487
{
2488
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
2489
  init_list(&hc->hostentries);
2490

    
2491
  hc->hash_items = 0;
2492
  hc_alloc_table(hc, HC_DEF_ORDER);
2493
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
2494

    
2495
  hc->lp = lp_new(rt_table_pool, LP_GOOD_SIZE(1024));
2496
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2497

    
2498
  tab->hostcache = hc;
2499
}
2500

    
2501
static void
2502
rt_free_hostcache(rtable *tab)
2503
{
2504
  struct hostcache *hc = tab->hostcache;
2505

    
2506
  node *n;
2507
  WALK_LIST(n, hc->hostentries)
2508
    {
2509
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
2510
      rta_free(he->src);
2511

    
2512
      if (he->uc)
2513
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
2514
    }
2515

    
2516
  rfree(hc->slab);
2517
  rfree(hc->lp);
2518
  mb_free(hc->hash_table);
2519
  mb_free(hc);
2520
}
2521

    
2522
static void
2523
rt_notify_hostcache(rtable *tab, net *net)
2524
{
2525
  if (tab->hcu_scheduled)
2526
    return;
2527

    
2528
  if (trie_match_net(tab->hostcache->trie, net->n.addr))
2529
    rt_schedule_hcu(tab);
2530
}
2531

    
2532
static int
2533
if_local_addr(ip_addr a, struct iface *i)
2534
{
2535
  struct ifa *b;
2536

    
2537
  WALK_LIST(b, i->addrs)
2538
    if (ipa_equal(a, b->ip))
2539
      return 1;
2540

    
2541
  return 0;
2542
}
2543

    
2544
static u32
2545
rt_get_igp_metric(rte *rt)
2546
{
2547
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
2548

    
2549
  if (ea)
2550
    return ea->u.data;
2551

    
2552
  rta *a = rt->attrs;
2553

    
2554
#ifdef CONFIG_OSPF
2555
  if ((a->source == RTS_OSPF) ||
2556
      (a->source == RTS_OSPF_IA) ||
2557
      (a->source == RTS_OSPF_EXT1))
2558
    return rt->u.ospf.metric1;
2559
#endif
2560

    
2561
#ifdef CONFIG_RIP
2562
  if (a->source == RTS_RIP)
2563
    return rt->u.rip.metric;
2564
#endif
2565

    
2566
  if (a->source == RTS_DEVICE)
2567
    return 0;
2568

    
2569
  return IGP_METRIC_UNKNOWN;
2570
}
2571

    
2572
static int
2573
rt_update_hostentry(rtable *tab, struct hostentry *he)
2574
{
2575
  rta *old_src = he->src;
2576
  int pxlen = 0;
2577

    
2578
  /* Reset the hostentry */
2579
  he->src = NULL;
2580
  he->nexthop_linkable = 0;
2581
  he->dest = RTD_UNREACHABLE;
2582
  he->igp_metric = 0;
2583

    
2584
  net_addr he_addr;
2585
  net_fill_ip_host(&he_addr, he->addr);
2586
  net *n = net_route(tab, &he_addr);
2587
  if (n)
2588
    {
2589
      rte *e = n->routes;
2590
      rta *a = e->attrs;
2591
      pxlen = n->n.addr->pxlen;
2592

    
2593
      if (a->hostentry)
2594
        {
2595
          /* Recursive route should not depend on another recursive route */
2596
          log(L_WARN "Next hop address %I resolvable through recursive route for %N",
2597
              he->addr, n->n.addr);
2598
          goto done;
2599
        }
2600

    
2601
      he->dest = a->dest;
2602
      he->nexthop_linkable = 1;
2603
      if (he->dest == RTD_UNICAST)
2604
        {
2605
          for (struct nexthop *nh = &(a->nh); nh; nh = nh->next)
2606
            if (ipa_zero(nh->gw))
2607
              {
2608
                if (if_local_addr(he->addr, nh->iface))
2609
                  {
2610
                    /* The host address is a local address, this is not valid */
2611
                    log(L_WARN "Next hop address %I is a local address of iface %s",
2612
                        he->addr, nh->iface->name);
2613
                    goto done;
2614
                  }
2615

    
2616
                he->nexthop_linkable = 0;
2617
                break;
2618
              }
2619
        }
2620

    
2621
      he->src = rta_clone(a);
2622
      he->igp_metric = rt_get_igp_metric(e);
2623
    }
2624

    
2625
done:
2626
  /* Add a prefix range to the trie */
2627
  trie_add_prefix(tab->hostcache->trie, &he_addr, pxlen, he_addr.pxlen);
2628

    
2629
  rta_free(old_src);
2630
  return old_src != he->src;
2631
}
2632

    
2633
static void
2634
rt_update_hostcache(rtable *tab)
2635
{
2636
  struct hostcache *hc = tab->hostcache;
2637
  struct hostentry *he;
2638
  node *n, *x;
2639

    
2640
  /* Reset the trie */
2641
  lp_flush(hc->lp);
2642
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2643

    
2644
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
2645
    {
2646
      he = SKIP_BACK(struct hostentry, ln, n);
2647
      if (!he->uc)
2648
        {
2649
          hc_delete_hostentry(hc, he);
2650
          continue;
2651
        }
2652

    
2653
      if (rt_update_hostentry(tab, he))
2654
        rt_schedule_nhu(he->tab);
2655
    }
2656

    
2657
  tab->hcu_scheduled = 0;
2658
}
2659

    
2660
struct hostentry *
2661
rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
2662
{
2663
  struct hostentry *he;
2664

    
2665
  if (!tab->hostcache)
2666
    rt_init_hostcache(tab);
2667

    
2668
  u32 k = hc_hash(a, dep);
2669
  struct hostcache *hc = tab->hostcache;
2670
  for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
2671
    if (ipa_equal(he->addr, a) && (he->tab == dep))
2672
      return he;
2673

    
2674
  he = hc_new_hostentry(hc, a, ipa_zero(ll) ? a : ll, dep, k);
2675
  rt_update_hostentry(tab, he);
2676
  return he;
2677
}
2678

    
2679

    
2680
/*
2681
 *  Documentation for functions declared inline in route.h
2682
 */
2683
#if 0
2684

2685
/**
2686
 * net_find - find a network entry
2687
 * @tab: a routing table
2688
 * @addr: address of the network
2689
 *
2690
 * net_find() looks up the given network in routing table @tab and
2691
 * returns a pointer to its &net entry or %NULL if no such network
2692
 * exists.
2693
 */
2694
static inline net *net_find(rtable *tab, net_addr *addr)
2695
{ DUMMY; }
2696

2697
/**
2698
 * net_get - obtain a network entry
2699
 * @tab: a routing table
2700
 * @addr: address of the network
2701
 *
2702
 * net_get() looks up the given network in routing table @tab and
2703
 * returns a pointer to its &net entry. If no such entry exists, it's
2704
 * created.
2705
 */
2706
static inline net *net_get(rtable *tab, net_addr *addr)
2707
{ DUMMY; }
2708

2709
/**
2710
 * rte_cow - copy a route for writing
2711
 * @r: a route entry to be copied
2712
 *
2713
 * rte_cow() takes a &rte and prepares it for modification. The exact action
2714
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2715
 * just returned unchanged, else a new temporary entry with the same contents
2716
 * is created.
2717
 *
2718
 * The primary use of this function is inside the filter machinery -- when
2719
 * a filter wants to modify &rte contents (to change the preference or to
2720
 * attach another set of attributes), it must ensure that the &rte is not
2721
 * shared with anyone else (and especially that it isn't stored in any routing
2722
 * table).
2723
 *
2724
 * Result: a pointer to the new writable &rte.
2725
 */
2726
static inline rte * rte_cow(rte *r)
2727
{ DUMMY; }
2728

2729
#endif