Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 5e173e9f

History | View | Annotate | Download (64.8 KB)

1 62aa008a Martin Mares
/*
2 58740ed4 Martin Mares
 *        BIRD -- Routing Tables
3 62aa008a Martin Mares
 *
4 50fe90ed Martin Mares
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5 62aa008a Martin Mares
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8
9 58740ed4 Martin Mares
/**
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 725270cb Martin Mares
 * There are multiple routing tables (a primary one together with any
17 58740ed4 Martin Mares
 * number of secondary ones if requested by the configuration). Each table
18
 * is basically a FIB containing entries describing the individual
19 58f7d004 Martin Mares
 * destination networks. For each network (represented by structure &net),
20 725270cb Martin Mares
 * 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 58740ed4 Martin Mares
 * 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 6b9fa320 Martin Mares
#undef LOCAL_DEBUG
32 1a54b1c6 Martin Mares
33 62aa008a Martin Mares
#include "nest/bird.h"
34
#include "nest/route.h"
35 2326b001 Martin Mares
#include "nest/protocol.h"
36 730f2e2c Martin Mares
#include "nest/cli.h"
37
#include "nest/iface.h"
38 2326b001 Martin Mares
#include "lib/resource.h"
39 5996da6a Martin Mares
#include "lib/event.h"
40 730f2e2c Martin Mares
#include "lib/string.h"
41 0e02abfd Martin Mares
#include "conf/conf.h"
42 529c4149 Martin Mares
#include "filter/filter.h"
43 221135d6 Martin Mares
#include "lib/string.h"
44 10af3676 Ondrej Filip
#include "lib/alloca.h"
45 7d875e09 Martin Mares
46 acb60628 Ondrej Zajicek
pool *rt_table_pool;
47
48 2326b001 Martin Mares
static slab *rte_slab;
49 e2dc2f30 Martin Mares
static linpool *rte_update_pool;
50 2326b001 Martin Mares
51 0e02abfd Martin Mares
static list routing_tables;
52 5996da6a Martin Mares
53 cfd46ee4 Martin Mares
static void rt_format_via(rte *e, byte *via);
54 cfe34a31 Ondrej Zajicek
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 0c791f87 Ondrej Zajicek
static inline int rt_prune_table(rtable *tab);
59 cfe34a31 Ondrej Zajicek
static inline void rt_schedule_gc(rtable *tab);
60 0c791f87 Ondrej Zajicek
static inline void rt_schedule_prune(rtable *tab);
61
62 cfd46ee4 Martin Mares
63 094d2bdb Ondrej Zajicek
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 d1e146f2 Ondrej Zajicek
/* Like fib_route(), but skips empty net entries */
72 fe9f1a6d Ondrej Zajicek (work)
/*
73 d1e146f2 Ondrej Zajicek
static net *
74
net_route(rtable *tab, ip_addr a, int len)
75
{
76
  ip_addr a0;
77
  net *n;
78

79
  while (len >= 0)
80
    {
81
      a0 = ipa_and(a, ipa_mkmask(len));
82
      n = fib_find(&tab->fib, &a0, len);
83 cf98be7b Ondrej Zajicek
      if (n && rte_is_valid(n->routes))
84 d1e146f2 Ondrej Zajicek
        return n;
85
      len--;
86
    }
87
  return NULL;
88
}
89 fe9f1a6d Ondrej Zajicek (work)
*/
90 2326b001 Martin Mares
91 58740ed4 Martin Mares
/**
92
 * rte_find - find a route
93
 * @net: network node
94 094d2bdb Ondrej Zajicek
 * @src: route source
95 58740ed4 Martin Mares
 *
96
 * The rte_find() function returns a route for destination @net
97 094d2bdb Ondrej Zajicek
 * which is from route source @src.
98 58740ed4 Martin Mares
 */
99 2326b001 Martin Mares
rte *
100 094d2bdb Ondrej Zajicek
rte_find(net *net, struct rte_src *src)
101 2326b001 Martin Mares
{
102
  rte *e = net->routes;
103
104 094d2bdb Ondrej Zajicek
  while (e && e->attrs->src != src)
105 2326b001 Martin Mares
    e = e->next;
106
  return e;
107
}
108
109 58740ed4 Martin Mares
/**
110
 * rte_get_temp - get a temporary &rte
111 3ce8c610 Martin Mares
 * @a: attributes to assign to the new route (a &rta; in case it's
112 2e9b2421 Martin Mares
 * un-cached, rte_update() will create a cached copy automatically)
113 58740ed4 Martin Mares
 *
114
 * Create a temporary &rte and bind it with the attributes @a.
115
 * Also set route preference to the default preference set for
116
 * the protocol.
117
 */
118 2326b001 Martin Mares
rte *
119
rte_get_temp(rta *a)
120
{
121
  rte *e = sl_alloc(rte_slab);
122
123
  e->attrs = a;
124 0cdbd397 Martin Mares
  e->flags = 0;
125 094d2bdb Ondrej Zajicek
  e->pref = a->src->proto->preference;
126 2326b001 Martin Mares
  return e;
127
}
128
129 e2dc2f30 Martin Mares
rte *
130
rte_do_cow(rte *r)
131
{
132
  rte *e = sl_alloc(rte_slab);
133
134
  memcpy(e, r, sizeof(rte));
135
  e->attrs = rta_clone(r->attrs);
136
  e->flags = 0;
137
  return e;
138
}
139
140 8d9eef17 Ondrej Zajicek
/**
141
 * rte_cow_rta - get a private writable copy of &rte with writable &rta
142
 * @r: a route entry to be copied
143
 * @lp: a linpool from which to allocate &rta
144
 *
145
 * rte_cow_rta() takes a &rte and prepares it and associated &rta for
146
 * modification. There are three possibilities: First, both &rte and &rta are
147
 * private copies, in that case they are returned unchanged.  Second, &rte is
148
 * private copy, but &rta is cached, in that case &rta is duplicated using
149
 * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
150
 * both structures are duplicated by rte_do_cow() and rta_do_cow().
151
 *
152
 * Note that in the second case, cached &rta loses one reference, while private
153
 * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
154
 * nexthops, ...) with it. To work properly, original shared &rta should have
155
 * another reference during the life of created private copy.
156
 *
157
 * Result: a pointer to the new writable &rte with writable &rta.
158
 */
159
rte *
160
rte_cow_rta(rte *r, linpool *lp)
161
{
162
  if (!rta_is_cached(r->attrs))
163
    return r;
164
165
  rte *e = rte_cow(r);
166
  rta *a = rta_do_cow(r->attrs, lp);
167
  rta_free(e->attrs);
168
  e->attrs = a;
169
  return e;
170
}
171
172 2326b001 Martin Mares
static int                                /* Actually better or at least as good as */
173
rte_better(rte *new, rte *old)
174
{
175 d9f330c5 Martin Mares
  int (*better)(rte *, rte *);
176
177 cf98be7b Ondrej Zajicek
  if (!rte_is_valid(old))
178 2326b001 Martin Mares
    return 1;
179 cf98be7b Ondrej Zajicek
  if (!rte_is_valid(new))
180
    return 0;
181
182 2326b001 Martin Mares
  if (new->pref > old->pref)
183
    return 1;
184
  if (new->pref < old->pref)
185
    return 0;
186 094d2bdb Ondrej Zajicek
  if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
187 4c1b4e1a Martin Mares
    {
188
      /*
189
       *  If the user has configured protocol preferences, so that two different protocols
190
       *  have the same preference, try to break the tie by comparing addresses. Not too
191
       *  useful, but keeps the ordering of routes unambiguous.
192
       */
193 094d2bdb Ondrej Zajicek
      return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
194 4c1b4e1a Martin Mares
    }
195 094d2bdb Ondrej Zajicek
  if (better = new->attrs->src->proto->rte_better)
196 d9f330c5 Martin Mares
    return better(new, old);
197
  return 0;
198 2326b001 Martin Mares
}
199
200 8d9eef17 Ondrej Zajicek
static int
201
rte_mergable(rte *pri, rte *sec)
202
{
203
  int (*mergable)(rte *, rte *);
204
205
  if (!rte_is_valid(pri) || !rte_is_valid(sec))
206
    return 0;
207
208
  if (pri->pref != sec->pref)
209
    return 0;
210
211
  if (pri->attrs->src->proto->proto != sec->attrs->src->proto->proto)
212
    return 0;
213
214
  if (mergable = pri->attrs->src->proto->rte_mergable)
215
    return mergable(pri, sec);
216
217
  return 0;
218
}
219
220 cfd46ee4 Martin Mares
static void
221
rte_trace(struct proto *p, rte *e, int dir, char *msg)
222
{
223
  byte via[STD_ADDRESS_P_LENGTH+32];
224
225
  rt_format_via(e, via);
226 fe9f1a6d Ondrej Zajicek (work)
  log(L_TRACE "%s %c %s %N %s", p->name, dir, msg, e->net->n.addr, via);
227 cfd46ee4 Martin Mares
}
228
229
static inline void
230 ae80a2de Pavel Tvrdík
rte_trace_in(uint flag, struct proto *p, rte *e, char *msg)
231 cfd46ee4 Martin Mares
{
232
  if (p->debug & flag)
233 b0a47440 Martin Mares
    rte_trace(p, e, '>', msg);
234 cfd46ee4 Martin Mares
}
235
236
static inline void
237 ae80a2de Pavel Tvrdík
rte_trace_out(uint flag, struct proto *p, rte *e, char *msg)
238 cfd46ee4 Martin Mares
{
239
  if (p->debug & flag)
240 b0a47440 Martin Mares
    rte_trace(p, e, '<', msg);
241 cfd46ee4 Martin Mares
}
242
243 00a09f3c Ondrej Zajicek
static rte *
244
export_filter(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
245 529c4149 Martin Mares
{
246 c0adf7e9 Ondrej Zajicek
  struct proto *p = ah->proto;
247
  struct filter *filter = ah->out_filter;
248
  struct proto_stats *stats = ah->stats;
249 00a09f3c Ondrej Zajicek
  ea_list *tmpb = NULL;
250
  rte *rt;
251
  int v;
252 c0adf7e9 Ondrej Zajicek
253 00a09f3c Ondrej Zajicek
  rt = rt0;
254
  *rt_free = NULL;
255 7de45ba4 Martin Mares
256 00a09f3c Ondrej Zajicek
  if (!tmpa)
257 db027a41 Ondrej Zajicek
    tmpa = &tmpb;
258
259
  *tmpa = make_tmp_attrs(rt, rte_update_pool);
260 925fe2d3 Ondrej Zajicek
261 00a09f3c Ondrej Zajicek
  v = p->import_control ? p->import_control(p, &rt, tmpa, rte_update_pool) : 0;
262
  if (v < 0)
263
    {
264
      if (silent)
265
        goto reject;
266 11361a10 Ondrej Zajicek
267 00a09f3c Ondrej Zajicek
      stats->exp_updates_rejected++;
268 36da2857 Ondrej Zajicek
      if (v == RIC_REJECT)
269
        rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
270 00a09f3c Ondrej Zajicek
      goto reject;
271
    }
272
  if (v > 0)
273 e2dc2f30 Martin Mares
    {
274 00a09f3c Ondrej Zajicek
      if (!silent)
275
        rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
276
      goto accept;
277 e2dc2f30 Martin Mares
    }
278 925fe2d3 Ondrej Zajicek
279 00a09f3c Ondrej Zajicek
  v = filter && ((filter == FILTER_REJECT) ||
280
                 (f_run(filter, &rt, tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT));
281
  if (v)
282
    {
283
      if (silent)
284
        goto reject;
285
286
      stats->exp_updates_filtered++;
287
      rte_trace_out(D_FILTERS, p, rt, "filtered out");
288
      goto reject;
289 e2dc2f30 Martin Mares
    }
290 925fe2d3 Ondrej Zajicek
291 00a09f3c Ondrej Zajicek
 accept:
292
  if (rt != rt0)
293
    *rt_free = rt;
294
  return rt;
295
296
 reject:
297
  /* Discard temporary rte */
298
  if (rt != rt0)
299
    rte_free(rt);
300
  return NULL;
301
}
302
303
static void
304
do_rt_notify(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
305
{
306
  struct proto *p = ah->proto;
307
  struct proto_stats *stats = ah->stats;
308 925fe2d3 Ondrej Zajicek
309 abced4a9 Ondrej Zajicek
310 ab758e4f Ondrej Zajicek
  /*
311 abced4a9 Ondrej Zajicek
   * First, apply export limit.
312
   *
313 ab758e4f Ondrej Zajicek
   * Export route limits has several problems. Because exp_routes
314
   * counter is reset before refeed, we don't really know whether
315 abced4a9 Ondrej Zajicek
   * limit is breached and whether the update is new or not. Therefore
316 ab758e4f Ondrej Zajicek
   * the number of really exported routes may exceed the limit
317
   * temporarily (routes exported before and new routes in refeed).
318
   *
319
   * Minor advantage is that if the limit is decreased and refeed is
320
   * requested, the number of exported routes really decrease.
321
   *
322
   * Second problem is that with export limits, we don't know whether
323
   * old was really exported (it might be blocked by limit). When a
324
   * withdraw is exported, we announce it even when the previous
325
   * update was blocked. This is not a big issue, but the same problem
326
   * is in updating exp_routes counter. Therefore, to be consistent in
327
   * increases and decreases of exp_routes, we count exported routes
328
   * regardless of blocking by limits.
329
   *
330
   * Similar problem is in handling updates - when a new route is
331
   * received and blocking is active, the route would be blocked, but
332
   * when an update for the route will be received later, the update
333
   * would be propagated (as old != NULL). Therefore, we have to block
334
   * also non-new updates (contrary to import blocking).
335
   */
336 925fe2d3 Ondrej Zajicek
337 d9b77cc2 Ondrej Zajicek
  struct proto_limit *l = ah->out_limit;
338 ab758e4f Ondrej Zajicek
  if (l && new)
339 d9b77cc2 Ondrej Zajicek
    {
340 ab758e4f Ondrej Zajicek
      if ((!old || refeed) && (stats->exp_routes >= l->limit))
341 b662290f Ondrej Zajicek
        proto_notify_limit(ah, l, PLD_OUT, stats->exp_routes);
342 d9b77cc2 Ondrej Zajicek
343
      if (l->state == PLS_BLOCKED)
344
        {
345 ab758e4f Ondrej Zajicek
          stats->exp_routes++;        /* see note above */
346 d9b77cc2 Ondrej Zajicek
          stats->exp_updates_rejected++;
347
          rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
348 ab758e4f Ondrej Zajicek
          new = NULL;
349 abced4a9 Ondrej Zajicek
350
          if (!old)
351
            return;
352 d9b77cc2 Ondrej Zajicek
        }
353
    }
354
355 ab758e4f Ondrej Zajicek
356 925fe2d3 Ondrej Zajicek
  if (new)
357 9db74169 Ondrej Zajicek
    stats->exp_updates_accepted++;
358 925fe2d3 Ondrej Zajicek
  else
359 9db74169 Ondrej Zajicek
    stats->exp_withdraws_accepted++;
360 925fe2d3 Ondrej Zajicek
361 8a7fb885 Ondrej Zajicek
  /* Hack: We do not decrease exp_routes during refeed, we instead
362
     reset exp_routes at the start of refeed. */
363 925fe2d3 Ondrej Zajicek
  if (new)
364 9db74169 Ondrej Zajicek
    stats->exp_routes++;
365 8a7fb885 Ondrej Zajicek
  if (old && !refeed)
366 9db74169 Ondrej Zajicek
    stats->exp_routes--;
367 925fe2d3 Ondrej Zajicek
368 cfd46ee4 Martin Mares
  if (p->debug & D_ROUTES)
369
    {
370
      if (new && old)
371
        rte_trace_out(D_ROUTES, p, new, "replaced");
372
      else if (new)
373
        rte_trace_out(D_ROUTES, p, new, "added");
374 349e21bb Martin Mares
      else if (old)
375 cfd46ee4 Martin Mares
        rte_trace_out(D_ROUTES, p, old, "removed");
376
    }
377 08f0290a Martin Mares
  if (!new)
378 c0adf7e9 Ondrej Zajicek
    p->rt_notify(p, ah->table, net, NULL, old, NULL);
379 08f0290a Martin Mares
  else if (tmpa)
380
    {
381 2f711231 Martin Mares
      ea_list *t = tmpa;
382
      while (t->next)
383
        t = t->next;
384
      t->next = new->attrs->eattrs;
385 c0adf7e9 Ondrej Zajicek
      p->rt_notify(p, ah->table, net, new, old, tmpa);
386 2f711231 Martin Mares
      t->next = NULL;
387 08f0290a Martin Mares
    }
388
  else
389 c0adf7e9 Ondrej Zajicek
    p->rt_notify(p, ah->table, net, new, old, new->attrs->eattrs);
390 00a09f3c Ondrej Zajicek
}
391
392
static void
393 db027a41 Ondrej Zajicek
rt_notify_basic(struct announce_hook *ah, net *net, rte *new0, rte *old0, int refeed)
394 00a09f3c Ondrej Zajicek
{
395 86f567e1 Ondrej Zajicek
  struct proto *p = ah->proto;
396 00a09f3c Ondrej Zajicek
  struct proto_stats *stats = ah->stats;
397
398 86f567e1 Ondrej Zajicek
  rte *new = new0;
399
  rte *old = old0;
400 00a09f3c Ondrej Zajicek
  rte *new_free = NULL;
401
  rte *old_free = NULL;
402 db027a41 Ondrej Zajicek
  ea_list *tmpa = NULL;
403 00a09f3c Ondrej Zajicek
404
  if (new)
405
    stats->exp_updates_received++;
406
  else
407
    stats->exp_withdraws_received++;
408
409
  /*
410
   * This is a tricky part - we don't know whether route 'old' was
411
   * exported to protocol 'p' or was filtered by the export filter.
412
   * We try to run the export filter to know this to have a correct
413
   * value in 'old' argument of rte_update (and proper filter value)
414
   *
415
   * FIXME - this is broken because 'configure soft' may change
416
   * filters but keep routes. Refeed is expected to be called after
417
   * change of the filters and with old == new, therefore we do not
418 86f567e1 Ondrej Zajicek
   * even try to run the filter on an old route, This may lead to
419 00a09f3c Ondrej Zajicek
   * 'spurious withdraws' but ensure that there are no 'missing
420
   * withdraws'.
421
   *
422
   * This is not completely safe as there is a window between
423
   * reconfiguration and the end of refeed - if a newly filtered
424
   * route disappears during this period, proper withdraw is not
425
   * sent (because old would be also filtered) and the route is
426
   * not refeeded (because it disappeared before that).
427
   */
428
429
  if (new)
430
    new = export_filter(ah, new, &new_free, &tmpa, 0);
431
432
  if (old && !refeed)
433
    old = export_filter(ah, old, &old_free, NULL, 1);
434
435
  if (!new && !old)
436 86f567e1 Ondrej Zajicek
  {
437
    /*
438
     * As mentioned above, 'old' value may be incorrect in some race conditions.
439
     * We generally ignore it with the exception of withdraw to pipe protocol.
440
     * In that case we rather propagate unfiltered withdraws regardless of
441
     * export filters to ensure that when a protocol is flushed, its routes are
442
     * removed from all tables. Possible spurious unfiltered withdraws are not
443
     * problem here as they are ignored if there is no corresponding route at
444
     * the other end of the pipe. We directly call rt_notify() hook instead of
445
     * do_rt_notify() to avoid logging and stat counters.
446
     */
447
448
#ifdef CONFIG_PIPE
449
    if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto))
450
      p->rt_notify(p, ah->table, net, NULL, old0, NULL);
451
#endif
452
453 00a09f3c Ondrej Zajicek
    return;
454 86f567e1 Ondrej Zajicek
  }
455 00a09f3c Ondrej Zajicek
456
  do_rt_notify(ah, net, new, old, tmpa, refeed);
457
458
  /* Discard temporary rte's */
459
  if (new_free)
460
    rte_free(new_free);
461
  if (old_free)
462
    rte_free(old_free);
463
}
464
465
static void
466 db027a41 Ondrej Zajicek
rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old, int feed)
467 00a09f3c Ondrej Zajicek
{
468
  // struct proto *p = ah->proto;
469
  struct proto_stats *stats = ah->stats;
470
471 db027a41 Ondrej Zajicek
  rte *r;
472 00a09f3c Ondrej Zajicek
  rte *new_best = NULL;
473
  rte *old_best = NULL;
474
  rte *new_free = NULL;
475
  rte *old_free = NULL;
476 db027a41 Ondrej Zajicek
  ea_list *tmpa = NULL;
477 00a09f3c Ondrej Zajicek
478 cf98be7b Ondrej Zajicek
  /* Used to track whether we met old_changed position. If before_old is NULL
479
     old_changed was the first and we met it implicitly before current best route. */
480
  int old_meet = old_changed && !before_old;
481
482
  /* Note that before_old is either NULL or valid (not rejected) route.
483
     If old_changed is valid, before_old have to be too. If old changed route
484
     was not valid, caller must use NULL for both old_changed and before_old. */
485 00a09f3c Ondrej Zajicek
486
  if (new_changed)
487
    stats->exp_updates_received++;
488
  else
489
    stats->exp_withdraws_received++;
490
491
  /* First, find the new_best route - first accepted by filters */
492 cf98be7b Ondrej Zajicek
  for (r=net->routes; rte_is_valid(r); r=r->next)
493 00a09f3c Ondrej Zajicek
    {
494
      if (new_best = export_filter(ah, r, &new_free, &tmpa, 0))
495
        break;
496
497
      /* Note if we walked around the position of old_changed route */
498
      if (r == before_old)
499
        old_meet = 1;
500
    }
501
502
  /* 
503
   * Second, handle the feed case. That means we do not care for
504
   * old_best. It is NULL for feed, and the new_best for refeed. 
505
   * For refeed, there is a hack similar to one in rt_notify_basic()
506
   * to ensure withdraws in case of changed filters
507
   */
508
  if (feed)
509
    {
510
      if (feed == 2)        /* refeed */
511 cf98be7b Ondrej Zajicek
        old_best = new_best ? new_best :
512
          (rte_is_valid(net->routes) ? net->routes : NULL);
513 00a09f3c Ondrej Zajicek
      else
514
        old_best = NULL;
515
516
      if (!new_best && !old_best)
517
        return;
518
519
      goto found;
520
    }
521
522
  /*
523
   * Now, we find the old_best route. Generally, it is the same as the
524
   * new_best, unless new_best is the same as new_changed or
525
   * old_changed is accepted before new_best.
526
   *
527
   * There are four cases:
528
   *
529
   * - We would find and accept old_changed before new_best, therefore
530
   *   old_changed is old_best. In remaining cases we suppose this
531
   *   is not true.
532
   *
533
   * - We found no new_best, therefore there is also no old_best and
534
   *   we ignore this withdraw.
535
   *
536
   * - We found new_best different than new_changed, therefore
537
   *   old_best is the same as new_best and we ignore this update.
538
   *
539
   * - We found new_best the same as new_changed, therefore it cannot
540
   *   be old_best and we have to continue search for old_best.
541
   */
542
543
  /* First case */
544
  if (old_meet)
545
    if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
546
      goto found;
547
548
  /* Second case */
549
  if (!new_best)
550
    return;
551 d9b77cc2 Ondrej Zajicek
552 26822d8f Ondrej Zajicek
  /* Third case, we use r instead of new_best, because export_filter() could change it */
553 00a09f3c Ondrej Zajicek
  if (r != new_changed)
554
    {
555
      if (new_free)
556
        rte_free(new_free);
557
      return;
558
    }
559
560
  /* Fourth case */
561 cf98be7b Ondrej Zajicek
  for (r=r->next; rte_is_valid(r); r=r->next)
562 00a09f3c Ondrej Zajicek
    {
563
      if (old_best = export_filter(ah, r, &old_free, NULL, 1))
564
        goto found;
565
566
      if (r == before_old)
567
        if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
568
          goto found;
569
    }
570
571
  /* Implicitly, old_best is NULL and new_best is non-NULL */
572
573
 found:
574
  do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2));
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 529c4149 Martin Mares
}
582
583 8d9eef17 Ondrej Zajicek
584
static struct mpnh *
585
mpnh_merge_rta(struct mpnh *nhs, rta *a, int max)
586
{
587
  struct mpnh nh = { .gw = a->gw, .iface = a->iface };
588
  struct mpnh *nh2 = (a->dest == RTD_MULTIPATH) ? a->nexthops : &nh;
589
  return mpnh_merge(nhs, nh2, 1, 0, max, rte_update_pool);
590
}
591
592
rte *
593
rt_export_merged(struct announce_hook *ah, net *net, rte **rt_free, ea_list **tmpa, int silent)
594
{
595
  // struct proto *p = ah->proto;
596
  struct mpnh *nhs = NULL;
597
  rte *best0, *best, *rt0, *rt, *tmp;
598
599
  best0 = net->routes;
600
  *rt_free = NULL;
601
602
  if (!rte_is_valid(best0))
603
    return NULL;
604
605
  best = export_filter(ah, best0, rt_free, tmpa, silent);
606
607
  if (!best || !rte_is_reachable(best))
608
    return best;
609
610
  for (rt0 = best0->next; rt0; rt0 = rt0->next)
611
  {
612
    if (!rte_mergable(best0, rt0))
613
      continue;
614
615
    rt = export_filter(ah, rt0, &tmp, NULL, 1);
616
617
    if (!rt)
618
      continue;
619
620
    if (rte_is_reachable(rt))
621
      nhs = mpnh_merge_rta(nhs, rt->attrs, ah->proto->merge_limit);
622
623
    if (tmp)
624
      rte_free(tmp);
625
  }
626
627
  if (nhs)
628
  {
629
    nhs = mpnh_merge_rta(nhs, best->attrs, ah->proto->merge_limit);
630
631
    if (nhs->next)
632
    {
633
      best = rte_cow_rta(best, rte_update_pool);
634
      best->attrs->dest = RTD_MULTIPATH;
635
      best->attrs->nexthops = nhs;
636
    }
637
  }
638
639
  if (best != best0)
640
    *rt_free = best;
641
642
  return best;
643
}
644
645
646
static void
647
rt_notify_merged(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed,
648
                 rte *new_best, rte*old_best, int refeed)
649
{
650
  // struct proto *p = ah->proto;
651
652
  rte *new_best_free = NULL;
653
  rte *old_best_free = NULL;
654
  rte *new_changed_free = NULL;
655
  rte *old_changed_free = NULL;
656
  ea_list *tmpa = NULL;
657
658
  /* We assume that all rte arguments are either NULL or rte_is_valid() */
659
660
  /* This check should be done by the caller */
661
  if (!new_best && !old_best)
662
    return;
663
664
  /* Check whether the change is relevant to the merged route */
665
  if ((new_best == old_best) && !refeed)
666
  {
667
    new_changed = rte_mergable(new_best, new_changed) ?
668
      export_filter(ah, new_changed, &new_changed_free, NULL, 1) : NULL;
669
670
    old_changed = rte_mergable(old_best, old_changed) ?
671
      export_filter(ah, old_changed, &old_changed_free, NULL, 1) : NULL;
672
673
    if (!new_changed && !old_changed)
674
      return;
675
  }
676
677
  if (new_best)
678
    ah->stats->exp_updates_received++;
679
  else
680
    ah->stats->exp_withdraws_received++;
681
682
  /* Prepare new merged route */
683
  if (new_best)
684
    new_best = rt_export_merged(ah, net, &new_best_free, &tmpa, 0);
685
686
  /* Prepare old merged route (without proper merged next hops) */
687
  /* There are some issues with running filter on old route - see rt_notify_basic() */
688
  if (old_best && !refeed)
689
    old_best = export_filter(ah, old_best, &old_best_free, NULL, 1);
690
691
  if (new_best || old_best)
692
    do_rt_notify(ah, net, new_best, old_best, tmpa, refeed);
693
694
  /* Discard temporary rte's */
695
  if (new_best_free)
696
    rte_free(new_best_free);
697
  if (old_best_free)
698
    rte_free(old_best_free);
699
  if (new_changed_free)
700
    rte_free(new_changed_free);
701
  if (old_changed_free)
702
    rte_free(old_changed_free);
703
}
704
705
706 9a8f20fc Martin Mares
/**
707
 * rte_announce - announce a routing table change
708
 * @tab: table the route has been added to
709 23ac9e9a Ondrej Zajicek
 * @type: type of route announcement (RA_OPTIMAL or RA_ANY)
710 9a8f20fc Martin Mares
 * @net: network in question
711
 * @new: the new route to be announced
712 23ac9e9a Ondrej Zajicek
 * @old: the previous route for the same network
713 9a8f20fc Martin Mares
 *
714
 * This function gets a routing table update and announces it
715 f98e2915 Ondrej Zajicek
 * to all protocols that acccepts given type of route announcement
716
 * and are connected to the same table by their announcement hooks.
717 9a8f20fc Martin Mares
 *
718 f98e2915 Ondrej Zajicek
 * Route announcement of type RA_OPTIMAL si generated when optimal
719
 * route (in routing table @tab) changes. In that case @old stores the
720
 * old optimal route.
721 23ac9e9a Ondrej Zajicek
 *
722 f98e2915 Ondrej Zajicek
 * Route announcement of type RA_ANY si generated when any route (in
723
 * routing table @tab) changes In that case @old stores the old route
724
 * from the same protocol.
725
 *
726
 * For each appropriate protocol, we first call its import_control()
727
 * hook which performs basic checks on the route (each protocol has a
728
 * right to veto or force accept of the route before any filter is
729
 * asked) and adds default values of attributes specific to the new
730
 * protocol (metrics, tags etc.).  Then it consults the protocol's
731
 * export filter and if it accepts the route, the rt_notify() hook of
732
 * the protocol gets called.
733 9a8f20fc Martin Mares
 */
734 e2dc2f30 Martin Mares
static void
735 8d9eef17 Ondrej Zajicek
rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old,
736
             rte *new_best, rte *old_best, rte *before_old)
737 2326b001 Martin Mares
{
738 8d9eef17 Ondrej Zajicek
  if (!rte_is_valid(new))
739
    new = NULL;
740
741 cf98be7b Ondrej Zajicek
  if (!rte_is_valid(old))
742
    old = before_old = NULL;
743
744 8d9eef17 Ondrej Zajicek
  if (!rte_is_valid(new_best))
745
    new_best = NULL;
746
747
  if (!rte_is_valid(old_best))
748
    old_best = NULL;
749 cf98be7b Ondrej Zajicek
750
  if (!old && !new)
751
    return;
752 2326b001 Martin Mares
753 925fe2d3 Ondrej Zajicek
  if (type == RA_OPTIMAL)
754
    {
755
      if (new)
756 094d2bdb Ondrej Zajicek
        new->attrs->src->proto->stats.pref_routes++;
757 925fe2d3 Ondrej Zajicek
      if (old)
758 094d2bdb Ondrej Zajicek
        old->attrs->src->proto->stats.pref_routes--;
759 cfe34a31 Ondrej Zajicek
760
      if (tab->hostcache)
761
        rt_notify_hostcache(tab, net);
762 925fe2d3 Ondrej Zajicek
    }
763
764 cf98be7b Ondrej Zajicek
  struct announce_hook *a;
765 0e02abfd Martin Mares
  WALK_LIST(a, tab->hooks)
766 0a2e9d9f Martin Mares
    {
767 0c791f87 Ondrej Zajicek
      ASSERT(a->proto->export_state != ES_DOWN);
768 23ac9e9a Ondrej Zajicek
      if (a->proto->accept_ra_types == type)
769 00a09f3c Ondrej Zajicek
        if (type == RA_ACCEPTED)
770 db027a41 Ondrej Zajicek
          rt_notify_accepted(a, net, new, old, before_old, 0);
771 8d9eef17 Ondrej Zajicek
        else if (type == RA_MERGED)
772
          rt_notify_merged(a, net, new, old, new_best, old_best, 0);
773 00a09f3c Ondrej Zajicek
        else
774 db027a41 Ondrej Zajicek
          rt_notify_basic(a, net, new, old, 0);
775 0a2e9d9f Martin Mares
    }
776 2326b001 Martin Mares
}
777
778 421838ff Martin Mares
static inline int
779
rte_validate(rte *e)
780
{
781
  int c;
782
  net *n = e->net;
783
784 fe9f1a6d Ondrej Zajicek (work)
  // (n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
785
  if (!net_validate(n->n.addr))
786
  {
787
    log(L_WARN "Ignoring bogus prefix %N received via %s",
788
        n->n.addr, e->sender->proto->name);
789
    return 0;
790
  }
791 ff2857b0 Ondrej Zajicek
792 fe9f1a6d Ondrej Zajicek (work)
  c = net_classify(n->n.addr);
793 ff2857b0 Ondrej Zajicek
  if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
794 fe9f1a6d Ondrej Zajicek (work)
  {
795
    log(L_WARN "Ignoring bogus route %N received via %s",
796
        n->n.addr, e->sender->proto->name);
797
    return 0;
798
  }
799 ff2857b0 Ondrej Zajicek
800 421838ff Martin Mares
  return 1;
801
}
802
803 58740ed4 Martin Mares
/**
804
 * rte_free - delete a &rte
805
 * @e: &rte to be deleted
806
 *
807
 * rte_free() deletes the given &rte from the routing table it's linked to.
808
 */
809 04925e90 Martin Mares
void
810 2326b001 Martin Mares
rte_free(rte *e)
811
{
812 094d2bdb Ondrej Zajicek
  if (rta_is_cached(e->attrs))
813 04925e90 Martin Mares
    rta_free(e->attrs);
814
  sl_free(rte_slab, e);
815
}
816
817
static inline void
818
rte_free_quick(rte *e)
819
{
820 2326b001 Martin Mares
  rta_free(e->attrs);
821
  sl_free(rte_slab, e);
822
}
823
824 67be5b23 Martin Mares
static int
825
rte_same(rte *x, rte *y)
826
{
827
  return
828
    x->attrs == y->attrs &&
829
    x->flags == y->flags &&
830
    x->pflags == y->pflags &&
831
    x->pref == y->pref &&
832 094d2bdb Ondrej Zajicek
    (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y));
833 67be5b23 Martin Mares
}
834
835 70577529 Ondrej Zajicek
static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); }
836
837 e2dc2f30 Martin Mares
static void
838 db027a41 Ondrej Zajicek
rte_recalculate(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
839 2326b001 Martin Mares
{
840 c0adf7e9 Ondrej Zajicek
  struct proto *p = ah->proto;
841
  struct rtable *table = ah->table;
842
  struct proto_stats *stats = ah->stats;
843 1123e707 Ondrej Zajicek
  static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
844 00a09f3c Ondrej Zajicek
  rte *before_old = NULL;
845 2326b001 Martin Mares
  rte *old_best = net->routes;
846
  rte *old = NULL;
847 00a09f3c Ondrej Zajicek
  rte **k;
848 2326b001 Martin Mares
849
  k = &net->routes;                        /* Find and remove original route from the same protocol */
850
  while (old = *k)
851
    {
852 094d2bdb Ondrej Zajicek
      if (old->attrs->src == src)
853 2326b001 Martin Mares
        {
854 11787b84 Ondrej Zajicek
          /* If there is the same route in the routing table but from
855
           * a different sender, then there are two paths from the
856
           * source protocol to this routing table through transparent
857
           * pipes, which is not allowed.
858
           *
859
           * We log that and ignore the route. If it is withdraw, we
860
           * ignore it completely (there might be 'spurious withdraws',
861
           * see FIXME in do_rte_announce())
862
           */
863 c0adf7e9 Ondrej Zajicek
          if (old->sender->proto != p)
864 11787b84 Ondrej Zajicek
            {
865
              if (new)
866
                {
867 fe9f1a6d Ondrej Zajicek (work)
                  log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %N to table %s",
868
                      net->n.addr, table->name);
869 11787b84 Ondrej Zajicek
                  rte_free_quick(new);
870
                }
871
              return;
872
            }
873
874 0b761098 Martin Mares
          if (new && rte_same(old, new))
875 67be5b23 Martin Mares
            {
876
              /* No changes, ignore the new route */
877 cf98be7b Ondrej Zajicek
878 15550957 Ondrej Zajicek
              if (!rte_is_filtered(new))
879 cf98be7b Ondrej Zajicek
                {
880
                  stats->imp_updates_ignored++;
881
                  rte_trace_in(D_ROUTES, p, new, "ignored");
882
                }
883
884 67be5b23 Martin Mares
              rte_free_quick(new);
885
              return;
886
            }
887 2326b001 Martin Mares
          *k = old->next;
888
          break;
889
        }
890
      k = &old->next;
891 00a09f3c Ondrej Zajicek
      before_old = old;
892 2326b001 Martin Mares
    }
893
894 00a09f3c Ondrej Zajicek
  if (!old)
895
    before_old = NULL;
896
897 925fe2d3 Ondrej Zajicek
  if (!old && !new)
898
    {
899 9db74169 Ondrej Zajicek
      stats->imp_withdraws_ignored++;
900 925fe2d3 Ondrej Zajicek
      return;
901
    }
902
903 b662290f Ondrej Zajicek
  int new_ok = rte_is_ok(new);
904
  int old_ok = rte_is_ok(old);
905
906
  struct proto_limit *l = ah->rx_limit;
907 7d0a31de Ondrej Zajicek
  if (l && !old && new)
908 ebecb6f6 Ondrej Zajicek
    {
909 15550957 Ondrej Zajicek
      u32 all_routes = stats->imp_routes + stats->filt_routes;
910 cf98be7b Ondrej Zajicek
911
      if (all_routes >= l->limit)
912 b662290f Ondrej Zajicek
        proto_notify_limit(ah, l, PLD_RX, all_routes);
913 7d0a31de Ondrej Zajicek
914
      if (l->state == PLS_BLOCKED)
915
        {
916 b662290f Ondrej Zajicek
          /* In receive limit the situation is simple, old is NULL so
917
             we just free new and exit like nothing happened */
918
919 7d0a31de Ondrej Zajicek
          stats->imp_updates_ignored++;
920
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
921
          rte_free_quick(new);
922
          return;
923
        }
924 ebecb6f6 Ondrej Zajicek
    }
925
926 b662290f Ondrej Zajicek
  l = ah->in_limit;
927
  if (l && !old_ok && new_ok)
928
    {
929
      if (stats->imp_routes >= l->limit)
930
        proto_notify_limit(ah, l, PLD_IN, stats->imp_routes);
931
932
      if (l->state == PLS_BLOCKED)
933
        {
934
          /* In import limit the situation is more complicated. We
935
             shouldn't just drop the route, we should handle it like
936
             it was filtered. We also have to continue the route
937
             processing if old or new is non-NULL, but we should exit
938
             if both are NULL as this case is probably assumed to be
939
             already handled. */
940
941
          stats->imp_updates_ignored++;
942
          rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
943
944
          if (ah->in_keep_filtered)
945
            new->flags |= REF_FILTERED;
946
          else
947
            { rte_free_quick(new); new = NULL; }
948
949
          /* Note that old && !new could be possible when
950
             ah->in_keep_filtered changed in the recent past. */
951
952
          if (!old && !new)
953
            return;
954
955
          new_ok = 0;
956
          goto skip_stats1;
957
        }
958
    }
959 70577529 Ondrej Zajicek
960
  if (new_ok)
961 9db74169 Ondrej Zajicek
    stats->imp_updates_accepted++;
962 70577529 Ondrej Zajicek
  else if (old_ok)
963 9db74169 Ondrej Zajicek
    stats->imp_withdraws_accepted++;
964 70577529 Ondrej Zajicek
  else
965
    stats->imp_withdraws_ignored++;
966 925fe2d3 Ondrej Zajicek
967 b662290f Ondrej Zajicek
 skip_stats1:
968 925fe2d3 Ondrej Zajicek
969
  if (new)
970 15550957 Ondrej Zajicek
    rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
971 925fe2d3 Ondrej Zajicek
  if (old)
972 15550957 Ondrej Zajicek
    rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
973 925fe2d3 Ondrej Zajicek
974 26822d8f Ondrej Zajicek
  if (table->config->sorted)
975 2326b001 Martin Mares
    {
976 26822d8f Ondrej Zajicek
      /* If routes are sorted, just insert new route to appropriate position */
977
      if (new)
978
        {
979
          if (before_old && !rte_better(new, before_old))
980
            k = &before_old->next;
981
          else
982
            k = &net->routes;
983 c0973621 Ondrej Zajicek
984 26822d8f Ondrej Zajicek
          for (; *k; k=&(*k)->next)
985
            if (rte_better(new, *k))
986
              break;
987 c0973621 Ondrej Zajicek
988 26822d8f Ondrej Zajicek
          new->next = *k;
989
          *k = new;
990
        }
991 2326b001 Martin Mares
    }
992 26822d8f Ondrej Zajicek
  else
993 2326b001 Martin Mares
    {
994 26822d8f Ondrej Zajicek
      /* If routes are not sorted, find the best route and move it on
995
         the first position. There are several optimized cases. */
996
997 094d2bdb Ondrej Zajicek
      if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
998 26822d8f Ondrej Zajicek
        goto do_recalculate;
999
1000
      if (new && rte_better(new, old_best))
1001 2326b001 Martin Mares
        {
1002 26822d8f Ondrej Zajicek
          /* The first case - the new route is cleary optimal,
1003
             we link it at the first position */
1004
1005 c0973621 Ondrej Zajicek
          new->next = net->routes;
1006
          net->routes = new;
1007
        }
1008 26822d8f Ondrej Zajicek
      else if (old == old_best)
1009 c0973621 Ondrej Zajicek
        {
1010 26822d8f Ondrej Zajicek
          /* The second case - the old best route disappeared, we add the
1011
             new route (if we have any) to the list (we don't care about
1012
             position) and then we elect the new optimal route and relink
1013
             that route at the first position and announce it. New optimal
1014
             route might be NULL if there is no more routes */
1015
1016
        do_recalculate:
1017
          /* Add the new route to the list */
1018
          if (new)
1019 2326b001 Martin Mares
            {
1020 26822d8f Ondrej Zajicek
              new->next = net->routes;
1021
              net->routes = new;
1022
            }
1023
1024
          /* Find a new optimal route (if there is any) */
1025
          if (net->routes)
1026
            {
1027
              rte **bp = &net->routes;
1028
              for (k=&(*bp)->next; *k; k=&(*k)->next)
1029
                if (rte_better(*k, *bp))
1030
                  bp = k;
1031
1032
              /* And relink it */
1033
              rte *best = *bp;
1034
              *bp = best->next;
1035
              best->next = net->routes;
1036
              net->routes = best;
1037 2326b001 Martin Mares
            }
1038
        }
1039 26822d8f Ondrej Zajicek
      else if (new)
1040
        {
1041
          /* The third case - the new route is not better than the old
1042
             best route (therefore old_best != NULL) and the old best
1043
             route was not removed (therefore old_best == net->routes).
1044
             We just link the new route after the old best route. */
1045
1046
          ASSERT(net->routes != NULL);
1047
          new->next = net->routes->next;
1048
          net->routes->next = new;
1049
        }
1050
      /* The fourth (empty) case - suboptimal route was removed, nothing to do */
1051 2326b001 Martin Mares
    }
1052 c0973621 Ondrej Zajicek
1053 26822d8f Ondrej Zajicek
  if (new)
1054
    new->lastmod = now;
1055
1056
  /* Log the route change */
1057 70577529 Ondrej Zajicek
  if (p->debug & D_ROUTES)
1058 e8b29bdc Ondrej Zajicek
    {
1059 70577529 Ondrej Zajicek
      if (new_ok)
1060
        rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added");
1061
      else if (old_ok)
1062
        {
1063
          if (old != old_best)
1064
            rte_trace(p, old, '>', "removed");
1065
          else if (rte_is_ok(net->routes))
1066
            rte_trace(p, old, '>', "removed [replaced]");
1067
          else
1068
            rte_trace(p, old, '>', "removed [sole]");
1069
        }
1070 c0973621 Ondrej Zajicek
    }
1071
1072 26822d8f Ondrej Zajicek
  /* Propagate the route change */
1073 8d9eef17 Ondrej Zajicek
  rte_announce(table, RA_ANY, net, new, old, NULL, NULL, NULL);
1074 26822d8f Ondrej Zajicek
  if (net->routes != old_best)
1075 8d9eef17 Ondrej Zajicek
    rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, NULL, NULL);
1076 26822d8f Ondrej Zajicek
  if (table->config->sorted)
1077 8d9eef17 Ondrej Zajicek
    rte_announce(table, RA_ACCEPTED, net, new, old, NULL, NULL, before_old);
1078
  rte_announce(table, RA_MERGED, net, new, old, net->routes, old_best, NULL);
1079 00a09f3c Ondrej Zajicek
1080
  if (!net->routes &&
1081
      (table->gc_counter++ >= table->config->gc_max_ops) &&
1082
      (table->gc_time + table->config->gc_min_time <= now))
1083
    rt_schedule_gc(table);
1084
1085 70577529 Ondrej Zajicek
  if (old_ok && p->rte_remove)
1086
    p->rte_remove(net, old);
1087
  if (new_ok && p->rte_insert)
1088
    p->rte_insert(net, new);
1089
1090 2326b001 Martin Mares
  if (old)
1091 70577529 Ondrej Zajicek
    rte_free_quick(old);
1092 5b22683d Martin Mares
}
1093
1094 e2dc2f30 Martin Mares
static int rte_update_nest_cnt;                /* Nesting counter to allow recursive updates */
1095
1096
static inline void
1097
rte_update_lock(void)
1098
{
1099
  rte_update_nest_cnt++;
1100
}
1101
1102
static inline void
1103
rte_update_unlock(void)
1104
{
1105
  if (!--rte_update_nest_cnt)
1106
    lp_flush(rte_update_pool);
1107
}
1108
1109 fad04c75 Ondrej Zajicek
static inline void
1110
rte_hide_dummy_routes(net *net, rte **dummy)
1111
{
1112
  if (net->routes && net->routes->attrs->source == RTS_DUMMY)
1113
  {
1114
    *dummy = net->routes;
1115
    net->routes = (*dummy)->next;
1116
  }
1117
}
1118
1119
static inline void
1120
rte_unhide_dummy_routes(net *net, rte **dummy)
1121
{
1122
  if (*dummy)
1123
  {
1124
    (*dummy)->next = net->routes;
1125
    net->routes = *dummy;
1126
  }
1127
}
1128
1129 58740ed4 Martin Mares
/**
1130
 * rte_update - enter a new update to a routing table
1131
 * @table: table to be updated
1132 c0adf7e9 Ondrej Zajicek
 * @ah: pointer to table announce hook
1133 58740ed4 Martin Mares
 * @net: network node
1134
 * @p: protocol submitting the update
1135 f98e2915 Ondrej Zajicek
 * @src: protocol originating the update
1136 58740ed4 Martin Mares
 * @new: a &rte representing the new route or %NULL for route removal.
1137
 *
1138
 * This function is called by the routing protocols whenever they discover
1139
 * a new route or wish to update/remove an existing route. The right announcement
1140 2e9b2421 Martin Mares
 * sequence is to build route attributes first (either un-cached with @aflags set
1141 58740ed4 Martin Mares
 * to zero or a cached one using rta_lookup(); in this case please note that
1142
 * you need to increase the use count of the attributes yourself by calling
1143
 * rta_clone()), call rte_get_temp() to obtain a temporary &rte, fill in all
1144
 * the appropriate data and finally submit the new &rte by calling rte_update().
1145
 *
1146 f98e2915 Ondrej Zajicek
 * @src specifies the protocol that originally created the route and the meaning
1147
 * of protocol-dependent data of @new. If @new is not %NULL, @src have to be the
1148
 * same value as @new->attrs->proto. @p specifies the protocol that called
1149
 * rte_update(). In most cases it is the same protocol as @src. rte_update()
1150
 * stores @p in @new->sender;
1151
 *
1152 9a8f20fc Martin Mares
 * When rte_update() gets any route, it automatically validates it (checks,
1153
 * whether the network and next hop address are valid IP addresses and also
1154
 * whether a normal routing protocol doesn't try to smuggle a host or link
1155
 * scope route to the table), converts all protocol dependent attributes stored
1156
 * in the &rte to temporary extended attributes, consults import filters of the
1157
 * protocol to see if the route should be accepted and/or its attributes modified,
1158
 * stores the temporary attributes back to the &rte.
1159
 *
1160
 * Now, having a "public" version of the route, we
1161 f98e2915 Ondrej Zajicek
 * automatically find any old route defined by the protocol @src
1162 58740ed4 Martin Mares
 * for network @n, replace it by the new one (or removing it if @new is %NULL),
1163
 * recalculate the optimal route for this destination and finally broadcast
1164 9a8f20fc Martin Mares
 * the change (if any) to all routing protocols by calling rte_announce().
1165 3ce8c610 Martin Mares
 *
1166
 * All memory used for attribute lists and other temporary allocations is taken
1167
 * from a special linear pool @rte_update_pool and freed when rte_update()
1168
 * finishes.
1169 58740ed4 Martin Mares
 */
1170 23ac9e9a Ondrej Zajicek
1171
void
1172 094d2bdb Ondrej Zajicek
rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
1173 23ac9e9a Ondrej Zajicek
{
1174 c0adf7e9 Ondrej Zajicek
  struct proto *p = ah->proto;
1175
  struct proto_stats *stats = ah->stats;
1176
  struct filter *filter = ah->in_filter;
1177 e2dc2f30 Martin Mares
  ea_list *tmpa = NULL;
1178 fad04c75 Ondrej Zajicek
  rte *dummy = NULL;
1179 e2dc2f30 Martin Mares
1180
  rte_update_lock();
1181
  if (new)
1182
    {
1183 c0adf7e9 Ondrej Zajicek
      new->sender = ah;
1184 40b65f94 Ondrej Zajicek
1185 9db74169 Ondrej Zajicek
      stats->imp_updates_received++;
1186 cfd46ee4 Martin Mares
      if (!rte_validate(new))
1187
        {
1188
          rte_trace_in(D_FILTERS, p, new, "invalid");
1189 9db74169 Ondrej Zajicek
          stats->imp_updates_invalid++;
1190 cfd46ee4 Martin Mares
          goto drop;
1191
        }
1192 cf98be7b Ondrej Zajicek
1193 40b65f94 Ondrej Zajicek
      if (filter == FILTER_REJECT)
1194 cfd46ee4 Martin Mares
        {
1195 9db74169 Ondrej Zajicek
          stats->imp_updates_filtered++;
1196 cfd46ee4 Martin Mares
          rte_trace_in(D_FILTERS, p, new, "filtered out");
1197 094d2bdb Ondrej Zajicek
1198 15550957 Ondrej Zajicek
          if (! ah->in_keep_filtered)
1199 cf98be7b Ondrej Zajicek
            goto drop;
1200
1201
          /* new is a private copy, i could modify it */
1202 15550957 Ondrej Zajicek
          new->flags |= REF_FILTERED;
1203 cfd46ee4 Martin Mares
        }
1204 cf98be7b Ondrej Zajicek
      else
1205 e2dc2f30 Martin Mares
        {
1206 736e143f Ondrej Zajicek
          tmpa = make_tmp_attrs(new, rte_update_pool);
1207 cf98be7b Ondrej Zajicek
          if (filter && (filter != FILTER_REJECT))
1208 cfd46ee4 Martin Mares
            {
1209 cf98be7b Ondrej Zajicek
              ea_list *old_tmpa = tmpa;
1210
              int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
1211
              if (fr > F_ACCEPT)
1212
                {
1213
                  stats->imp_updates_filtered++;
1214
                  rte_trace_in(D_FILTERS, p, new, "filtered out");
1215
1216 15550957 Ondrej Zajicek
                  if (! ah->in_keep_filtered)
1217 cf98be7b Ondrej Zajicek
                    goto drop;
1218
1219 15550957 Ondrej Zajicek
                  new->flags |= REF_FILTERED;
1220 cf98be7b Ondrej Zajicek
                }
1221 736e143f Ondrej Zajicek
              if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
1222
                src->proto->store_tmp_attrs(new, tmpa);
1223 cfd46ee4 Martin Mares
            }
1224 e2dc2f30 Martin Mares
        }
1225 094d2bdb Ondrej Zajicek
      if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
1226 e2dc2f30 Martin Mares
        new->attrs = rta_lookup(new->attrs);
1227
      new->flags |= REF_COW;
1228
    }
1229 925fe2d3 Ondrej Zajicek
  else
1230 094d2bdb Ondrej Zajicek
    {
1231
      stats->imp_withdraws_received++;
1232
1233
      if (!net || !src)
1234
        {
1235
          stats->imp_withdraws_ignored++;
1236
          rte_update_unlock();
1237
          return;
1238
        }
1239
    }
1240 925fe2d3 Ondrej Zajicek
1241 fad04c75 Ondrej Zajicek
 recalc:
1242
  rte_hide_dummy_routes(net, &dummy);
1243 db027a41 Ondrej Zajicek
  rte_recalculate(ah, net, new, src);
1244 fad04c75 Ondrej Zajicek
  rte_unhide_dummy_routes(net, &dummy);
1245 e2dc2f30 Martin Mares
  rte_update_unlock();
1246
  return;
1247
1248 fad04c75 Ondrej Zajicek
 drop:
1249 e2dc2f30 Martin Mares
  rte_free(new);
1250 fad04c75 Ondrej Zajicek
  new = NULL;
1251
  goto recalc;
1252 e2dc2f30 Martin Mares
}
1253
1254 cfe34a31 Ondrej Zajicek
/* Independent call to rte_announce(), used from next hop
1255
   recalculation, outside of rte_update(). new must be non-NULL */
1256
static inline void 
1257 8d9eef17 Ondrej Zajicek
rte_announce_i(rtable *tab, unsigned type, net *net, rte *new, rte *old,
1258
               rte *new_best, rte *old_best)
1259 cfe34a31 Ondrej Zajicek
{
1260
  rte_update_lock();
1261 8d9eef17 Ondrej Zajicek
  rte_announce(tab, type, net, new, old, new_best, old_best, NULL);
1262 cfe34a31 Ondrej Zajicek
  rte_update_unlock();
1263
}
1264
1265 5b22683d Martin Mares
void
1266 0e02abfd Martin Mares
rte_discard(rtable *t, rte *old)        /* Non-filtered route deletion, used during garbage collection */
1267 5b22683d Martin Mares
{
1268 e2dc2f30 Martin Mares
  rte_update_lock();
1269 db027a41 Ondrej Zajicek
  rte_recalculate(old->sender, old->net, NULL, old->attrs->src);
1270 e2dc2f30 Martin Mares
  rte_update_unlock();
1271 2326b001 Martin Mares
}
1272
1273 36da2857 Ondrej Zajicek
/* Check rtable for best route to given net whether it would be exported do p */
1274
int
1275 fe9f1a6d Ondrej Zajicek (work)
rt_examine(rtable *t, net_addr *a, struct proto *p, struct filter *filter)
1276 36da2857 Ondrej Zajicek
{
1277 fe9f1a6d Ondrej Zajicek (work)
  net *n = net_find(t, a);
1278 36da2857 Ondrej Zajicek
  rte *rt = n ? n->routes : NULL;
1279
1280
  if (!rte_is_valid(rt))
1281
    return 0;
1282
1283
  rte_update_lock();
1284
1285
  /* Rest is stripped down export_filter() */
1286 736e143f Ondrej Zajicek
  ea_list *tmpa = make_tmp_attrs(rt, rte_update_pool);
1287 36da2857 Ondrej Zajicek
  int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0;
1288
  if (v == RIC_PROCESS)
1289
    v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
1290
1291
   /* Discard temporary rte */
1292
  if (rt != n->routes)
1293
    rte_free(rt);
1294
1295
  rte_update_unlock();
1296
1297
  return v > 0;
1298
}
1299
1300 6eda3f13 Ondrej Zajicek
1301
/**
1302
 * rt_refresh_begin - start a refresh cycle
1303
 * @t: related routing table
1304
 * @ah: related announce hook 
1305
 *
1306
 * This function starts a refresh cycle for given routing table and announce
1307
 * hook. The refresh cycle is a sequence where the protocol sends all its valid
1308
 * routes to the routing table (by rte_update()). After that, all protocol
1309
 * routes (more precisely routes with @ah as @sender) not sent during the
1310
 * refresh cycle but still in the table from the past are pruned. This is
1311
 * implemented by marking all related routes as stale by REF_STALE flag in
1312
 * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
1313
 * flag in rt_refresh_end() and then removing such routes in the prune loop.
1314
 */
1315 0c791f87 Ondrej Zajicek
void
1316
rt_refresh_begin(rtable *t, struct announce_hook *ah)
1317
{
1318
  net *n;
1319
  rte *e;
1320
1321
  FIB_WALK(&t->fib, fn)
1322
    {
1323
      n = (net *) fn;
1324
      for (e = n->routes; e; e = e->next)
1325
        if (e->sender == ah)
1326
          e->flags |= REF_STALE;
1327
    }
1328
  FIB_WALK_END;
1329
}
1330
1331 6eda3f13 Ondrej Zajicek
/**
1332
 * rt_refresh_end - end a refresh cycle
1333
 * @t: related routing table
1334
 * @ah: related announce hook 
1335
 *
1336
 * This function starts a refresh cycle for given routing table and announce
1337
 * hook. See rt_refresh_begin() for description of refresh cycles.
1338
 */
1339 0c791f87 Ondrej Zajicek
void
1340
rt_refresh_end(rtable *t, struct announce_hook *ah)
1341
{
1342
  int prune = 0;
1343
  net *n;
1344
  rte *e;
1345
1346
  FIB_WALK(&t->fib, fn)
1347
    {
1348
      n = (net *) fn;
1349
      for (e = n->routes; e; e = e->next)
1350
        if ((e->sender == ah) && (e->flags & REF_STALE))
1351
          {
1352
            e->flags |= REF_DISCARD;
1353
            prune = 1;
1354
          }
1355
    }
1356
  FIB_WALK_END;
1357
1358
  if (prune)
1359
    rt_schedule_prune(t);
1360
}
1361
1362
1363 58740ed4 Martin Mares
/**
1364
 * rte_dump - dump a route
1365
 * @e: &rte to be dumped
1366
 *
1367
 * This functions dumps contents of a &rte to debug output.
1368
 */
1369 2326b001 Martin Mares
void
1370 a0762910 Martin Mares
rte_dump(rte *e)
1371 2326b001 Martin Mares
{
1372 a0762910 Martin Mares
  net *n = e->net;
1373 fe9f1a6d Ondrej Zajicek (work)
  debug("%-1N ", n->n.addr);
1374 c10421d3 Martin Mares
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
1375 0cdbd397 Martin Mares
  rta_dump(e->attrs);
1376 094d2bdb Ondrej Zajicek
  if (e->attrs->src->proto->proto->dump_attrs)
1377
    e->attrs->src->proto->proto->dump_attrs(e);
1378 0cdbd397 Martin Mares
  debug("\n");
1379 2326b001 Martin Mares
}
1380 62aa008a Martin Mares
1381 58740ed4 Martin Mares
/**
1382
 * rt_dump - dump a routing table
1383
 * @t: routing table to be dumped
1384
 *
1385
 * This function dumps contents of a given routing table to debug output.
1386
 */
1387 2326b001 Martin Mares
void
1388
rt_dump(rtable *t)
1389
{
1390 0cdbd397 Martin Mares
  rte *e;
1391
  net *n;
1392 0e02abfd Martin Mares
  struct announce_hook *a;
1393 0cdbd397 Martin Mares
1394
  debug("Dump of routing table <%s>\n", t->name);
1395 e440395d Martin Mares
#ifdef DEBUGGING
1396 08e2d625 Martin Mares
  fib_check(&t->fib);
1397 e440395d Martin Mares
#endif
1398 08e2d625 Martin Mares
  FIB_WALK(&t->fib, fn)
1399
    {
1400
      n = (net *) fn;
1401
      for(e=n->routes; e; e=e->next)
1402
        rte_dump(e);
1403 0cdbd397 Martin Mares
    }
1404 08e2d625 Martin Mares
  FIB_WALK_END;
1405 0e02abfd Martin Mares
  WALK_LIST(a, t->hooks)
1406
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
1407 0cdbd397 Martin Mares
  debug("\n");
1408 2326b001 Martin Mares
}
1409 62aa008a Martin Mares
1410 58740ed4 Martin Mares
/**
1411
 * rt_dump_all - dump all routing tables
1412
 *
1413
 * This function dumps contents of all routing tables to debug output.
1414
 */
1415 2326b001 Martin Mares
void
1416 6d45cf21 Martin Mares
rt_dump_all(void)
1417
{
1418 0e02abfd Martin Mares
  rtable *t;
1419
1420
  WALK_LIST(t, routing_tables)
1421
    rt_dump(t);
1422 6d45cf21 Martin Mares
}
1423
1424 cfe34a31 Ondrej Zajicek
static inline void
1425 0c791f87 Ondrej Zajicek
rt_schedule_prune(rtable *tab)
1426
{
1427
  rt_mark_for_prune(tab);
1428
  ev_schedule(tab->rt_event);
1429
}
1430
1431
static inline void
1432 cfe34a31 Ondrej Zajicek
rt_schedule_gc(rtable *tab)
1433
{
1434
  if (tab->gc_scheduled)
1435
    return;
1436
1437
  tab->gc_scheduled = 1;
1438
  ev_schedule(tab->rt_event);
1439
}
1440
1441
static inline void
1442
rt_schedule_hcu(rtable *tab)
1443
{
1444
  if (tab->hcu_scheduled)
1445
    return;
1446
1447
  tab->hcu_scheduled = 1;
1448
  ev_schedule(tab->rt_event);
1449
}
1450
1451
static inline void
1452
rt_schedule_nhu(rtable *tab)
1453
{
1454
  if (tab->nhu_state == 0)
1455
    ev_schedule(tab->rt_event);
1456
1457
  /* state change 0->1, 2->3 */
1458
  tab->nhu_state |= 1;
1459
}
1460
1461 0c791f87 Ondrej Zajicek
1462 8f6accb5 Martin Mares
static void
1463 fb829de6 Ondrej Zajicek
rt_prune_nets(rtable *tab)
1464
{
1465
  struct fib_iterator fit;
1466
  int ncnt = 0, ndel = 0;
1467
1468
#ifdef DEBUGGING
1469
  fib_check(&tab->fib);
1470
#endif
1471
1472
  FIB_ITERATE_INIT(&fit, &tab->fib);
1473
again:
1474
  FIB_ITERATE_START(&tab->fib, &fit, f)
1475
    {
1476
      net *n = (net *) f;
1477
      ncnt++;
1478
      if (!n->routes)                /* Orphaned FIB entry */
1479
        {
1480
          FIB_ITERATE_PUT(&fit, f);
1481
          fib_delete(&tab->fib, f);
1482
          ndel++;
1483
          goto again;
1484
        }
1485
    }
1486
  FIB_ITERATE_END(f);
1487
  DBG("Pruned %d of %d networks\n", ndel, ncnt);
1488
1489
  tab->gc_counter = 0;
1490
  tab->gc_time = now;
1491
  tab->gc_scheduled = 0;
1492
}
1493
1494
static void
1495 cfe34a31 Ondrej Zajicek
rt_event(void *ptr)
1496 5996da6a Martin Mares
{
1497 cfe34a31 Ondrej Zajicek
  rtable *tab = ptr;
1498
1499
  if (tab->hcu_scheduled)
1500
    rt_update_hostcache(tab);
1501 0e02abfd Martin Mares
1502 cfe34a31 Ondrej Zajicek
  if (tab->nhu_state)
1503
    rt_next_hop_update(tab);
1504
1505 0c791f87 Ondrej Zajicek
  if (tab->prune_state)
1506
    if (!rt_prune_table(tab))
1507
      {
1508
        /* Table prune unfinished */
1509
        ev_schedule(tab->rt_event);
1510
        return;
1511
      }
1512
1513 cfe34a31 Ondrej Zajicek
  if (tab->gc_scheduled)
1514 094d2bdb Ondrej Zajicek
    {
1515
      rt_prune_nets(tab);
1516
      rt_prune_sources(); // FIXME this should be moved to independent event
1517
    }
1518 5996da6a Martin Mares
}
1519
1520 6d45cf21 Martin Mares
void
1521 b9626ec6 Martin Mares
rt_setup(pool *p, rtable *t, char *name, struct rtable_config *cf)
1522
{
1523
  bzero(t, sizeof(*t));
1524
  t->name = name;
1525
  t->config = cf;
1526 fe9f1a6d Ondrej Zajicek (work)
  t->addr_type = cf ? cf->addr_type : NET_IP4;
1527
  fib_init(&t->fib, p, t->addr_type, sizeof(net), OFFSETOF(net, n), 0, NULL);
1528 b9626ec6 Martin Mares
  init_list(&t->hooks);
1529
  if (cf)
1530
    {
1531 cfe34a31 Ondrej Zajicek
      t->rt_event = ev_new(p);
1532
      t->rt_event->hook = rt_event;
1533
      t->rt_event->data = t;
1534 2eca3b3a Martin Mares
      t->gc_time = now;
1535 b9626ec6 Martin Mares
    }
1536
}
1537
1538 58740ed4 Martin Mares
/**
1539
 * rt_init - initialize routing tables
1540
 *
1541
 * This function is called during BIRD startup. It initializes the
1542
 * routing table module.
1543
 */
1544 b9626ec6 Martin Mares
void
1545 2326b001 Martin Mares
rt_init(void)
1546
{
1547
  rta_init();
1548 5996da6a Martin Mares
  rt_table_pool = rp_new(&root_pool, "Routing tables");
1549 e2dc2f30 Martin Mares
  rte_update_pool = lp_new(rt_table_pool, 4080);
1550 5996da6a Martin Mares
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
1551 0e02abfd Martin Mares
  init_list(&routing_tables);
1552 2326b001 Martin Mares
}
1553 1a54b1c6 Martin Mares
1554 fb829de6 Ondrej Zajicek
1555 0c791f87 Ondrej Zajicek
static int
1556 d0e23d42 Ondrej Zajicek
rt_prune_step(rtable *tab, int *limit)
1557 fb829de6 Ondrej Zajicek
{
1558
  struct fib_iterator *fit = &tab->prune_fit;
1559 1a54b1c6 Martin Mares
1560
  DBG("Pruning route table %s\n", tab->name);
1561 0521e4f6 Martin Mares
#ifdef DEBUGGING
1562
  fib_check(&tab->fib);
1563
#endif
1564 fb829de6 Ondrej Zajicek
1565 0c791f87 Ondrej Zajicek
  if (tab->prune_state == RPS_NONE)
1566 fb829de6 Ondrej Zajicek
    return 1;
1567
1568 0c791f87 Ondrej Zajicek
  if (tab->prune_state == RPS_SCHEDULED)
1569 fb829de6 Ondrej Zajicek
    {
1570
      FIB_ITERATE_INIT(fit, &tab->fib);
1571 0c791f87 Ondrej Zajicek
      tab->prune_state = RPS_RUNNING;
1572 fb829de6 Ondrej Zajicek
    }
1573
1574 08e2d625 Martin Mares
again:
1575 fb829de6 Ondrej Zajicek
  FIB_ITERATE_START(&tab->fib, fit, fn)
1576 1a54b1c6 Martin Mares
    {
1577 fb829de6 Ondrej Zajicek
      net *n = (net *) fn;
1578 08e2d625 Martin Mares
      rte *e;
1579 fb829de6 Ondrej Zajicek
1580 08e2d625 Martin Mares
    rescan:
1581 fb829de6 Ondrej Zajicek
      for (e=n->routes; e; e=e->next)
1582 d0e23d42 Ondrej Zajicek
        if (e->sender->proto->flushing || (e->flags & REF_DISCARD))
1583 08e2d625 Martin Mares
          {
1584 0c791f87 Ondrej Zajicek
            if (*limit <= 0)
1585 fb829de6 Ondrej Zajicek
              {
1586
                FIB_ITERATE_PUT(fit, fn);
1587
                return 0;
1588
              }
1589
1590 0e02abfd Martin Mares
            rte_discard(tab, e);
1591 0c791f87 Ondrej Zajicek
            (*limit)--;
1592 fb829de6 Ondrej Zajicek
1593 08e2d625 Martin Mares
            goto rescan;
1594
          }
1595 fb829de6 Ondrej Zajicek
      if (!n->routes)                /* Orphaned FIB entry */
1596 1a54b1c6 Martin Mares
        {
1597 fb829de6 Ondrej Zajicek
          FIB_ITERATE_PUT(fit, fn);
1598
          fib_delete(&tab->fib, fn);
1599 08e2d625 Martin Mares
          goto again;
1600 1a54b1c6 Martin Mares
        }
1601
    }
1602 fb829de6 Ondrej Zajicek
  FIB_ITERATE_END(fn);
1603
1604 0521e4f6 Martin Mares
#ifdef DEBUGGING
1605
  fib_check(&tab->fib);
1606
#endif
1607 fb829de6 Ondrej Zajicek
1608 0c791f87 Ondrej Zajicek
  tab->prune_state = RPS_NONE;
1609 fb829de6 Ondrej Zajicek
  return 1;
1610 1a54b1c6 Martin Mares
}
1611 0e02abfd Martin Mares
1612 6eda3f13 Ondrej Zajicek
/**
1613
 * rt_prune_table - prune a routing table
1614
 *
1615
 * This function scans the routing table @tab and removes routes belonging to
1616
 * flushing protocols, discarded routes and also stale network entries, in a
1617
 * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
1618
 * pruned. Contrary to rt_prune_loop(), this function is not a part of the
1619
 * protocol flushing loop, but it is called from rt_event() for just one routing
1620
 * table.
1621
 *
1622
 * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
1623
 * prune state (@prune_state) and also the pruning iterator (@prune_fit).
1624
 */
1625 0c791f87 Ondrej Zajicek
static inline int
1626
rt_prune_table(rtable *tab)
1627
{
1628
  int limit = 512;
1629 d0e23d42 Ondrej Zajicek
  return rt_prune_step(tab, &limit);
1630 0c791f87 Ondrej Zajicek
}
1631
1632 58740ed4 Martin Mares
/**
1633 fb829de6 Ondrej Zajicek
 * rt_prune_loop - prune routing tables
1634 58740ed4 Martin Mares
 *
1635 6eda3f13 Ondrej Zajicek
 * The prune loop scans routing tables and removes routes belonging to flushing
1636
 * protocols, discarded routes and also stale network entries. Returns 1 when
1637
 * all such routes are pruned. It is a part of the protocol flushing loop.
1638 58740ed4 Martin Mares
 */
1639 fb829de6 Ondrej Zajicek
int
1640
rt_prune_loop(void)
1641 0e02abfd Martin Mares
{
1642 0c791f87 Ondrej Zajicek
  int limit = 512;
1643 9135c1f0 Ondrej Zajicek
  rtable *t;
1644 0e02abfd Martin Mares
1645
  WALK_LIST(t, routing_tables)
1646 d0e23d42 Ondrej Zajicek
    if (! rt_prune_step(t, &limit))
1647 fb829de6 Ondrej Zajicek
      return 0;
1648
1649
  return 1;
1650 0e02abfd Martin Mares
}
1651
1652 cfe34a31 Ondrej Zajicek
void
1653
rt_preconfig(struct config *c)
1654
{
1655 9b9a7143 Ondrej Zajicek (work)
  struct symbol *s = cf_get_symbol("master");
1656 cfe34a31 Ondrej Zajicek
1657
  init_list(&c->tables);
1658 fe9f1a6d Ondrej Zajicek (work)
  c->master_rtc = rt_new_table(s, NET_IP4);
1659 cfe34a31 Ondrej Zajicek
}
1660
1661
1662
/* 
1663
 * Some functions for handing internal next hop updates
1664
 * triggered by rt_schedule_nhu().
1665
 */
1666
1667
static inline int
1668
rta_next_hop_outdated(rta *a)
1669
{
1670
  struct hostentry *he = a->hostentry;
1671 7e95c05d Ondrej Zajicek
1672
  if (!he)
1673
    return 0;
1674
1675
  if (!he->src)
1676
    return a->dest != RTD_UNREACHABLE;
1677
1678
  return (a->iface != he->src->iface) || !ipa_equal(a->gw, he->gw) ||
1679
    (a->dest != he->dest) || (a->igp_metric != he->igp_metric) ||
1680
    !mpnh_same(a->nexthops, he->src->nexthops);
1681 cfe34a31 Ondrej Zajicek
}
1682
1683
static inline void
1684
rta_apply_hostentry(rta *a, struct hostentry *he)
1685
{
1686
  a->hostentry = he;
1687 7e95c05d Ondrej Zajicek
  a->iface = he->src ? he->src->iface : NULL;
1688 cfe34a31 Ondrej Zajicek
  a->gw = he->gw;
1689
  a->dest = he->dest;
1690 d1e146f2 Ondrej Zajicek
  a->igp_metric = he->igp_metric;
1691 7e95c05d Ondrej Zajicek
  a->nexthops = he->src ? he->src->nexthops : NULL;
1692 cfe34a31 Ondrej Zajicek
}
1693
1694
static inline rte *
1695
rt_next_hop_update_rte(rtable *tab, rte *old)
1696
{
1697
  rta a;
1698
  memcpy(&a, old->attrs, sizeof(rta));
1699
  rta_apply_hostentry(&a, old->attrs->hostentry);
1700
  a.aflags = 0;
1701
1702
  rte *e = sl_alloc(rte_slab);
1703
  memcpy(e, old, sizeof(rte));
1704
  e->attrs = rta_lookup(&a);
1705
1706
  return e;
1707
}
1708
1709
static inline int
1710
rt_next_hop_update_net(rtable *tab, net *n)
1711
{
1712
  rte **k, *e, *new, *old_best, **new_best;
1713
  int count = 0;
1714
  int free_old_best = 0;
1715
1716
  old_best = n->routes;
1717
  if (!old_best)
1718
    return 0;
1719
1720
  for (k = &n->routes; e = *k; k = &e->next)
1721 be4cd99a Ondrej Zajicek
    if (rta_next_hop_outdated(e->attrs))
1722
      {
1723
        new = rt_next_hop_update_rte(tab, e);
1724
        *k = new;
1725 cfe34a31 Ondrej Zajicek
1726 8d9eef17 Ondrej Zajicek
        rte_announce_i(tab, RA_ANY, n, new, e, NULL, NULL);
1727 c0adf7e9 Ondrej Zajicek
        rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
1728 cfe34a31 Ondrej Zajicek
1729 be4cd99a Ondrej Zajicek
        /* Call a pre-comparison hook */
1730
        /* Not really an efficient way to compute this */
1731 094d2bdb Ondrej Zajicek
        if (e->attrs->src->proto->rte_recalculate)
1732
          e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
1733 cfe34a31 Ondrej Zajicek
1734 be4cd99a Ondrej Zajicek
        if (e != old_best)
1735
          rte_free_quick(e);
1736
        else /* Freeing of the old best rte is postponed */
1737
          free_old_best = 1;
1738 cfe34a31 Ondrej Zajicek
1739 be4cd99a Ondrej Zajicek
        e = new;
1740
        count++;
1741
      }
1742
1743
  if (!count)
1744
    return 0;
1745
1746
  /* Find the new best route */
1747
  new_best = NULL;
1748
  for (k = &n->routes; e = *k; k = &e->next)
1749
    {
1750 cfe34a31 Ondrej Zajicek
      if (!new_best || rte_better(e, *new_best))
1751
        new_best = k;
1752
    }
1753
1754
  /* Relink the new best route to the first position */
1755
  new = *new_best;
1756
  if (new != n->routes)
1757
    {
1758
      *new_best = new->next;
1759
      new->next = n->routes;
1760
      n->routes = new;
1761
    }
1762
1763
  /* Announce the new best route */
1764
  if (new != old_best)
1765
    {
1766 8d9eef17 Ondrej Zajicek
      rte_announce_i(tab, RA_OPTIMAL, n, new, old_best, NULL, NULL);
1767 c0adf7e9 Ondrej Zajicek
      rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
1768 cfe34a31 Ondrej Zajicek
    }
1769
1770 8d9eef17 Ondrej Zajicek
  /* FIXME: Better announcement of merged routes */
1771
  rte_announce_i(tab, RA_MERGED, n, new, old_best, new, old_best);
1772
1773 cfe34a31 Ondrej Zajicek
   if (free_old_best)
1774
    rte_free_quick(old_best);
1775
1776
  return count;
1777
}
1778
1779
static void
1780
rt_next_hop_update(rtable *tab)
1781
{
1782
  struct fib_iterator *fit = &tab->nhu_fit;
1783
  int max_feed = 32;
1784
1785
  if (tab->nhu_state == 0)
1786
    return;
1787
1788
  if (tab->nhu_state == 1)
1789
    {
1790
      FIB_ITERATE_INIT(fit, &tab->fib);
1791
      tab->nhu_state = 2;
1792
    }
1793
1794
  FIB_ITERATE_START(&tab->fib, fit, fn)
1795
    {
1796
      if (max_feed <= 0)
1797
        {
1798
          FIB_ITERATE_PUT(fit, fn);
1799
          ev_schedule(tab->rt_event);
1800
          return;
1801
        }
1802
      max_feed -= rt_next_hop_update_net(tab, (net *) fn);
1803
    }
1804
  FIB_ITERATE_END(fn);
1805
1806
  /* state change 2->0, 3->1 */
1807
  tab->nhu_state &= 1;
1808
1809
  if (tab->nhu_state > 0)
1810
    ev_schedule(tab->rt_event);
1811
}
1812
1813
1814 b9626ec6 Martin Mares
struct rtable_config *
1815 fe9f1a6d Ondrej Zajicek (work)
rt_new_table(struct symbol *s, uint addr_type)
1816 b9626ec6 Martin Mares
{
1817 36415e4b Ondrej Zajicek
  /* Hack that allows to 'redefine' the master table */
1818
  if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc))
1819
    return s->def;
1820
1821 b9626ec6 Martin Mares
  struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
1822
1823
  cf_define_symbol(s, SYM_TABLE, c);
1824
  c->name = s->name;
1825 fe9f1a6d Ondrej Zajicek (work)
  c->addr_type = addr_type;
1826 b9626ec6 Martin Mares
  add_tail(&new_config->tables, &c->n);
1827 2eca3b3a Martin Mares
  c->gc_max_ops = 1000;
1828 b9626ec6 Martin Mares
  c->gc_min_time = 5;
1829
  return c;
1830
}
1831
1832 58740ed4 Martin Mares
/**
1833
 * rt_lock_table - lock a routing table
1834
 * @r: routing table to be locked
1835
 *
1836
 * Lock a routing table, because it's in use by a protocol,
1837
 * preventing it from being freed when it gets undefined in a new
1838
 * configuration.
1839
 */
1840 0e02abfd Martin Mares
void
1841 50fe90ed Martin Mares
rt_lock_table(rtable *r)
1842 0e02abfd Martin Mares
{
1843 50fe90ed Martin Mares
  r->use_count++;
1844
}
1845
1846 58740ed4 Martin Mares
/**
1847
 * rt_unlock_table - unlock a routing table
1848
 * @r: routing table to be unlocked
1849
 *
1850
 * Unlock a routing table formerly locked by rt_lock_table(),
1851
 * that is decrease its use count and delete it if it's scheduled
1852
 * for deletion by configuration changes.
1853
 */
1854 50fe90ed Martin Mares
void
1855
rt_unlock_table(rtable *r)
1856
{
1857
  if (!--r->use_count && r->deleted)
1858
    {
1859
      struct config *conf = r->deleted;
1860
      DBG("Deleting routing table %s\n", r->name);
1861 86b4e170 Ondrej Zajicek (work)
      r->config->table = NULL;
1862 cfe34a31 Ondrej Zajicek
      if (r->hostcache)
1863
        rt_free_hostcache(r);
1864 50fe90ed Martin Mares
      rem_node(&r->n);
1865
      fib_free(&r->fib);
1866 cfe34a31 Ondrej Zajicek
      rfree(r->rt_event);
1867 50fe90ed Martin Mares
      mb_free(r);
1868
      config_del_obstacle(conf);
1869
    }
1870
}
1871
1872 58740ed4 Martin Mares
/**
1873
 * rt_commit - commit new routing table configuration
1874
 * @new: new configuration
1875
 * @old: original configuration or %NULL if it's boot time config
1876
 *
1877
 * Scan differences between @old and @new configuration and modify
1878
 * the routing tables according to these changes. If @new defines a
1879
 * previously unknown table, create it, if it omits a table existing
1880
 * in @old, schedule it for deletion (it gets deleted when all protocols
1881
 * disconnect from it by calling rt_unlock_table()), if it exists
1882
 * in both configurations, leave it unchanged.
1883
 */
1884 50fe90ed Martin Mares
void
1885
rt_commit(struct config *new, struct config *old)
1886
{
1887
  struct rtable_config *o, *r;
1888 0e02abfd Martin Mares
1889 50fe90ed Martin Mares
  DBG("rt_commit:\n");
1890
  if (old)
1891 0e02abfd Martin Mares
    {
1892 50fe90ed Martin Mares
      WALK_LIST(o, old->tables)
1893
        {
1894
          rtable *ot = o->table;
1895
          if (!ot->deleted)
1896
            {
1897 9b9a7143 Ondrej Zajicek (work)
              struct symbol *sym = cf_find_symbol(new, o->name);
1898 bf8558bc Martin Mares
              if (sym && sym->class == SYM_TABLE && !new->shutdown)
1899 50fe90ed Martin Mares
                {
1900
                  DBG("\t%s: same\n", o->name);
1901
                  r = sym->def;
1902
                  r->table = ot;
1903
                  ot->name = r->name;
1904 b9626ec6 Martin Mares
                  ot->config = r;
1905 26822d8f Ondrej Zajicek
                  if (o->sorted != r->sorted)
1906
                    log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
1907 50fe90ed Martin Mares
                }
1908
              else
1909
                {
1910 bf8558bc Martin Mares
                  DBG("\t%s: deleted\n", o->name);
1911 50fe90ed Martin Mares
                  ot->deleted = old;
1912
                  config_add_obstacle(old);
1913
                  rt_lock_table(ot);
1914
                  rt_unlock_table(ot);
1915
                }
1916
            }
1917
        }
1918 0e02abfd Martin Mares
    }
1919 50fe90ed Martin Mares
1920
  WALK_LIST(r, new->tables)
1921
    if (!r->table)
1922
      {
1923
        rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
1924
        DBG("\t%s: created\n", r->name);
1925 b9626ec6 Martin Mares
        rt_setup(rt_table_pool, t, r->name, r);
1926 50fe90ed Martin Mares
        add_tail(&routing_tables, &t->n);
1927
        r->table = t;
1928
      }
1929
  DBG("\tdone\n");
1930 0e02abfd Martin Mares
}
1931 730f2e2c Martin Mares
1932 23ac9e9a Ondrej Zajicek
static inline void
1933
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
1934
{
1935
  rte_update_lock();
1936 00a09f3c Ondrej Zajicek
  if (type == RA_ACCEPTED)
1937 db027a41 Ondrej Zajicek
    rt_notify_accepted(h, n, e, NULL, NULL, p->refeeding ? 2 : 1);
1938 8d9eef17 Ondrej Zajicek
  else if (type == RA_MERGED)
1939
    rt_notify_merged(h, n, NULL, NULL, e, p->refeeding ? e : NULL, p->refeeding);
1940 00a09f3c Ondrej Zajicek
  else
1941 db027a41 Ondrej Zajicek
    rt_notify_basic(h, n, e, p->refeeding ? e : NULL, p->refeeding);
1942 23ac9e9a Ondrej Zajicek
  rte_update_unlock();
1943
}
1944
1945 58740ed4 Martin Mares
/**
1946
 * rt_feed_baby - advertise routes to a new protocol
1947
 * @p: protocol to be fed
1948
 *
1949
 * This function performs one pass of advertisement of routes to a newly
1950
 * initialized protocol. It's called by the protocol code as long as it
1951
 * has something to do. (We avoid transferring all the routes in single
1952
 * pass in order not to monopolize CPU time.)
1953
 */
1954 ac5d8012 Martin Mares
int
1955
rt_feed_baby(struct proto *p)
1956
{
1957
  struct announce_hook *h;
1958
  struct fib_iterator *fit;
1959 76dfda9e Martin Mares
  int max_feed = 256;
1960 ac5d8012 Martin Mares
1961
  if (!p->feed_ahook)                        /* Need to initialize first */
1962
    {
1963
      if (!p->ahooks)
1964
        return 1;
1965
      DBG("Announcing routes to new protocol %s\n", p->name);
1966
      p->feed_ahook = p->ahooks;
1967
      fit = p->feed_iterator = mb_alloc(p->pool, sizeof(struct fib_iterator));
1968
      goto next_hook;
1969
    }
1970
  fit = p->feed_iterator;
1971
1972
again:
1973
  h = p->feed_ahook;
1974
  FIB_ITERATE_START(&h->table->fib, fit, fn)
1975
    {
1976
      net *n = (net *) fn;
1977 258d0ad4 Ondrej Zajicek
      rte *e = n->routes;
1978 76dfda9e Martin Mares
      if (max_feed <= 0)
1979
        {
1980
          FIB_ITERATE_PUT(fit, fn);
1981
          return 0;
1982
        }
1983 23ac9e9a Ondrej Zajicek
1984 cf98be7b Ondrej Zajicek
      /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
1985
1986 b7f3df79 Ondrej Zajicek
      if ((p->accept_ra_types == RA_OPTIMAL) ||
1987 8d9eef17 Ondrej Zajicek
          (p->accept_ra_types == RA_ACCEPTED) ||
1988
          (p->accept_ra_types == RA_MERGED))
1989 cf98be7b Ondrej Zajicek
        if (rte_is_valid(e))
1990 23ac9e9a Ondrej Zajicek
          {
1991 0c791f87 Ondrej Zajicek
            if (p->export_state != ES_FEEDING)
1992 23ac9e9a Ondrej Zajicek
              return 1;  /* In the meantime, the protocol fell down. */
1993 ca34698c Ondrej Zajicek
1994 b7f3df79 Ondrej Zajicek
            do_feed_baby(p, p->accept_ra_types, h, n, e);
1995 23ac9e9a Ondrej Zajicek
            max_feed--;
1996
          }
1997
1998
      if (p->accept_ra_types == RA_ANY)
1999 ca34698c Ondrej Zajicek
        for(e = n->routes; e; e = e->next)
2000 23ac9e9a Ondrej Zajicek
          {
2001 0c791f87 Ondrej Zajicek
            if (p->export_state != ES_FEEDING)
2002 23ac9e9a Ondrej Zajicek
              return 1;  /* In the meantime, the protocol fell down. */
2003 ca34698c Ondrej Zajicek
2004
            if (!rte_is_valid(e))
2005
              continue;
2006
2007 23ac9e9a Ondrej Zajicek
            do_feed_baby(p, RA_ANY, h, n, e);
2008
            max_feed--;
2009
          }
2010 ac5d8012 Martin Mares
    }
2011
  FIB_ITERATE_END(fn);
2012
  p->feed_ahook = h->next;
2013
  if (!p->feed_ahook)
2014
    {
2015
      mb_free(p->feed_iterator);
2016
      p->feed_iterator = NULL;
2017
      return 1;
2018
    }
2019
2020
next_hook:
2021
  h = p->feed_ahook;
2022
  FIB_ITERATE_INIT(fit, &h->table->fib);
2023
  goto again;
2024
}
2025
2026 58740ed4 Martin Mares
/**
2027
 * rt_feed_baby_abort - abort protocol feeding
2028
 * @p: protocol
2029
 *
2030
 * This function is called by the protocol code when the protocol
2031
 * stops or ceases to exist before the last iteration of rt_feed_baby()
2032
 * has finished.
2033
 */
2034 ac5d8012 Martin Mares
void
2035
rt_feed_baby_abort(struct proto *p)
2036
{
2037
  if (p->feed_ahook)
2038
    {
2039
      /* Unlink the iterator and exit */
2040
      fit_get(&p->feed_ahook->table->fib, p->feed_iterator);
2041
      p->feed_ahook = NULL;
2042
    }
2043
}
2044
2045 f2b76f2c Ondrej Zajicek
2046
static inline unsigned
2047
ptr_hash(void *ptr)
2048
{
2049
  uintptr_t p = (uintptr_t) ptr;
2050
  return p ^ (p << 8) ^ (p >> 16);
2051
}
2052
2053
static inline unsigned
2054
hc_hash(ip_addr a, rtable *dep)
2055
{
2056
  return (ipa_hash(a) ^ ptr_hash(dep)) & 0xffff;
2057
}
2058
2059
static inline void
2060
hc_insert(struct hostcache *hc, struct hostentry *he)
2061
{
2062 ae80a2de Pavel Tvrdík
  uint k = he->hash_key >> hc->hash_shift;
2063 f2b76f2c Ondrej Zajicek
  he->next = hc->hash_table[k];
2064
  hc->hash_table[k] = he;
2065
}
2066
2067
static inline void
2068
hc_remove(struct hostcache *hc, struct hostentry *he)
2069
{
2070
  struct hostentry **hep;
2071 ae80a2de Pavel Tvrdík
  uint k = he->hash_key >> hc->hash_shift;
2072 f2b76f2c Ondrej Zajicek
2073
  for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
2074
  *hep = he->next;
2075
}
2076
2077
#define HC_DEF_ORDER 10
2078
#define HC_HI_MARK *4
2079
#define HC_HI_STEP 2
2080
#define HC_HI_ORDER 16                        /* Must be at most 16 */
2081
#define HC_LO_MARK /5
2082
#define HC_LO_STEP 2
2083
#define HC_LO_ORDER 10
2084
2085
static void
2086
hc_alloc_table(struct hostcache *hc, unsigned order)
2087
{
2088
  unsigned hsize = 1 << order;
2089
  hc->hash_order = order;
2090
  hc->hash_shift = 16 - order;
2091
  hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
2092
  hc->hash_min = (order <= HC_LO_ORDER) ?  0 : (hsize HC_LO_MARK);
2093
2094
  hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
2095
}
2096
2097 cfe34a31 Ondrej Zajicek
static void
2098 f2b76f2c Ondrej Zajicek
hc_resize(struct hostcache *hc, unsigned new_order)
2099 cfe34a31 Ondrej Zajicek
{
2100 f2b76f2c Ondrej Zajicek
  unsigned old_size = 1 << hc->hash_order;
2101
  struct hostentry **old_table = hc->hash_table;
2102
  struct hostentry *he, *hen;
2103
  int i;
2104
2105
  hc_alloc_table(hc, new_order);
2106
  for (i = 0; i < old_size; i++)
2107
    for (he = old_table[i]; he != NULL; he=hen)
2108
      {
2109
        hen = he->next;
2110
        hc_insert(hc, he);
2111
      }
2112
  mb_free(old_table);
2113
}
2114
2115
static struct hostentry *
2116 1b180121 Ondrej Zajicek
hc_new_hostentry(struct hostcache *hc, ip_addr a, ip_addr ll, rtable *dep, unsigned k)
2117 f2b76f2c Ondrej Zajicek
{
2118
  struct hostentry *he = sl_alloc(hc->slab);
2119
2120
  he->addr = a;
2121 1b180121 Ondrej Zajicek
  he->link = ll;
2122 f2b76f2c Ondrej Zajicek
  he->tab = dep;
2123
  he->hash_key = k;
2124
  he->uc = 0;
2125 7e95c05d Ondrej Zajicek
  he->src = NULL;
2126 f2b76f2c Ondrej Zajicek
2127
  add_tail(&hc->hostentries, &he->ln);
2128
  hc_insert(hc, he);
2129
2130
  hc->hash_items++;
2131
  if (hc->hash_items > hc->hash_max)
2132
    hc_resize(hc, hc->hash_order + HC_HI_STEP);
2133
2134
  return he;
2135
}
2136
2137
static void
2138
hc_delete_hostentry(struct hostcache *hc, struct hostentry *he)
2139
{
2140 7e95c05d Ondrej Zajicek
  rta_free(he->src);
2141
2142 f2b76f2c Ondrej Zajicek
  rem_node(&he->ln);
2143
  hc_remove(hc, he);
2144
  sl_free(hc->slab, he);
2145
2146
  hc->hash_items--;
2147
  if (hc->hash_items < hc->hash_min)
2148
    hc_resize(hc, hc->hash_order - HC_LO_STEP);
2149 cfe34a31 Ondrej Zajicek
}
2150
2151
static void
2152
rt_init_hostcache(rtable *tab)
2153
{
2154
  struct hostcache *hc = mb_allocz(rt_table_pool, sizeof(struct hostcache));
2155
  init_list(&hc->hostentries);
2156 f2b76f2c Ondrej Zajicek
2157
  hc->hash_items = 0;
2158
  hc_alloc_table(hc, HC_DEF_ORDER);
2159
  hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
2160
2161 c477f489 Ondrej Zajicek
  hc->lp = lp_new(rt_table_pool, 1008);
2162 51762a45 Ondrej Zajicek
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2163 c477f489 Ondrej Zajicek
2164 cfe34a31 Ondrej Zajicek
  tab->hostcache = hc;
2165
}
2166
2167
static void
2168
rt_free_hostcache(rtable *tab)
2169
{
2170
  struct hostcache *hc = tab->hostcache;
2171
2172
  node *n;
2173
  WALK_LIST(n, hc->hostentries)
2174
    {
2175
      struct hostentry *he = SKIP_BACK(struct hostentry, ln, n);
2176 7e95c05d Ondrej Zajicek
      rta_free(he->src);
2177
2178 cfe34a31 Ondrej Zajicek
      if (he->uc)
2179
        log(L_ERR "Hostcache is not empty in table %s", tab->name);
2180
    }
2181
2182 f2b76f2c Ondrej Zajicek
  rfree(hc->slab);
2183 c477f489 Ondrej Zajicek
  rfree(hc->lp);
2184 f2b76f2c Ondrej Zajicek
  mb_free(hc->hash_table);
2185 cfe34a31 Ondrej Zajicek
  mb_free(hc);
2186
}
2187
2188
static void
2189
rt_notify_hostcache(rtable *tab, net *net)
2190
{
2191
  struct hostcache *hc = tab->hostcache;
2192
2193
  if (tab->hcu_scheduled)
2194
    return;
2195
2196 fe9f1a6d Ondrej Zajicek (work)
  // XXXX
2197
  // if (trie_match_prefix(hc->trie, net->n.prefix, net->n.pxlen))
2198
  // rt_schedule_hcu(tab);
2199 cfe34a31 Ondrej Zajicek
}
2200
2201
static int
2202
if_local_addr(ip_addr a, struct iface *i)
2203
{
2204
  struct ifa *b;
2205
2206
  WALK_LIST(b, i->addrs)
2207
    if (ipa_equal(a, b->ip))
2208
      return 1;
2209
2210
  return 0;
2211
}
2212
2213 d1e146f2 Ondrej Zajicek
static u32 
2214
rt_get_igp_metric(rte *rt)
2215
{
2216 ba5e5940 Ondrej Zajicek
  eattr *ea = ea_find(rt->attrs->eattrs, EA_GEN_IGP_METRIC);
2217
2218
  if (ea)
2219
    return ea->u.data;
2220
2221 d1e146f2 Ondrej Zajicek
  rta *a = rt->attrs;
2222 b7c48981 Ondrej Filip
2223
#ifdef CONFIG_OSPF
2224 d1e146f2 Ondrej Zajicek
  if ((a->source == RTS_OSPF) ||
2225
      (a->source == RTS_OSPF_IA) ||
2226
      (a->source == RTS_OSPF_EXT1))
2227
    return rt->u.ospf.metric1;
2228 b7c48981 Ondrej Filip
#endif
2229 d1e146f2 Ondrej Zajicek
2230 b7c48981 Ondrej Filip
#ifdef CONFIG_RIP
2231 d1e146f2 Ondrej Zajicek
  if (a->source == RTS_RIP)
2232
    return rt->u.rip.metric;
2233 b7c48981 Ondrej Filip
#endif
2234 d1e146f2 Ondrej Zajicek
2235
  /* Device routes */
2236 7e95c05d Ondrej Zajicek
  if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
2237 d1e146f2 Ondrej Zajicek
    return 0;
2238
2239
  return IGP_METRIC_UNKNOWN;
2240
}
2241
2242 cfe34a31 Ondrej Zajicek
static int
2243
rt_update_hostentry(rtable *tab, struct hostentry *he)
2244
{
2245 7e95c05d Ondrej Zajicek
  rta *old_src = he->src;
2246 c477f489 Ondrej Zajicek
  int pxlen = 0;
2247 cfe34a31 Ondrej Zajicek
2248 7e95c05d Ondrej Zajicek
  /* Reset the hostentry */ 
2249
  he->src = NULL;
2250
  he->gw = IPA_NONE;
2251
  he->dest = RTD_UNREACHABLE;
2252
  he->igp_metric = 0;
2253
2254 fe9f1a6d Ondrej Zajicek (work)
  // XXXX
2255
  // net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
2256
  net *n = NULL;
2257 d1e146f2 Ondrej Zajicek
  if (n)
2258 cfe34a31 Ondrej Zajicek
    {
2259 cf98be7b Ondrej Zajicek
      rte *e = n->routes;
2260
      rta *a = e->attrs;
2261 fe9f1a6d Ondrej Zajicek (work)
      pxlen = n->n.addr->pxlen;
2262 cfe34a31 Ondrej Zajicek
2263 2c9033af Ondrej Zajicek
      if (a->hostentry)
2264
        {
2265
          /* Recursive route should not depend on another recursive route */
2266 fe9f1a6d Ondrej Zajicek (work)
          log(L_WARN "Next hop address %I resolvable through recursive route for %N",
2267
              he->addr, n->n.addr);
2268 7e95c05d Ondrej Zajicek
          goto done;
2269 2c9033af Ondrej Zajicek
        }
2270 7e95c05d Ondrej Zajicek
2271
      if (a->dest == RTD_DEVICE)
2272 cfe34a31 Ondrej Zajicek
        {
2273 f2b76f2c Ondrej Zajicek
          if (if_local_addr(he->addr, a->iface))
2274 cfe34a31 Ondrej Zajicek
            {
2275
              /* The host address is a local address, this is not valid */
2276
              log(L_WARN "Next hop address %I is a local address of iface %s",
2277 f2b76f2c Ondrej Zajicek
                  he->addr, a->iface->name);
2278 7e95c05d Ondrej Zajicek
              goto done;
2279 cfe34a31 Ondrej Zajicek
                  }
2280 7e95c05d Ondrej Zajicek
2281
          /* The host is directly reachable, use link as a gateway */
2282
          he->gw = he->link;
2283
          he->dest = RTD_ROUTER;
2284 cfe34a31 Ondrej Zajicek
        }
2285
      else
2286
        {
2287
          /* The host is reachable through some route entry */
2288
          he->gw = a->gw;
2289
          he->dest = a->dest;
2290
        }
2291 d1e146f2 Ondrej Zajicek
2292 7e95c05d Ondrej Zajicek
      he->src = rta_clone(a);
2293 cf98be7b Ondrej Zajicek
      he->igp_metric = rt_get_igp_metric(e);
2294 cfe34a31 Ondrej Zajicek
    }
2295
2296 7e95c05d Ondrej Zajicek
 done:
2297 c477f489 Ondrej Zajicek
  /* Add a prefix range to the trie */
2298 5e173e9f Jan Moskyto Matejka
  /* XXXX
2299 d7661fbe Jan Moskyto Matejka
  if (ipa_is_ip4(he->addr))
2300
    trie_add_prefix(tab->hostcache->trie, he->addr, IP4_MAX_PREFIX_LENGTH, pxlen, IP4_MAX_PREFIX_LENGTH);
2301
  else
2302
    trie_add_prefix(tab->hostcache->trie, he->addr, IP6_MAX_PREFIX_LENGTH, pxlen, IP6_MAX_PREFIX_LENGTH);
2303 5e173e9f Jan Moskyto Matejka
  */
2304 c477f489 Ondrej Zajicek
2305 7e95c05d Ondrej Zajicek
  rta_free(old_src);
2306
  return old_src != he->src;
2307 cfe34a31 Ondrej Zajicek
}
2308
2309
static void
2310
rt_update_hostcache(rtable *tab)
2311
{
2312
  struct hostcache *hc = tab->hostcache;
2313
  struct hostentry *he;
2314
  node *n, *x;
2315
2316 c477f489 Ondrej Zajicek
  /* Reset the trie */
2317
  lp_flush(hc->lp);
2318 51762a45 Ondrej Zajicek
  hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
2319 c477f489 Ondrej Zajicek
2320 cfe34a31 Ondrej Zajicek
  WALK_LIST_DELSAFE(n, x, hc->hostentries)
2321
    {
2322
      he = SKIP_BACK(struct hostentry, ln, n);
2323
      if (!he->uc)
2324
        {
2325 f2b76f2c Ondrej Zajicek
          hc_delete_hostentry(hc, he);
2326 cfe34a31 Ondrej Zajicek
          continue;
2327
        }
2328
2329
      if (rt_update_hostentry(tab, he))
2330
        rt_schedule_nhu(he->tab);
2331
    }
2332
2333
  tab->hcu_scheduled = 0;
2334
}
2335
2336
static struct hostentry *
2337 094d2bdb Ondrej Zajicek
rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
2338 cfe34a31 Ondrej Zajicek
{
2339
  struct hostentry *he;
2340
2341
  if (!tab->hostcache)
2342
    rt_init_hostcache(tab);
2343
2344 ae80a2de Pavel Tvrdík
  uint k = hc_hash(a, dep);
2345 f2b76f2c Ondrej Zajicek
  struct hostcache *hc = tab->hostcache;
2346
  for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
2347
    if (ipa_equal(he->addr, a) && (he->tab == dep))
2348
      return he;
2349 cfe34a31 Ondrej Zajicek
2350 1b180121 Ondrej Zajicek
  he = hc_new_hostentry(hc, a, ll, dep, k);
2351 f2b76f2c Ondrej Zajicek
  rt_update_hostentry(tab, he);
2352 cfe34a31 Ondrej Zajicek
  return he;
2353
}
2354
2355
void
2356 1b180121 Ondrej Zajicek
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll)
2357 cfe34a31 Ondrej Zajicek
{
2358 094d2bdb Ondrej Zajicek
  rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep));
2359 cfe34a31 Ondrej Zajicek
}
2360
2361 094d2bdb Ondrej Zajicek
2362 730f2e2c Martin Mares
/*
2363
 *  CLI commands
2364
 */
2365
2366
static void
2367 cfd46ee4 Martin Mares
rt_format_via(rte *e, byte *via)
2368 730f2e2c Martin Mares
{
2369
  rta *a = e->attrs;
2370
2371
  switch (a->dest)
2372
    {
2373
    case RTD_ROUTER:        bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
2374
    case RTD_DEVICE:        bsprintf(via, "dev %s", a->iface->name); break;
2375
    case RTD_BLACKHOLE:        bsprintf(via, "blackhole"); break;
2376
    case RTD_UNREACHABLE:        bsprintf(via, "unreachable"); break;
2377
    case RTD_PROHIBIT:        bsprintf(via, "prohibited"); break;
2378 7e95c05d Ondrej Zajicek
    case RTD_MULTIPATH:        bsprintf(via, "multipath"); break;
2379 730f2e2c Martin Mares
    default:                bsprintf(via, "???");
2380
    }
2381 cfd46ee4 Martin Mares
}
2382
2383
static void
2384 ce1da96e Martin Mares
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
2385 cfd46ee4 Martin Mares
{
2386 4ca93a50 Ondrej Zajicek
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8];
2387 c37e7851 Ondrej Zajicek
  byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
2388 cfd46ee4 Martin Mares
  rta *a = e->attrs;
2389 5a56f27c Ondrej Zajicek
  int primary = (e->net->routes == e);
2390 32f95476 Ondrej Zajicek
  int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
2391 094d2bdb Ondrej Zajicek
  void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs);
2392 7e95c05d Ondrej Zajicek
  struct mpnh *nh;
2393 cfd46ee4 Martin Mares
2394
  rt_format_via(e, via);
2395 c37e7851 Ondrej Zajicek
  tm_format_datetime(tm, &config->tf_route, e->lastmod);
2396 730f2e2c Martin Mares
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
2397
    bsprintf(from, " from %I", a->from);
2398
  else
2399
    from[0] = 0;
2400 094d2bdb Ondrej Zajicek
2401
  get_route_info = a->src->proto->proto->get_route_info;
2402
  if (get_route_info || d->verbose)
2403 ce1da96e Martin Mares
    {
2404
      /* Need to normalize the extended attributes */
2405
      ea_list *t = tmpa;
2406
      t = ea_append(t, a->eattrs);
2407
      tmpa = alloca(ea_scan(t));
2408
      ea_merge(t, tmpa);
2409 2f711231 Martin Mares
      ea_sort(tmpa);
2410 ce1da96e Martin Mares
    }
2411 094d2bdb Ondrej Zajicek
  if (get_route_info)
2412
    get_route_info(e, info, tmpa);
2413 730f2e2c Martin Mares
  else
2414
    bsprintf(info, " (%d)", e->pref);
2415 094d2bdb Ondrej Zajicek
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->src->proto->name,
2416 32f95476 Ondrej Zajicek
             tm, from, primary ? (sync_error ? " !" : " *") : "", info);
2417 7e95c05d Ondrej Zajicek
  for (nh = a->nexthops; nh; nh = nh->next)
2418
    cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1);
2419 730f2e2c Martin Mares
  if (d->verbose)
2420 ce1da96e Martin Mares
    rta_show(c, a, tmpa);
2421 730f2e2c Martin Mares
}
2422
2423
static void
2424
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
2425
{
2426
  rte *e, *ee;
2427
  byte ia[STD_ADDRESS_P_LENGTH+8];
2428 c865cae3 Ondrej Zajicek
  struct ea_list *tmpa;
2429
  struct announce_hook *a = NULL;
2430
  int first = 1;
2431
  int pass = 0;
2432 730f2e2c Martin Mares
2433 fe9f1a6d Ondrej Zajicek (work)
  bsprintf(ia, "%N", n->n.addr);
2434 cf98be7b Ondrej Zajicek
2435 c865cae3 Ondrej Zajicek
  if (d->export_mode)
2436
    {
2437 7aa80901 Ondrej Zajicek
      if (! d->export_protocol->rt_notify)
2438
        return;
2439
2440 c865cae3 Ondrej Zajicek
      a = proto_find_announce_hook(d->export_protocol, d->table);
2441
      if (!a)
2442
        return;
2443
    }
2444
2445
  for (e = n->routes; e; e = e->next)
2446 730f2e2c Martin Mares
    {
2447 15550957 Ondrej Zajicek
      if (rte_is_filtered(e) != d->filtered)
2448 cf98be7b Ondrej Zajicek
        continue;
2449
2450 23693958 Martin Mares
      d->rt_counter++;
2451 c865cae3 Ondrej Zajicek
      d->net_counter += first;
2452
      first = 0;
2453
2454
      if (pass)
2455
        continue;
2456
2457 730f2e2c Martin Mares
      ee = e;
2458
      rte_update_lock();                /* We use the update buffer for filtering */
2459 094d2bdb Ondrej Zajicek
      tmpa = make_tmp_attrs(e, rte_update_pool);
2460 c865cae3 Ondrej Zajicek
2461 8d9eef17 Ondrej Zajicek
      /* Special case for merged export */
2462
      if ((d->export_mode == RSEM_EXPORT) && (d->export_protocol->accept_ra_types == RA_MERGED))
2463
        {
2464
          rte *rt_free;
2465
          e = rt_export_merged(a, n, &rt_free, &tmpa, 1);
2466
          pass = 1;
2467
2468
          if (!e)
2469
          { e = ee; goto skip; }
2470
        }
2471
      else if (d->export_mode)
2472 ce1da96e Martin Mares
        {
2473 c865cae3 Ondrej Zajicek
          struct proto *ep = d->export_protocol;
2474
          int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0;
2475
2476 8d9eef17 Ondrej Zajicek
          if (ep->accept_ra_types == RA_OPTIMAL || ep->accept_ra_types == RA_MERGED)
2477 c865cae3 Ondrej Zajicek
            pass = 1;
2478
2479
          if (ic < 0)
2480
            goto skip;
2481
2482 7aa80901 Ondrej Zajicek
          if (d->export_mode > RSEM_PREEXPORT)
2483 ce1da96e Martin Mares
            {
2484 c865cae3 Ondrej Zajicek
              /*
2485
               * FIXME - This shows what should be exported according to current
2486
               * filters, but not what was really exported. 'configure soft'
2487
               * command may change the export filter and do not update routes.
2488
               */
2489 7aa80901 Ondrej Zajicek
              int do_export = (ic > 0) ||
2490
                (f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
2491 c865cae3 Ondrej Zajicek
2492 7aa80901 Ondrej Zajicek
              if (do_export != (d->export_mode == RSEM_EXPORT))
2493 c865cae3 Ondrej Zajicek
                goto skip;
2494
2495 7aa80901 Ondrej Zajicek
              if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED))
2496 c865cae3 Ondrej Zajicek
                pass = 1;
2497 ce1da96e Martin Mares
            }
2498
        }
2499 c865cae3 Ondrej Zajicek
2500
      if (d->show_protocol && (d->show_protocol != e->attrs->src->proto))
2501
        goto skip;
2502
2503
      if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
2504
        goto skip;
2505
2506
      d->show_counter++;
2507
      if (d->stats < 2)
2508
        rt_show_rte(c, ia, e, d, tmpa);
2509
      ia[0] = 0;
2510
2511
    skip:
2512 730f2e2c Martin Mares
      if (e != ee)
2513 5e9bdac2 Ondrej Zajicek
      {
2514
        rte_free(e);
2515
        e = ee;
2516
      }
2517 730f2e2c Martin Mares
      rte_update_unlock();
2518 c865cae3 Ondrej Zajicek
2519 0117d004 Martin Mares
      if (d->primary_only)
2520 ce1da96e Martin Mares
        break;
2521 730f2e2c Martin Mares
    }
2522
}
2523
2524
static void
2525
rt_show_cont(struct cli *c)
2526
{
2527
  struct rt_show_data *d = c->rover;
2528 f098e072 Martin Mares
#ifdef DEBUGGING
2529
  unsigned max = 4;
2530
#else
2531
  unsigned max = 64;
2532
#endif
2533 730f2e2c Martin Mares
  struct fib *fib = &d->table->fib;
2534
  struct fib_iterator *it = &d->fit;
2535
2536
  FIB_ITERATE_START(fib, it, f)
2537
    {
2538
      net *n = (net *) f;
2539 ce1da96e Martin Mares
      if (d->running_on_config && d->running_on_config != config)
2540
        {
2541
          cli_printf(c, 8004, "Stopped due to reconfiguration");
2542
          goto done;
2543
        }
2544 0c791f87 Ondrej Zajicek
      if (d->export_protocol && (d->export_protocol->export_state == ES_DOWN))
2545 ce1da96e Martin Mares
        {
2546
          cli_printf(c, 8005, "Protocol is down");
2547
          goto done;
2548
        }
2549 730f2e2c Martin Mares
      if (!max--)
2550
        {
2551
          FIB_ITERATE_PUT(it, f);
2552
          return;
2553
        }
2554
      rt_show_net(c, n, d);
2555
    }
2556
  FIB_ITERATE_END(f);
2557 23693958 Martin Mares
  if (d->stats)
2558
    cli_printf(c, 14, "%d of %d routes for %d networks", d->show_counter, d->rt_counter, d->net_counter);
2559
  else
2560
    cli_printf(c, 0, "");
2561 ce1da96e Martin Mares
done:
2562 730f2e2c Martin Mares
  c->cont = c->cleanup = NULL;
2563
}
2564
2565
static void
2566
rt_show_cleanup(struct cli *c)
2567
{
2568
  struct rt_show_data *d = c->rover;
2569
2570
  /* Unlink the iterator */
2571
  fit_get(&d->table->fib, &d->fit);
2572
}
2573
2574
void
2575
rt_show(struct rt_show_data *d)
2576
{
2577
  net *n;
2578
2579 e667622a Ondrej Filip
  /* Default is either a master table or a table related to a respective protocol */
2580 c865cae3 Ondrej Zajicek
  if (!d->table && d->export_protocol) d->table = d->export_protocol->table;
2581
  if (!d->table && d->show_protocol) d->table = d->show_protocol->table;
2582 e667622a Ondrej Filip
  if (!d->table) d->table = config->master_rtc->table;
2583
2584 c865cae3 Ondrej Zajicek
  /* Filtered routes are neither exported nor have sensible ordering */
2585
  if (d->filtered && (d->export_mode || d->primary_only))
2586
    cli_msg(0, "");
2587
2588 d7661fbe Jan Moskyto Matejka
  if (!d->prefix)
2589 730f2e2c Martin Mares
    {
2590
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
2591
      this_cli->cont = rt_show_cont;
2592
      this_cli->cleanup = rt_show_cleanup;
2593
      this_cli->rover = d;
2594
    }
2595
  else
2596
    {
2597 fe9f1a6d Ondrej Zajicek (work)
      /* XXXX 
2598 9449c91a Martin Mares
      if (d->show_for)
2599 d1e146f2 Ondrej Zajicek
        n = net_route(d->table, d->prefix, d->pxlen);
2600 9449c91a Martin Mares
      else
2601 d1e146f2 Ondrej Zajicek
        n = net_find(d->table, d->prefix, d->pxlen);
2602 fe9f1a6d Ondrej Zajicek (work)
      */
2603
      n = NULL;
2604 0da562a7 Ondrej Zajicek
2605 730f2e2c Martin Mares
      if (n)
2606 0da562a7 Ondrej Zajicek
        rt_show_net(this_cli, n, d);
2607
2608
      if (d->rt_counter)
2609
        cli_msg(0, "");
2610 730f2e2c Martin Mares
      else
2611
        cli_msg(8001, "Network not in table");
2612
    }
2613
}
2614 3ce8c610 Martin Mares
2615
/*
2616
 *  Documentation for functions declared inline in route.h
2617
 */
2618
#if 0
2619

2620
/**
2621
 * net_find - find a network entry
2622
 * @tab: a routing table
2623
 * @addr: address of the network
2624
 *
2625
 * net_find() looks up the given network in routing table @tab and
2626
 * returns a pointer to its &net entry or %NULL if no such network
2627
 * exists.
2628
 */
2629 fe9f1a6d Ondrej Zajicek (work)
static inline net *net_find(rtable *tab, net_addr *addr)
2630 3ce8c610 Martin Mares
{ DUMMY; }
2631

2632
/**
2633
 * net_get - obtain a network entry
2634
 * @tab: a routing table
2635
 * @addr: address of the network
2636
 *
2637
 * net_get() looks up the given network in routing table @tab and
2638
 * returns a pointer to its &net entry. If no such entry exists, it's
2639
 * created.
2640
 */
2641 fe9f1a6d Ondrej Zajicek (work)
static inline net *net_get(rtable *tab, net_addr *addr)
2642 3ce8c610 Martin Mares
{ DUMMY; }
2643

2644
/**
2645
 * rte_cow - copy a route for writing
2646
 * @r: a route entry to be copied
2647
 *
2648
 * rte_cow() takes a &rte and prepares it for modification. The exact action
2649
 * taken depends on the flags of the &rte -- if it's a temporary entry, it's
2650
 * just returned unchanged, else a new temporary entry with the same contents
2651
 * is created.
2652
 *
2653
 * The primary use of this function is inside the filter machinery -- when
2654
 * a filter wants to modify &rte contents (to change the preference or to
2655
 * attach another set of attributes), it must ensure that the &rte is not
2656
 * shared with anyone else (and especially that it isn't stored in any routing
2657
 * table).
2658
 *
2659 2e9b2421 Martin Mares
 * Result: a pointer to the new writable &rte.
2660 3ce8c610 Martin Mares
 */
2661
static inline rte * rte_cow(rte *r)
2662
{ DUMMY; }
2663

2664
#endif