Statistics
| Branch: | Revision:

iof-bird-daemon / proto / babel / babel.c @ 153f02da

History | View | Annotate | Download (56.3 KB)

1 937e75d8 Ondrej Zajicek (work)
/*
2
 *        BIRD -- The Babel protocol
3
 *
4
 *        Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 *
8
 *        This file contains the main routines for handling and sending TLVs, as
9
 *        well as timers and interaction with the nest.
10
 */
11
12
/**
13
 * DOC: The Babel protocol
14
 *
15
 * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
16
 * robust and efficient both in ordinary wired networks and in wireless mesh
17
 * networks.
18
 *
19
 * The Babel protocol keeps state for each neighbour in a &babel_neighbor
20
 * struct, tracking received Hello and I Heard You (IHU) messages. A
21
 * &babel_interface struct keeps hello and update times for each interface, and
22
 * a separate hello seqno is maintained for each interface.
23
 *
24
 * For each prefix, Babel keeps track of both the possible routes (with next hop
25
 * and router IDs), as well as the feasibility distance for each prefix and
26
 * router id. The prefix itself is tracked in a &babel_entry struct, while the
27
 * possible routes for the prefix are tracked as &babel_route entries and the
28
 * feasibility distance is maintained through &babel_source structures.
29
 *
30
 * The main route selection is done in babel_select_route(). This is called when
31
 * an entry is updated by receiving updates from the network or when modified by
32
 * internal timers. It performs feasibility checks on the available routes for
33
 * the prefix and selects the one with the lowest metric to be announced to the
34
 * core.
35
 */
36
37
#include <stdlib.h>
38
#include "babel.h"
39
40
41
#define OUR_ROUTE(r) (r->neigh == NULL)
42
43
/*
44
 * Is one number greater or equal than another mod 2^16? This is based on the
45
 * definition of serial number space in RFC 1982. Note that arguments are of
46
 * uint type to avoid integer promotion to signed integer.
47
 */
48
static inline int ge_mod64k(uint a, uint b)
49
{ return (u16)(a - b) < 0x8000; }
50
51
static void babel_dump_entry(struct babel_entry *e);
52
static void babel_dump_route(struct babel_route *r);
53
static void babel_select_route(struct babel_entry *e);
54
static void babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n);
55
static void babel_send_wildcard_request(struct babel_iface *ifa);
56 5e8df049 Ondrej Zajicek (work)
static int  babel_cache_seqno_request(struct babel_proto *p, net_addr *n, u64 router_id, u16 seqno);
57 937e75d8 Ondrej Zajicek (work)
static void babel_trigger_iface_update(struct babel_iface *ifa);
58
static void babel_trigger_update(struct babel_proto *p);
59
static void babel_send_seqno_request(struct babel_entry *e);
60
static inline void babel_kick_timer(struct babel_proto *p);
61
static inline void babel_iface_kick_timer(struct babel_iface *ifa);
62
63
64
/*
65
 *        Functions to maintain data structures
66
 */
67
68
static void
69 5e8df049 Ondrej Zajicek (work)
babel_init_entry(void *E)
70 937e75d8 Ondrej Zajicek (work)
{
71 5e8df049 Ondrej Zajicek (work)
  struct babel_entry *e = E;
72
73 937e75d8 Ondrej Zajicek (work)
  e->updated = now;
74
  init_list(&e->sources);
75
  init_list(&e->routes);
76
}
77
78
static inline struct babel_entry *
79 5e8df049 Ondrej Zajicek (work)
babel_find_entry(struct babel_proto *p, const net_addr *n)
80 937e75d8 Ondrej Zajicek (work)
{
81 4324025f Ondrej Zajicek (work)
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
82
  return fib_find(rtable, n);
83 937e75d8 Ondrej Zajicek (work)
}
84
85
static struct babel_entry *
86 5e8df049 Ondrej Zajicek (work)
babel_get_entry(struct babel_proto *p, const net_addr *n)
87 937e75d8 Ondrej Zajicek (work)
{
88 4324025f Ondrej Zajicek (work)
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
89
  struct babel_entry *e = fib_get(rtable, n);
90 937e75d8 Ondrej Zajicek (work)
  e->proto = p;
91
  return e;
92
}
93
94
static struct babel_source *
95
babel_find_source(struct babel_entry *e, u64 router_id)
96
{
97
  struct babel_source *s;
98
99
  WALK_LIST(s, e->sources)
100
    if (s->router_id == router_id)
101
      return s;
102
103
  return NULL;
104
}
105
106
static struct babel_source *
107
babel_get_source(struct babel_entry *e, u64 router_id)
108
{
109
  struct babel_proto *p = e->proto;
110
  struct babel_source *s = babel_find_source(e, router_id);
111
112
  if (s)
113
    return s;
114
115
  s = sl_alloc(p->source_slab);
116
  s->router_id = router_id;
117
  s->expires = now + BABEL_GARBAGE_INTERVAL;
118
  s->seqno = 0;
119
  s->metric = BABEL_INFINITY;
120
  add_tail(&e->sources, NODE s);
121
122
  return s;
123
}
124
125
static void
126
babel_expire_sources(struct babel_entry *e)
127
{
128
  struct babel_proto *p = e->proto;
129
  struct babel_source *n, *nx;
130
131
  WALK_LIST_DELSAFE(n, nx, e->sources)
132
  {
133
    if (n->expires && n->expires <= now)
134
    {
135
      rem_node(NODE n);
136
      sl_free(p->source_slab, n);
137
    }
138
  }
139
}
140
141
static struct babel_route *
142
babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
143
{
144
  struct babel_route *r;
145
146
  WALK_LIST(r, e->routes)
147
    if (r->neigh == n)
148
      return r;
149
150
  return NULL;
151
}
152
153
static struct babel_route *
154
babel_get_route(struct babel_entry *e, struct babel_neighbor *nbr)
155
{
156
  struct babel_proto *p = e->proto;
157
  struct babel_route *r = babel_find_route(e, nbr);
158
159
  if (r)
160
    return r;
161
162
  r = sl_alloc(p->route_slab);
163
  memset(r, 0, sizeof(*r));
164
  r->e = e;
165
  add_tail(&e->routes, NODE r);
166
167
  if (nbr)
168
  {
169
    r->neigh = nbr;
170
    r->expires = now + BABEL_GARBAGE_INTERVAL;
171
    add_tail(&nbr->routes, NODE &r->neigh_route);
172
  }
173
174
  return r;
175
}
176
177
static void
178
babel_flush_route(struct babel_route *r)
179
{
180
  struct babel_proto *p = r->e->proto;
181
182 5e8df049 Ondrej Zajicek (work)
  DBG("Babel: Flush route %N router_id %lR neigh %I\n",
183
      r->e->n.addr, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE);
184 937e75d8 Ondrej Zajicek (work)
185
  rem_node(NODE r);
186
187
  if (r->neigh)
188
    rem_node(&r->neigh_route);
189
190
  if (r->e->selected_in == r)
191
    r->e->selected_in = NULL;
192
193
  if (r->e->selected_out == r)
194
    r->e->selected_out = NULL;
195
196
  sl_free(p->route_slab, r);
197
}
198
199
static void
200
babel_expire_route(struct babel_route *r)
201
{
202
  struct babel_proto *p = r->e->proto;
203
  struct babel_entry *e = r->e;
204
205 5e8df049 Ondrej Zajicek (work)
  TRACE(D_EVENTS, "Route expiry timer for %N router-id %lR fired",
206
        e->n.addr, r->router_id);
207 937e75d8 Ondrej Zajicek (work)
208
  if (r->metric < BABEL_INFINITY)
209
  {
210
    r->metric = BABEL_INFINITY;
211
    r->expires = now + r->expiry_interval;
212
  }
213
  else
214
  {
215
    babel_flush_route(r);
216
  }
217
}
218
219
static void
220
babel_refresh_route(struct babel_route *r)
221
{
222
  if (!OUR_ROUTE(r) && (r == r->e->selected_in))
223
    babel_send_route_request(r->e, r->neigh);
224
225
  r->refresh_time = 0;
226
}
227
228
static void
229 4324025f Ondrej Zajicek (work)
babel_expire_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
230 937e75d8 Ondrej Zajicek (work)
{
231
  struct babel_route *r, *rx;
232
  struct fib_iterator fit;
233
234 4324025f Ondrej Zajicek (work)
  FIB_ITERATE_INIT(&fit, rtable);
235 937e75d8 Ondrej Zajicek (work)
236
loop:
237 4324025f Ondrej Zajicek (work)
  FIB_ITERATE_START(rtable, &fit, struct babel_entry, e)
238 937e75d8 Ondrej Zajicek (work)
  {
239
    int changed = 0;
240
241
    WALK_LIST_DELSAFE(r, rx, e->routes)
242
    {
243
      if (r->refresh_time && r->refresh_time <= now)
244
        babel_refresh_route(r);
245
246
      if (r->expires && r->expires <= now)
247
      {
248
        babel_expire_route(r);
249
        changed = 1;
250
      }
251
    }
252
253
    if (changed)
254
    {
255
      /*
256
       * We have to restart the iteration because there may be a cascade of
257
       * synchronous events babel_select_route() -> nest table change ->
258 4324025f Ondrej Zajicek (work)
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
259 937e75d8 Ondrej Zajicek (work)
       */
260
261 5e8df049 Ondrej Zajicek (work)
      FIB_ITERATE_PUT(&fit);
262 937e75d8 Ondrej Zajicek (work)
      babel_select_route(e);
263
      goto loop;
264
    }
265
266
    babel_expire_sources(e);
267
268
    /* Remove empty entries */
269
    if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes))
270
    {
271 5e8df049 Ondrej Zajicek (work)
      FIB_ITERATE_PUT(&fit);
272 4324025f Ondrej Zajicek (work)
      fib_delete(rtable, e);
273 937e75d8 Ondrej Zajicek (work)
      goto loop;
274
    }
275
  }
276 5e8df049 Ondrej Zajicek (work)
  FIB_ITERATE_END;
277 937e75d8 Ondrej Zajicek (work)
}
278
279 4324025f Ondrej Zajicek (work)
static void
280
babel_expire_routes(struct babel_proto *p)
281
{
282
  babel_expire_routes_(p, &p->ip4_rtable);
283
  babel_expire_routes_(p, &p->ip6_rtable);
284
}
285
286 937e75d8 Ondrej Zajicek (work)
static struct babel_neighbor *
287
babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
288
{
289
  struct babel_neighbor *nbr;
290
291
  WALK_LIST(nbr, ifa->neigh_list)
292
    if (ipa_equal(nbr->addr, addr))
293
      return nbr;
294
295
  return NULL;
296
}
297
298
static struct babel_neighbor *
299
babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
300
{
301
  struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);
302
303
  if (nbr)
304
    return nbr;
305
306
  nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
307
  nbr->ifa = ifa;
308
  nbr->addr = addr;
309
  nbr->txcost = BABEL_INFINITY;
310
  init_list(&nbr->routes);
311
  add_tail(&ifa->neigh_list, NODE nbr);
312
313
  return nbr;
314
}
315
316
static void
317
babel_flush_neighbor(struct babel_neighbor *nbr)
318
{
319
  struct babel_proto *p = nbr->ifa->proto;
320
  node *n;
321
322
  TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
323
324
  WALK_LIST_FIRST(n, nbr->routes)
325
  {
326
    struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n);
327
    struct babel_entry *e = r->e;
328
    int selected = (r == e->selected_in);
329
330
    babel_flush_route(r);
331
332
    if (selected)
333
      babel_select_route(e);
334
  }
335
336
  rem_node(NODE nbr);
337
  mb_free(nbr);
338
}
339
340
static void
341
babel_expire_ihu(struct babel_neighbor *nbr)
342
{
343
  nbr->txcost = BABEL_INFINITY;
344
}
345
346
static void
347
babel_expire_hello(struct babel_neighbor *nbr)
348
{
349
  nbr->hello_map <<= 1;
350
351
  if (nbr->hello_cnt < 16)
352
    nbr->hello_cnt++;
353
354
  if (!nbr->hello_map)
355
    babel_flush_neighbor(nbr);
356
}
357
358
static void
359
babel_expire_neighbors(struct babel_proto *p)
360
{
361
  struct babel_iface *ifa;
362
  struct babel_neighbor *nbr, *nbx;
363
364
  WALK_LIST(ifa, p->interfaces)
365
  {
366
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
367
    {
368
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now)
369
        babel_expire_ihu(nbr);
370
371
      if (nbr->hello_expiry && nbr->hello_expiry <= now)
372
        babel_expire_hello(nbr);
373
    }
374
  }
375
}
376
377
378
/*
379
 *        Best route selection
380
 */
381
382
/*
383
 * From the RFC (section 3.5.1):
384
 *
385
 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
386
 * metric) is feasible if one of the following conditions holds:
387
 *
388
 * - metric is infinite; or
389
 *
390
 * - no entry exists in the source table indexed by (id, prefix, plen); or
391
 *
392
 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
393
 *   table, and either
394
 *   - seqno' < seqno or
395
 *   - seqno = seqno' and metric < metric'.
396
 */
397
static inline int
398
babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
399
{
400
  return !s ||
401
    (metric == BABEL_INFINITY) ||
402
    (seqno > s->seqno) ||
403
    ((seqno == s->seqno) && (metric < s->metric));
404
}
405
406
static u16
407
babel_compute_rxcost(struct babel_neighbor *n)
408
{
409
  struct babel_iface *ifa = n->ifa;
410
  u8 cnt, missed;
411
  u16 map=n->hello_map;
412
413
  if (!map) return BABEL_INFINITY;
414
  cnt = u32_popcount(map); // number of bits set
415
  missed = n->hello_cnt-cnt;
416
417
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
418
  {
419
    /* ETX - Appendix 2.2 in the RFC.
420

421
       beta = prob. of successful transmission.
422
       rxcost = BABEL_RXCOST_WIRELESS/beta
423

424
       Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
425
       Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
426
   */
427
    if (!cnt) return BABEL_INFINITY;
428
    return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt;
429
  }
430
  else
431
  {
432
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
433
    DBG("Babel: Missed %d hellos from %I\n", missed, n->addr);
434
    /* Link is bad if more than half the expected hellos were lost */
435
    return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost;
436
  }
437
}
438
439
440
static u16
441
babel_compute_cost(struct babel_neighbor *n)
442
{
443
  struct babel_iface *ifa = n->ifa;
444
  u16 rxcost = babel_compute_rxcost(n);
445
  if (rxcost == BABEL_INFINITY) return rxcost;
446
  else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
447
  {
448
    /* ETX - Appendix 2.2 in the RFC */
449
    return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS;
450
  }
451
  else
452
  {
453
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
454
    return n->txcost;
455
  }
456
}
457
458
/* Simple additive metric - Appendix 3.1 in the RFC */
459
static u16
460
babel_compute_metric(struct babel_neighbor *n, uint metric)
461
{
462
  metric += babel_compute_cost(n);
463
  return MIN(metric, BABEL_INFINITY);
464
}
465
466
467
/**
468
 * babel_announce_rte - announce selected route to the core
469
 * @p: Babel protocol instance
470
 * @e: Babel route entry to announce
471
 *
472
 * This function announces a Babel entry to the core if it has a selected
473
 * incoming path, and retracts it otherwise. If the selected entry has infinite
474
 * metric, the route is announced as unreachable.
475
 */
476
static void
477
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
478
{
479
  struct babel_route *r = e->selected_in;
480 4324025f Ondrej Zajicek (work)
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
481 937e75d8 Ondrej Zajicek (work)
482
  if (r)
483
  {
484 b2b84359 Jan Moskyto Matejka
    rta *ap0 = allocz(RTA_MAX_SIZE);
485
    *ap0 = (rta) {
486 937e75d8 Ondrej Zajicek (work)
      .src = p->p.main_source,
487
      .source = RTS_BABEL,
488
      .scope = SCOPE_UNIVERSE,
489 b2b84359 Jan Moskyto Matejka
      .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_UNICAST,
490 937e75d8 Ondrej Zajicek (work)
      .from = r->neigh->addr,
491 b2b84359 Jan Moskyto Matejka
      .nh.iface = r->neigh->ifa->iface,
492 937e75d8 Ondrej Zajicek (work)
    };
493
494
    if (r->metric < BABEL_INFINITY)
495 b2b84359 Jan Moskyto Matejka
      ap0->nh.gw = r->next_hop;
496 937e75d8 Ondrej Zajicek (work)
497 b2b84359 Jan Moskyto Matejka
    rta *a = rta_lookup(ap0);
498 937e75d8 Ondrej Zajicek (work)
    rte *rte = rte_get_temp(a);
499
    rte->u.babel.metric = r->metric;
500
    rte->u.babel.router_id = r->router_id;
501
    rte->pflags = 0;
502
503 4324025f Ondrej Zajicek (work)
    rte_update2(c, e->n.addr, rte, p->p.main_source);
504 937e75d8 Ondrej Zajicek (work)
  }
505
  else
506
  {
507
    /* Retraction */
508 4324025f Ondrej Zajicek (work)
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
509 937e75d8 Ondrej Zajicek (work)
  }
510
}
511
512
/**
513
 * babel_select_route - select best route for given route entry
514
 * @e: Babel entry to select the best route for
515
 *
516
 * Select the best feasible route for a given prefix among the routes received
517
 * from peers, and propagate it to the nest. This just selects the feasible
518
 * route with the lowest metric.
519
 *
520
 * If no feasible route is available for a prefix that previously had a route
521
 * selected, a seqno request is sent to try to get a valid route. In the
522
 * meantime, the route is marked as infeasible in the nest (to blackhole packets
523
 * going to it, as per the RFC).
524
 *
525
 * If no feasible route is available, and no previous route is selected, the
526
 * route is removed from the nest entirely.
527
 */
528
static void
529
babel_select_route(struct babel_entry *e)
530
{
531
  struct babel_proto *p = e->proto;
532
  struct babel_route *r, *cur = e->selected_in;
533
534
  /* try to find the best feasible route */
535
  WALK_LIST(r, e->routes)
536
    if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */
537
        (!cur || r->metric < cur->metric) &&
538
        babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
539
      cur = r;
540
541
  if (cur && !OUR_ROUTE(cur) &&
542
      ((!e->selected_in && cur->metric < BABEL_INFINITY) ||
543
       (e->selected_in && cur->metric < e->selected_in->metric)))
544
  {
545 5e8df049 Ondrej Zajicek (work)
    TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
546
          e->n.addr, cur->router_id, cur->metric);
547 937e75d8 Ondrej Zajicek (work)
548
    e->selected_in = cur;
549
    e->updated = now;
550
    babel_announce_rte(p, e);
551
  }
552
  else if (!cur || cur->metric == BABEL_INFINITY)
553
  {
554
    /* Couldn't find a feasible route. If we have a selected route, that means
555
       it just became infeasible; so set it's metric to infinite and install it
556
       (as unreachable), then send a seqno request.
557

558
       babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
559
    if (e->selected_in)
560
    {
561 5e8df049 Ondrej Zajicek (work)
      TRACE(D_EVENTS, "Lost feasible route for prefix %N",
562
            e->n.addr);
563 937e75d8 Ondrej Zajicek (work)
564
      e->selected_in->metric = BABEL_INFINITY;
565
      e->updated = now;
566
567
      babel_send_seqno_request(e);
568
      babel_announce_rte(p, e);
569 0f673666 Ondrej Zajicek (work)
570
      /* Section 3.6 of the RFC forbids an infeasible from being selected. This
571
         is cleared after announcing the route to the core to make sure an
572
         unreachable route is propagated first. */
573
      e->selected_in = NULL;
574 937e75d8 Ondrej Zajicek (work)
    }
575
    else
576
    {
577
      /* No route currently selected, and no new one selected; this means we
578
         don't have a route to this destination anymore (and were probably
579
         called from an expiry timer). Remove the route from the nest. */
580 5e8df049 Ondrej Zajicek (work)
      TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
581 937e75d8 Ondrej Zajicek (work)
582
      e->selected_in = NULL;
583
      e->updated = now;
584
      babel_announce_rte(p, e);
585
    }
586
  }
587
}
588
589
/*
590
 *        Functions to send replies
591
 */
592
593
static void
594
babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
595
{
596
  struct babel_proto *p = ifa->proto;
597
  union babel_msg msg = {};
598
599
  TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce);
600
601
  msg.type = BABEL_TLV_ACK;
602
  msg.ack.nonce = nonce;
603
604
  babel_send_unicast(&msg, ifa, dest);
605
}
606
607
static void
608
babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
609
{
610
  struct babel_proto *p = ifa->proto;
611
612
  msg->type = BABEL_TLV_IHU;
613
  msg->ihu.addr = n->addr;
614
  msg->ihu.rxcost = babel_compute_rxcost(n);
615
  msg->ihu.interval = ifa->cf->ihu_interval;
616
617
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %d",
618
        msg->ihu.addr, msg->ihu.rxcost, msg->ihu.interval);
619
}
620
621
static void
622
babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
623
{
624
  union babel_msg msg = {};
625
  babel_build_ihu(&msg, ifa, n);
626
  babel_send_unicast(&msg, ifa, n->addr);
627
}
628
629
static void
630
babel_send_ihus(struct babel_iface *ifa)
631
{
632
  struct babel_neighbor *n;
633
  WALK_LIST(n, ifa->neigh_list)
634
  {
635
    union babel_msg msg = {};
636
    babel_build_ihu(&msg, ifa, n);
637
    babel_enqueue(&msg, ifa);
638
  }
639
}
640
641
static void
642
babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
643
{
644
  struct babel_proto *p = ifa->proto;
645
  union babel_msg msg = {};
646
647
  msg.type = BABEL_TLV_HELLO;
648
  msg.hello.seqno = ifa->hello_seqno++;
649
  msg.hello.interval = ifa->cf->hello_interval;
650
651
  TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %d",
652
        ifa->ifname, msg.hello.seqno, msg.hello.interval);
653
654
  babel_enqueue(&msg, ifa);
655
656
  if (send_ihu)
657
    babel_send_ihus(ifa);
658
}
659
660
static void
661
babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n)
662
{
663
  struct babel_proto *p = e->proto;
664
  struct babel_iface *ifa = n->ifa;
665
  union babel_msg msg = {};
666
667 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Sending route request for %N to %I",
668
        e->n.addr, n->addr);
669 937e75d8 Ondrej Zajicek (work)
670
  msg.type = BABEL_TLV_ROUTE_REQUEST;
671 5e8df049 Ondrej Zajicek (work)
  net_copy(&msg.route_request.net, e->n.addr);
672 937e75d8 Ondrej Zajicek (work)
673
  babel_send_unicast(&msg, ifa, n->addr);
674
}
675
676
static void
677
babel_send_wildcard_request(struct babel_iface *ifa)
678
{
679
  struct babel_proto *p = ifa->proto;
680
  union babel_msg msg = {};
681
682
  TRACE(D_PACKETS, "Sending wildcard route request on %s",
683
        ifa->ifname);
684
685
  msg.type = BABEL_TLV_ROUTE_REQUEST;
686
  msg.route_request.full = 1;
687
688
  babel_enqueue(&msg, ifa);
689
}
690
691
static void
692
babel_send_seqno_request(struct babel_entry *e)
693
{
694
  struct babel_proto *p = e->proto;
695
  struct babel_route *r = e->selected_in;
696
  struct babel_iface *ifa = NULL;
697
  struct babel_source *s = NULL;
698
  union babel_msg msg = {};
699
700
  s = babel_find_source(e, r->router_id);
701 5e8df049 Ondrej Zajicek (work)
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
702 937e75d8 Ondrej Zajicek (work)
    return;
703
704 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d",
705
        e->n.addr, r->router_id, s->seqno + 1);
706 937e75d8 Ondrej Zajicek (work)
707
  msg.type = BABEL_TLV_SEQNO_REQUEST;
708
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
709 5e8df049 Ondrej Zajicek (work)
  msg.seqno_request.seqno = s->seqno + 1;
710 937e75d8 Ondrej Zajicek (work)
  msg.seqno_request.router_id = r->router_id;
711 5e8df049 Ondrej Zajicek (work)
  net_copy(&msg.seqno_request.net, e->n.addr);
712 937e75d8 Ondrej Zajicek (work)
713
  WALK_LIST(ifa, p->interfaces)
714
    babel_enqueue(&msg, ifa);
715
}
716
717
static void
718
babel_unicast_seqno_request(struct babel_route *r)
719
{
720
  struct babel_entry *e = r->e;
721
  struct babel_proto *p = e->proto;
722
  struct babel_iface *ifa = r->neigh->ifa;
723
  struct babel_source *s = NULL;
724
  union babel_msg msg = {};
725
726
  s = babel_find_source(e, r->router_id);
727 5e8df049 Ondrej Zajicek (work)
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
728 937e75d8 Ondrej Zajicek (work)
    return;
729
730 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d",
731
        e->n.addr, r->router_id, s->seqno + 1);
732 937e75d8 Ondrej Zajicek (work)
733
  msg.type = BABEL_TLV_SEQNO_REQUEST;
734
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
735 5e8df049 Ondrej Zajicek (work)
  msg.seqno_request.seqno = s->seqno + 1;
736 937e75d8 Ondrej Zajicek (work)
  msg.seqno_request.router_id = r->router_id;
737 5e8df049 Ondrej Zajicek (work)
  net_copy(&msg.seqno_request.net, e->n.addr);
738 937e75d8 Ondrej Zajicek (work)
739
  babel_send_unicast(&msg, ifa, r->neigh->addr);
740
}
741
742
/**
743
 * babel_send_update - send route table updates
744
 * @ifa: Interface to transmit on
745
 * @changed: Only send entries changed since this time
746
 *
747
 * This function produces update TLVs for all entries changed since the time
748
 * indicated by the &changed parameter and queues them for transmission on the
749
 * selected interface. During the process, the feasibility distance for each
750
 * transmitted entry is updated.
751
 */
752
static void
753 4324025f Ondrej Zajicek (work)
babel_send_update_(struct babel_iface *ifa, bird_clock_t changed, struct fib *rtable)
754 937e75d8 Ondrej Zajicek (work)
{
755
  struct babel_proto *p = ifa->proto;
756
757 4324025f Ondrej Zajicek (work)
  FIB_WALK(rtable, struct babel_entry, e)
758 937e75d8 Ondrej Zajicek (work)
  {
759
    struct babel_route *r = e->selected_out;
760
761
    if (!r)
762
      continue;
763
764
    /* Our own seqno might have changed, in which case we update the routes we
765
       originate. */
766
    if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno))
767
    {
768
      r->seqno = p->update_seqno;
769
      e->updated = now;
770
    }
771
772
    /* Skip routes that weren't updated since 'changed' time */
773
    if (e->updated < changed)
774
      continue;
775
776 5e8df049 Ondrej Zajicek (work)
    TRACE(D_PACKETS, "Sending update for %N router-id %lR seqno %d metric %d",
777
          e->n.addr, r->router_id, r->seqno, r->metric);
778 937e75d8 Ondrej Zajicek (work)
779
    union babel_msg msg = {};
780
    msg.type = BABEL_TLV_UPDATE;
781
    msg.update.interval = ifa->cf->update_interval;
782
    msg.update.seqno = r->seqno;
783
    msg.update.metric = r->metric;
784
    msg.update.router_id = r->router_id;
785 5e8df049 Ondrej Zajicek (work)
    net_copy(&msg.update.net, e->n.addr);
786 937e75d8 Ondrej Zajicek (work)
787 4324025f Ondrej Zajicek (work)
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
788
                           ifa->next_hop_ip4 : ifa->next_hop_ip6);
789
790 c6ed5a0f Ondrej Zajicek (work)
    babel_enqueue(&msg, ifa);
791
792
    /* Update feasibility distance for redistributed routes */
793
    if (!OUR_ROUTE(r))
794 937e75d8 Ondrej Zajicek (work)
    {
795 c6ed5a0f Ondrej Zajicek (work)
      struct babel_source *s = babel_get_source(e, r->router_id);
796
      s->expires = now + BABEL_GARBAGE_INTERVAL;
797
798
      if ((msg.update.seqno > s->seqno) ||
799
          ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
800
      {
801
        s->seqno = msg.update.seqno;
802
        s->metric = msg.update.metric;
803
      }
804 937e75d8 Ondrej Zajicek (work)
    }
805
  }
806
  FIB_WALK_END;
807
}
808
809
static void
810 4324025f Ondrej Zajicek (work)
babel_send_update(struct babel_iface *ifa, bird_clock_t changed)
811
{
812
  struct babel_proto *p = ifa->proto;
813
814
  babel_send_update_(ifa, changed, &p->ip4_rtable);
815
  babel_send_update_(ifa, changed, &p->ip6_rtable);
816
}
817
818
static void
819 937e75d8 Ondrej Zajicek (work)
babel_trigger_iface_update(struct babel_iface *ifa)
820
{
821
  struct babel_proto *p = ifa->proto;
822
823
  /* Interface not active or already scheduled */
824
  if (!ifa->up || ifa->want_triggered)
825
    return;
826
827
  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
828
        ifa->iface->name, p->update_seqno);
829
830
  ifa->want_triggered = now;
831
  babel_iface_kick_timer(ifa);
832
}
833
834
/* Sends and update on all interfaces. */
835
static void
836
babel_trigger_update(struct babel_proto *p)
837
{
838
  if (p->triggered)
839
    return;
840
841
  struct babel_iface *ifa;
842
  WALK_LIST(ifa, p->interfaces)
843
    babel_trigger_iface_update(ifa);
844
845
  p->triggered = 1;
846
}
847
848
/* A retraction is an update with an infinite metric */
849
static void
850 5e8df049 Ondrej Zajicek (work)
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
851 937e75d8 Ondrej Zajicek (work)
{
852
  struct babel_proto *p = ifa->proto;
853
  union babel_msg msg = {};
854
855 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Sending retraction for %N seqno %d", n, p->update_seqno);
856 937e75d8 Ondrej Zajicek (work)
857
  msg.type = BABEL_TLV_UPDATE;
858
  msg.update.interval = ifa->cf->update_interval;
859
  msg.update.seqno = p->update_seqno;
860
  msg.update.metric = BABEL_INFINITY;
861 5e8df049 Ondrej Zajicek (work)
  msg.update.net = *n;
862 5d6ca220 Ondrej Zajicek (work)
863
  babel_enqueue(&msg, ifa);
864
}
865
866
static void
867
babel_send_wildcard_retraction(struct babel_iface *ifa)
868
{
869
  struct babel_proto *p = ifa->proto;
870
  union babel_msg msg = {};
871
872
  TRACE(D_PACKETS, "Sending wildcard retraction on %s", ifa->ifname);
873
874
  msg.type = BABEL_TLV_UPDATE;
875
  msg.update.wildcard = 1;
876
  msg.update.interval = ifa->cf->update_interval;
877
  msg.update.seqno = p->update_seqno;
878
  msg.update.metric = BABEL_INFINITY;
879 937e75d8 Ondrej Zajicek (work)
880
  babel_enqueue(&msg, ifa);
881
}
882
883
884
/*
885
 *        TLV handler helpers
886
 */
887
888
/* Update hello history according to Appendix A1 of the RFC */
889
static void
890
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, u16 interval)
891
{
892
  /*
893
   * Compute the difference between expected and received seqno (modulo 2^16).
894
   * If the expected and received seqnos are within 16 of each other, the modular
895
   * difference is going to be less than 16 for one of the directions. Otherwise,
896
   * the values differ too much, so just reset the state.
897
   */
898
899
  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
900
901
  if (delta == 0)
902
  {
903
    /* Do nothing */
904
  }
905
  else if (delta <= 16)
906
  {
907
    /* Sending node decreased interval; fast-forward */
908
    n->hello_map <<= delta;
909
    n->hello_cnt = MIN(n->hello_cnt + delta, 16);
910
  }
911
  else if (delta >= 0xfff0)
912
  {
913
    u8 diff = (0xffff - delta);
914
    /* Sending node increased interval; undo history */
915
    n->hello_map >>= diff;
916
    n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
917
  }
918
  else
919
  {
920
    /* Note state reset - flush entries */
921
    n->hello_map = n->hello_cnt = 0;
922
  }
923
924
  /* Current entry */
925
  n->hello_map = (n->hello_map << 1) | 1;
926
  n->next_hello_seqno = seqno+1;
927
  if (n->hello_cnt < 16) n->hello_cnt++;
928
  n->hello_expiry = now + BABEL_HELLO_EXPIRY_FACTOR(interval);
929
}
930
931
static void
932
babel_expire_seqno_requests(struct babel_proto *p)
933
{
934
  struct babel_seqno_request *n, *nx;
935
  WALK_LIST_DELSAFE(n, nx, p->seqno_cache)
936
  {
937
    if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now)
938
    {
939
      rem_node(NODE n);
940
      sl_free(p->seqno_slab, n);
941
    }
942
  }
943
}
944
945
/*
946
 * Checks the seqno request cache for a matching request and returns failure if
947
 * found. Otherwise, a new entry is stored in the cache.
948
 */
949
static int
950 5e8df049 Ondrej Zajicek (work)
babel_cache_seqno_request(struct babel_proto *p, net_addr *n,
951 937e75d8 Ondrej Zajicek (work)
                          u64 router_id, u16 seqno)
952
{
953
  struct babel_seqno_request *r;
954
955
  WALK_LIST(r, p->seqno_cache)
956
  {
957 5e8df049 Ondrej Zajicek (work)
    if (net_equal(&r->net, n) && (r->router_id == router_id) && (r->seqno == seqno))
958 937e75d8 Ondrej Zajicek (work)
      return 0;
959
  }
960
961
  /* no entries found */
962
  r = sl_alloc(p->seqno_slab);
963 5e8df049 Ondrej Zajicek (work)
  net_copy(&r->net, n);
964 937e75d8 Ondrej Zajicek (work)
  r->router_id = router_id;
965
  r->seqno = seqno;
966
  r->updated = now;
967
  add_tail(&p->seqno_cache, NODE r);
968
969
  return 1;
970
}
971
972
static void
973
babel_forward_seqno_request(struct babel_entry *e,
974
                            struct babel_msg_seqno_request *in,
975
                            ip_addr sender)
976
{
977
  struct babel_proto *p = e->proto;
978
  struct babel_route *r;
979
980 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Forwarding seqno request for %N router-id %lR seqno %d",
981
        e->n.addr, in->router_id, in->seqno);
982 937e75d8 Ondrej Zajicek (work)
983
  WALK_LIST(r, e->routes)
984
  {
985
    if ((r->router_id == in->router_id) &&
986
        !OUR_ROUTE(r) &&
987
        !ipa_equal(r->neigh->addr, sender))
988
    {
989 5e8df049 Ondrej Zajicek (work)
      if (!babel_cache_seqno_request(p, e->n.addr, in->router_id, in->seqno))
990 937e75d8 Ondrej Zajicek (work)
        return;
991
992
      union babel_msg msg = {};
993
      msg.type = BABEL_TLV_SEQNO_REQUEST;
994
      msg.seqno_request.hop_count = in->hop_count-1;
995 5e8df049 Ondrej Zajicek (work)
      msg.seqno_request.seqno = in->seqno;
996 937e75d8 Ondrej Zajicek (work)
      msg.seqno_request.router_id = in->router_id;
997 5e8df049 Ondrej Zajicek (work)
      net_copy(&msg.seqno_request.net, e->n.addr);
998 937e75d8 Ondrej Zajicek (work)
999
      babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr);
1000
      return;
1001
    }
1002
  }
1003
}
1004
1005
1006
/*
1007
 *        TLV handlers
1008
 */
1009
1010
void
1011
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
1012
{
1013
  struct babel_proto *p = ifa->proto;
1014
  struct babel_msg_ack_req *msg = &m->ack_req;
1015
1016
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %d",
1017
        msg->nonce, msg->interval);
1018
1019
  babel_send_ack(ifa, msg->sender, msg->nonce);
1020
}
1021
1022
void
1023
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
1024
{
1025
  struct babel_proto *p = ifa->proto;
1026
  struct babel_msg_hello *msg = &m->hello;
1027
1028
  TRACE(D_PACKETS, "Handling hello seqno %d interval %d",
1029
        msg->seqno, msg->interval);
1030
1031
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1032
  babel_update_hello_history(n, msg->seqno, msg->interval);
1033
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
1034
    babel_send_ihu(ifa, n);
1035
}
1036
1037
void
1038
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
1039
{
1040
  struct babel_proto *p = ifa->proto;
1041
  struct babel_msg_ihu *msg = &m->ihu;
1042
1043
  /* Ignore IHUs that are not about us */
1044
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
1045
    return;
1046
1047
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d",
1048
        msg->rxcost, msg->interval);
1049
1050
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1051
  n->txcost = msg->rxcost;
1052
  n->ihu_expiry = now + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1053
}
1054
1055
/**
1056
 * babel_handle_update - handle incoming route updates
1057
 * @m: Incoming update TLV
1058
 * @ifa: Interface the update was received on
1059
 *
1060
 * This function is called as a handler for update TLVs and handles the updating
1061
 * and maintenance of route entries in Babel's internal routing cache. The
1062
 * handling follows the actions described in the Babel RFC, and at the end of
1063
 * each update handling, babel_select_route() is called on the affected entry to
1064
 * optionally update the selected routes and propagate them to the core.
1065
 */
1066
void
1067
babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
1068
{
1069
  struct babel_proto *p = ifa->proto;
1070
  struct babel_msg_update *msg = &m->update;
1071
1072 ecae2f43 Ondrej Zajicek (work)
  struct babel_neighbor *nbr;
1073 937e75d8 Ondrej Zajicek (work)
  struct babel_entry *e;
1074
  struct babel_source *s;
1075
  struct babel_route *r;
1076 ecae2f43 Ondrej Zajicek (work)
  node *n;
1077 937e75d8 Ondrej Zajicek (work)
  int feasible;
1078
1079 5e8df049 Ondrej Zajicek (work)
  if (msg->wildcard)
1080
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
1081
  else
1082
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
1083
          &msg->net, msg->seqno, msg->metric);
1084 937e75d8 Ondrej Zajicek (work)
1085 ecae2f43 Ondrej Zajicek (work)
  nbr = babel_find_neighbor(ifa, msg->sender);
1086
  if (!nbr)
1087 937e75d8 Ondrej Zajicek (work)
  {
1088
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
1089
    return;
1090
  }
1091
1092
  if (msg->router_id == p->router_id)
1093
  {
1094
    DBG("Babel: Ignoring update for our own router ID.\n");
1095
    return;
1096
  }
1097
1098 4324025f Ondrej Zajicek (work)
  struct channel *c = (msg->net.type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
1099
  if (!c || (c->channel_state != CS_UP))
1100
  {
1101
    DBG("Babel: Ignoring update for inactive address family.\n");
1102
    return;
1103
  }
1104
1105 937e75d8 Ondrej Zajicek (work)
  /*
1106
   * RFC section 3.5.4:
1107
   *
1108
   * When a Babel node receives an update (id, prefix, seqno, metric) from a
1109
   * neighbour neigh with a link cost value equal to cost, it checks whether it
1110
   * already has a routing table entry indexed by (neigh, id, prefix).
1111
   *
1112
   * If no such entry exists:
1113
   *
1114
   * o if the update is unfeasible, it is ignored;
1115
   *
1116
   * o if the metric is infinite (the update is a retraction), the update is
1117
   *   ignored;
1118
   *
1119
   * o otherwise, a new route table entry is created, indexed by (neigh, id,
1120
   *   prefix), with seqno equal to seqno and an advertised metric equal to the
1121
   *   metric carried by the update.
1122
   *
1123
   * If such an entry exists:
1124
   *
1125
   * o if the entry is currently installed and the update is unfeasible, then
1126
   *   the behaviour depends on whether the router-ids of the two entries match.
1127
   *   If the router-ids are different, the update is treated as though it were
1128
   *   a retraction (i.e., as though the metric were FFFF hexadecimal). If the
1129
   *   router-ids are equal, the update is ignored;
1130
   *
1131
   * o otherwise (i.e., if either the update is feasible or the entry is not
1132
   *   currently installed), then the entry's sequence number, advertised
1133
   *   metric, metric, and router-id are updated and, unless the advertised
1134
   *   metric is infinite, the route's expiry timer is reset to a small multiple
1135
   *   of the Interval value included in the update.
1136
   */
1137
1138 ecae2f43 Ondrej Zajicek (work)
  /* Retraction */
1139 937e75d8 Ondrej Zajicek (work)
  if (msg->metric == BABEL_INFINITY)
1140 ecae2f43 Ondrej Zajicek (work)
  {
1141 5d6ca220 Ondrej Zajicek (work)
    if (msg->wildcard)
1142 ecae2f43 Ondrej Zajicek (work)
    {
1143
      /*
1144
       * Special case: This is a retraction of all prefixes announced by this
1145
       * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
1146
       */
1147
      WALK_LIST(n, nbr->routes)
1148
      {
1149
        r = SKIP_BACK(struct babel_route, neigh_route, n);
1150
        r->metric = BABEL_INFINITY;
1151
        babel_select_route(r->e);
1152
      }
1153
    }
1154
    else
1155
    {
1156 5e8df049 Ondrej Zajicek (work)
      e = babel_find_entry(p, &msg->net);
1157 ecae2f43 Ondrej Zajicek (work)
1158
      if (!e)
1159
        return;
1160
1161
      /* The route entry indexed by neighbour */
1162
      r = babel_find_route(e, nbr);
1163 937e75d8 Ondrej Zajicek (work)
1164 ecae2f43 Ondrej Zajicek (work)
      if (!r)
1165
        return;
1166
1167
      r->metric = BABEL_INFINITY;
1168
      babel_select_route(e);
1169
    }
1170
1171
    /* Done with retractions */
1172 937e75d8 Ondrej Zajicek (work)
    return;
1173 ecae2f43 Ondrej Zajicek (work)
  }
1174 937e75d8 Ondrej Zajicek (work)
1175 5e8df049 Ondrej Zajicek (work)
  e = babel_get_entry(p, &msg->net);
1176 ecae2f43 Ondrej Zajicek (work)
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1177 937e75d8 Ondrej Zajicek (work)
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1178
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1179
1180
  if (!r)
1181
  {
1182 ecae2f43 Ondrej Zajicek (work)
    if (!feasible)
1183 937e75d8 Ondrej Zajicek (work)
      return;
1184
1185 ecae2f43 Ondrej Zajicek (work)
    r = babel_get_route(e, nbr);
1186 937e75d8 Ondrej Zajicek (work)
    r->advert_metric = msg->metric;
1187
    r->router_id = msg->router_id;
1188 ecae2f43 Ondrej Zajicek (work)
    r->metric = babel_compute_metric(nbr, msg->metric);
1189 937e75d8 Ondrej Zajicek (work)
    r->next_hop = msg->next_hop;
1190
    r->seqno = msg->seqno;
1191
  }
1192
  else if (r == r->e->selected_in && !feasible)
1193
  {
1194 ecae2f43 Ondrej Zajicek (work)
    /*
1195
     * Route is installed and update is infeasible - we may lose the route,
1196
     * so send a unicast seqno request (section 3.8.2.2 second paragraph).
1197
     */
1198 937e75d8 Ondrej Zajicek (work)
    babel_unicast_seqno_request(r);
1199
1200 ecae2f43 Ondrej Zajicek (work)
    if (msg->router_id == r->router_id)
1201
      return;
1202
1203
    /* Treat as retraction */
1204
    r->metric = BABEL_INFINITY;
1205 937e75d8 Ondrej Zajicek (work)
  }
1206
  else
1207
  {
1208
    /* Last paragraph above - update the entry */
1209
    r->advert_metric = msg->metric;
1210 ecae2f43 Ondrej Zajicek (work)
    r->metric = babel_compute_metric(nbr, msg->metric);
1211 937e75d8 Ondrej Zajicek (work)
    r->next_hop = msg->next_hop;
1212 ecae2f43 Ondrej Zajicek (work)
1213
    r->router_id = msg->router_id;
1214 937e75d8 Ondrej Zajicek (work)
    r->seqno = msg->seqno;
1215
1216 ecae2f43 Ondrej Zajicek (work)
    r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1217
    r->expires = now + r->expiry_interval;
1218
    if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
1219
      r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
1220 937e75d8 Ondrej Zajicek (work)
1221
    /* If the route is not feasible at this point, it means it is from another
1222
       neighbour than the one currently selected; so send a unicast seqno
1223
       request to try to get a better route (section 3.8.2.2 last paragraph). */
1224
    if (!feasible)
1225
      babel_unicast_seqno_request(r);
1226
  }
1227
1228
  babel_select_route(e);
1229
}
1230
1231
void
1232
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
1233
{
1234
  struct babel_proto *p = ifa->proto;
1235
  struct babel_msg_route_request *msg = &m->route_request;
1236
1237
  /* RFC 6126 3.8.1.1 */
1238
1239
  /* Wildcard request - full update on the interface */
1240
  if (msg->full)
1241
  {
1242
    TRACE(D_PACKETS, "Handling wildcard route request");
1243
    ifa->want_triggered = 1;
1244
    return;
1245
  }
1246
1247 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Handling route request for %N", &msg->net);
1248 937e75d8 Ondrej Zajicek (work)
1249
  /* Non-wildcard request - see if we have an entry for the route.
1250
     If not, send a retraction, otherwise send an update. */
1251 5e8df049 Ondrej Zajicek (work)
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1252 937e75d8 Ondrej Zajicek (work)
  if (!e)
1253
  {
1254 5e8df049 Ondrej Zajicek (work)
    babel_send_retraction(ifa, &msg->net);
1255 937e75d8 Ondrej Zajicek (work)
  }
1256
  else
1257
  {
1258
    babel_trigger_iface_update(ifa);
1259
    e->updated = now;
1260
  }
1261
}
1262
1263
1264
void
1265
babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
1266
{
1267
  struct babel_proto *p = ifa->proto;
1268
  struct babel_msg_seqno_request *msg = &m->seqno_request;
1269
1270
  /* RFC 6126 3.8.1.2 */
1271
1272 5e8df049 Ondrej Zajicek (work)
  TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d",
1273
        &msg->net, msg->router_id, msg->seqno, msg->hop_count);
1274 937e75d8 Ondrej Zajicek (work)
1275
  /* Ignore if we have no such entry or entry has infinite metric */
1276 5e8df049 Ondrej Zajicek (work)
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1277 937e75d8 Ondrej Zajicek (work)
  if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
1278
    return;
1279
1280
  /* Trigger update on incoming interface if we have a selected route with
1281
     different router id or seqno no smaller than requested */
1282
  struct babel_route *r = e->selected_out;
1283
  if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno))
1284
  {
1285
    babel_trigger_iface_update(ifa);
1286
    e->updated = now;
1287
    return;
1288
  }
1289
1290
  /* Seqno is larger; check if we own the router id */
1291
  if (msg->router_id == p->router_id)
1292
  {
1293
    /* Ours; update seqno and trigger global update */
1294
    p->update_seqno++;
1295
    babel_trigger_update(p);
1296
  }
1297
  else
1298
  {
1299
    /* Not ours; forward if TTL allows it */
1300
    if (msg->hop_count > 1)
1301
      babel_forward_seqno_request(e, msg, msg->sender);
1302
  }
1303
}
1304
1305
1306
/*
1307
 *        Babel interfaces
1308
 */
1309
1310
/**
1311
 * babel_iface_timer - Babel interface timer handler
1312
 * @t: Timer
1313
 *
1314
 * This function is called by the per-interface timer and triggers sending of
1315
 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1316
 * and updates are simply handled by setting the next_{hello,regular} variables
1317
 * on the interface, and triggering an update (and resetting the variable)
1318
 * whenever 'now' exceeds that value.
1319
 *
1320
 * For triggered updates, babel_trigger_iface_update() will set the
1321
 * want_triggered field on the interface to a timestamp value. If this is set
1322
 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1323
 * babel_send_update() will be called with this timestamp as the second
1324
 * parameter. This causes updates to be send consisting of only the routes that
1325
 * have changed since the time saved in want_triggered.
1326
 *
1327
 * Mostly when an update is triggered, the route being modified will be set to
1328
 * the value of 'now' at the time of the trigger; the >= comparison for
1329
 * selecting which routes to send in the update will make sure this is included.
1330
 */
1331
static void
1332
babel_iface_timer(timer *t)
1333
{
1334
  struct babel_iface *ifa = t->data;
1335
  struct babel_proto *p = ifa->proto;
1336
  bird_clock_t hello_period = ifa->cf->hello_interval;
1337
  bird_clock_t update_period = ifa->cf->update_interval;
1338
1339
  if (now >= ifa->next_hello)
1340
  {
1341
    babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
1342
                           ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
1343
    ifa->next_hello +=  hello_period * (1 + (now - ifa->next_hello) / hello_period);
1344
  }
1345
1346
  if (now >= ifa->next_regular)
1347
  {
1348
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
1349
    babel_send_update(ifa, 0);
1350
    ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period);
1351
    ifa->want_triggered = 0;
1352
    p->triggered = 0;
1353
  }
1354
  else if (ifa->want_triggered && (now >= ifa->next_triggered))
1355
  {
1356
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
1357
    babel_send_update(ifa, ifa->want_triggered);
1358
    ifa->next_triggered = now + MIN(5, update_period / 2 + 1);
1359
    ifa->want_triggered = 0;
1360
    p->triggered = 0;
1361
  }
1362
1363
  bird_clock_t next_event = MIN(ifa->next_hello, ifa->next_regular);
1364
  tm_start(ifa->timer, ifa->want_triggered ? 1 : (next_event - now));
1365
}
1366
1367
static inline void
1368
babel_iface_kick_timer(struct babel_iface *ifa)
1369
{
1370
  if (ifa->timer->expires > (now + 1))
1371
    tm_start(ifa->timer, 1);
1372
}
1373
1374
static void
1375
babel_iface_start(struct babel_iface *ifa)
1376
{
1377
  struct babel_proto *p = ifa->proto;
1378
1379
  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
1380
1381
  ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1;
1382
  ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1;
1383
  ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1);
1384
  ifa->want_triggered = 0;        /* We send an immediate update (below) */
1385
  tm_start(ifa->timer, 1);
1386
  ifa->up = 1;
1387
1388
  babel_send_hello(ifa, 0);
1389 5d6ca220 Ondrej Zajicek (work)
  babel_send_wildcard_retraction(ifa);
1390 937e75d8 Ondrej Zajicek (work)
  babel_send_wildcard_request(ifa);
1391
  babel_send_update(ifa, 0);        /* Full update */
1392
}
1393
1394
static void
1395
babel_iface_stop(struct babel_iface *ifa)
1396
{
1397
  struct babel_proto *p = ifa->proto;
1398
  struct babel_neighbor *nbr;
1399
  struct babel_route *r;
1400
  node *n;
1401
1402
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1403
1404
  /*
1405
   * Rather than just flushing the neighbours, we set the metric of their routes
1406
   * to infinity. This allows us to keep the neighbour hello state for when the
1407
   * interface comes back up. The routes will also be kept until they expire.
1408
   */
1409
  WALK_LIST(nbr, ifa->neigh_list)
1410
  {
1411
    WALK_LIST(n, nbr->routes)
1412
    {
1413
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1414
      r->metric = BABEL_INFINITY;
1415
      r->expires = now + r->expiry_interval;
1416
      babel_select_route(r->e);
1417
    }
1418
  }
1419
1420
  tm_stop(ifa->timer);
1421
  ifa->up = 0;
1422
}
1423
1424
static inline int
1425
babel_iface_link_up(struct babel_iface *ifa)
1426
{
1427
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
1428
}
1429
1430
static void
1431
babel_iface_update_state(struct babel_iface *ifa)
1432
{
1433
  int up = ifa->sk && babel_iface_link_up(ifa);
1434
1435
  if (up == ifa->up)
1436
    return;
1437
1438
  if (up)
1439
    babel_iface_start(ifa);
1440
  else
1441
    babel_iface_stop(ifa);
1442
}
1443
1444
static void
1445
babel_iface_update_buffers(struct babel_iface *ifa)
1446
{
1447
  if (!ifa->sk)
1448
    return;
1449
1450
  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
1451
  uint rbsize = ifa->cf->rx_buffer ?: mtu;
1452
  uint tbsize = ifa->cf->tx_length ?: mtu;
1453
  rbsize = MAX(rbsize, tbsize);
1454
1455
  sk_set_rbsize(ifa->sk, rbsize);
1456
  sk_set_tbsize(ifa->sk, tbsize);
1457
1458
  ifa->tx_length = tbsize - BABEL_OVERHEAD;
1459
}
1460
1461
static struct babel_iface*
1462
babel_find_iface(struct babel_proto *p, struct iface *what)
1463
{
1464
  struct babel_iface *ifa;
1465
1466
  WALK_LIST (ifa, p->interfaces)
1467
    if (ifa->iface == what)
1468
      return ifa;
1469
1470
  return NULL;
1471
}
1472
1473
static void
1474
babel_iface_locked(struct object_lock *lock)
1475
{
1476
  struct babel_iface *ifa = lock->data;
1477
  struct babel_proto *p = ifa->proto;
1478
1479
  if (!babel_open_socket(ifa))
1480
  {
1481
    log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
1482
    return;
1483
  }
1484
1485
  babel_iface_update_buffers(ifa);
1486
  babel_iface_update_state(ifa);
1487
}
1488
1489
static void
1490
babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
1491
{
1492
  struct babel_iface *ifa;
1493
1494
  TRACE(D_EVENTS, "Adding interface %s", new->name);
1495
1496
  pool *pool = rp_new(p->p.pool, new->name);
1497
1498
  ifa = mb_allocz(pool, sizeof(struct babel_iface));
1499
  ifa->proto = p;
1500
  ifa->iface = new;
1501
  ifa->cf = ic;
1502
  ifa->pool = pool;
1503
  ifa->ifname = new->name;
1504 153f02da Ondrej Zajicek (work)
  ifa->addr = new->llv6->ip;
1505 937e75d8 Ondrej Zajicek (work)
1506
  add_tail(&p->interfaces, NODE ifa);
1507
1508 153f02da Ondrej Zajicek (work)
  ip_addr addr4 = new->addr4 ? new->addr4->ip : IPA_NONE;
1509 4324025f Ondrej Zajicek (work)
  ifa->next_hop_ip4 = ipa_nonzero(ic->next_hop_ip4) ? ic->next_hop_ip4 : addr4;
1510
  ifa->next_hop_ip6 = ipa_nonzero(ic->next_hop_ip6) ? ic->next_hop_ip6 : ifa->addr;
1511
1512
  if (ipa_zero(ifa->next_hop_ip4) && p->ip4_channel)
1513
    log(L_WARN "%s: Cannot find IPv4 next hop addr on %s", p->p.name, new->name);
1514
1515 937e75d8 Ondrej Zajicek (work)
  init_list(&ifa->neigh_list);
1516
  ifa->hello_seqno = 1;
1517
1518
  ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0);
1519
1520
  init_list(&ifa->msg_queue);
1521
  ifa->send_event = ev_new(ifa->pool);
1522
  ifa->send_event->hook = babel_send_queue;
1523
  ifa->send_event->data = ifa;
1524
1525
  struct object_lock *lock = olock_new(ifa->pool);
1526
  lock->type = OBJLOCK_UDP;
1527
  lock->addr = IP6_BABEL_ROUTERS;
1528
  lock->port = ifa->cf->port;
1529
  lock->iface = ifa->iface;
1530
  lock->hook = babel_iface_locked;
1531
  lock->data = ifa;
1532
1533
  olock_acquire(lock);
1534
}
1535
1536
static void
1537
babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
1538
{
1539
  TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
1540
1541
  struct babel_neighbor *n;
1542
  WALK_LIST_FIRST(n, ifa->neigh_list)
1543
    babel_flush_neighbor(n);
1544
1545
  rem_node(NODE ifa);
1546
1547
  rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
1548
}
1549
1550
static void
1551
babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
1552
{
1553
  struct babel_proto *p = (void *) P;
1554
  struct babel_config *cf = (void *) P->cf;
1555
1556
  if (iface->flags & IF_IGNORE)
1557
    return;
1558
1559
  if (flags & IF_CHANGE_UP)
1560
  {
1561 4ae3ee12 Jan Maria Matejka
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1562 937e75d8 Ondrej Zajicek (work)
1563
    /* we only speak multicast */
1564
    if (!(iface->flags & IF_MULTICAST))
1565
      return;
1566
1567 153f02da Ondrej Zajicek (work)
    /* Ignore ifaces without link-local address */
1568
    if (!iface->llv6)
1569
      return;
1570
1571 937e75d8 Ondrej Zajicek (work)
    if (ic)
1572
      babel_add_iface(p, iface, ic);
1573
1574
    return;
1575
  }
1576
1577
  struct babel_iface *ifa = babel_find_iface(p, iface);
1578
1579
  if (!ifa)
1580
    return;
1581
1582
  if (flags & IF_CHANGE_DOWN)
1583
  {
1584
    babel_remove_iface(p, ifa);
1585
    return;
1586
  }
1587
1588
  if (flags & IF_CHANGE_MTU)
1589
    babel_iface_update_buffers(ifa);
1590
1591
  if (flags & IF_CHANGE_LINK)
1592
    babel_iface_update_state(ifa);
1593
}
1594
1595
static int
1596
babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new)
1597
{
1598
  struct babel_iface_config *old = ifa->cf;
1599
1600
  /* Change of these options would require to reset the iface socket */
1601
  if ((new->port != old->port) ||
1602
      (new->tx_tos != old->tx_tos) ||
1603
      (new->tx_priority != old->tx_priority))
1604
    return 0;
1605
1606
  TRACE(D_EVENTS, "Reconfiguring interface %s", ifa->iface->name);
1607
1608
  ifa->cf = new;
1609
1610 153f02da Ondrej Zajicek (work)
  ip_addr addr4 = ifa->iface->addr4 ? ifa->iface->addr4->ip : IPA_NONE;
1611
  ifa->next_hop_ip4 = ipa_nonzero(new->next_hop_ip4) ? new->next_hop_ip4 : addr4;
1612 4324025f Ondrej Zajicek (work)
  ifa->next_hop_ip6 = ipa_nonzero(new->next_hop_ip6) ? new->next_hop_ip6 : ifa->addr;
1613
1614
  if (ipa_zero(ifa->next_hop_ip4) && p->ip4_channel)
1615
    log(L_WARN "%s: Cannot find IPv4 next hop addr on %s", p->p.name, ifa->ifname);
1616
1617 13a31a40 Ondrej Zajicek (work)
  if (ifa->next_hello > (now + new->hello_interval))
1618
    ifa->next_hello = now + (random() % new->hello_interval) + 1;
1619
1620 937e75d8 Ondrej Zajicek (work)
  if (ifa->next_regular > (now + new->update_interval))
1621
    ifa->next_regular = now + (random() % new->update_interval) + 1;
1622
1623
  if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
1624
    babel_iface_update_buffers(ifa);
1625
1626
  if (new->check_link != old->check_link)
1627
    babel_iface_update_state(ifa);
1628
1629
  if (ifa->up)
1630
    babel_iface_kick_timer(ifa);
1631
1632
  return 1;
1633
}
1634
1635
static void
1636
babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
1637
{
1638
  struct iface *iface;
1639
1640
  WALK_LIST(iface, iface_list)
1641
  {
1642 153f02da Ondrej Zajicek (work)
    if (!(iface->flags & IF_UP))
1643
      continue;
1644
1645
    /* Ignore non-multicast ifaces */
1646
    if (!(iface->flags & IF_MULTICAST))
1647
      continue;
1648
1649
    /* Ignore ifaces without link-local address */
1650
    if (!iface->llv6)
1651 937e75d8 Ondrej Zajicek (work)
      continue;
1652
1653
    struct babel_iface *ifa = babel_find_iface(p, iface);
1654
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1655
1656
    if (ifa && ic)
1657
    {
1658
      if (babel_reconfigure_iface(p, ifa, ic))
1659
        continue;
1660
1661
      /* Hard restart */
1662
      log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
1663
      babel_remove_iface(p, ifa);
1664
      babel_add_iface(p, iface, ic);
1665
    }
1666
1667
    if (ifa && !ic)
1668
      babel_remove_iface(p, ifa);
1669
1670
    if (!ifa && ic)
1671
      babel_add_iface(p, iface, ic);
1672
  }
1673
}
1674
1675
1676
/*
1677
 *        Debugging and info output functions
1678
 */
1679
1680
static void
1681
babel_dump_source(struct babel_source *s)
1682
{
1683
  debug("Source router_id %lR seqno %d metric %d expires %d\n",
1684
        s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0);
1685
}
1686
1687
static void
1688
babel_dump_route(struct babel_route *r)
1689
{
1690
  debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %d\n",
1691
        r->neigh ? r->neigh->addr : IPA_NONE,
1692
        r->neigh ? r->neigh->ifa->ifname : "(none)",
1693
        r->seqno, r->advert_metric, r->metric,
1694
        r->router_id, r->expires ? r->expires-now : 0);
1695
}
1696
1697
static void
1698
babel_dump_entry(struct babel_entry *e)
1699
{
1700
  struct babel_source *s;
1701
  struct babel_route *r;
1702
1703 5e8df049 Ondrej Zajicek (work)
  debug("Babel: Entry %N:\n", e->n.addr);
1704 937e75d8 Ondrej Zajicek (work)
1705
  WALK_LIST(s,e->sources)
1706
  { debug(" "); babel_dump_source(s); }
1707
1708
  WALK_LIST(r,e->routes)
1709
  {
1710
    debug(" ");
1711
    if (r == e->selected_out) debug("*");
1712
    if (r == e->selected_in) debug("+");
1713
    babel_dump_route(r);
1714
  }
1715
}
1716
1717
static void
1718
babel_dump_neighbor(struct babel_neighbor *n)
1719
{
1720
  debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n",
1721
        n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
1722
        n->hello_expiry ? n->hello_expiry - now : 0,
1723
        n->ihu_expiry ? n->ihu_expiry - now : 0);
1724
}
1725
1726
static void
1727
babel_dump_iface(struct babel_iface *ifa)
1728
{
1729
  struct babel_neighbor *n;
1730
1731 4324025f Ondrej Zajicek (work)
  debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d",
1732 937e75d8 Ondrej Zajicek (work)
        ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
1733
        ifa->cf->hello_interval, ifa->cf->update_interval);
1734 4324025f Ondrej Zajicek (work)
  debug(" next hop v4 %I next hop v6 %I\n", ifa->next_hop_ip4, ifa->next_hop_ip6);
1735 937e75d8 Ondrej Zajicek (work)
1736
  WALK_LIST(n, ifa->neigh_list)
1737
  { debug(" "); babel_dump_neighbor(n); }
1738
}
1739
1740
static void
1741
babel_dump(struct proto *P)
1742
{
1743
  struct babel_proto *p = (struct babel_proto *) P;
1744
  struct babel_iface *ifa;
1745
1746
  debug("Babel: router id %lR update seqno %d\n", p->router_id, p->update_seqno);
1747
1748
  WALK_LIST(ifa, p->interfaces)
1749
    babel_dump_iface(ifa);
1750
1751 4324025f Ondrej Zajicek (work)
  FIB_WALK(&p->ip4_rtable, struct babel_entry, e)
1752
  {
1753
    babel_dump_entry(e);
1754
  }
1755
  FIB_WALK_END;
1756
  FIB_WALK(&p->ip6_rtable, struct babel_entry, e)
1757 937e75d8 Ondrej Zajicek (work)
  {
1758 5e8df049 Ondrej Zajicek (work)
    babel_dump_entry(e);
1759 937e75d8 Ondrej Zajicek (work)
  }
1760
  FIB_WALK_END;
1761
}
1762
1763
static void
1764 3e236955 Jan Moskyto Matejka
babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
1765 937e75d8 Ondrej Zajicek (work)
{
1766
  buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id);
1767
}
1768
1769
static int
1770
babel_get_attr(eattr *a, byte *buf, int buflen UNUSED)
1771
{
1772
  switch (a->id)
1773
  {
1774
  case EA_BABEL_METRIC:
1775
    bsprintf(buf, "metric: %d", a->u.data);
1776
    return GA_FULL;
1777
1778
  case EA_BABEL_ROUTER_ID:
1779
  {
1780
    u64 rid = 0;
1781
    memcpy(&rid, a->u.ptr->data, sizeof(u64));
1782
    bsprintf(buf, "router_id: %lR", rid);
1783
    return GA_FULL;
1784
  }
1785
1786
  default:
1787
    return GA_UNKNOWN;
1788
  }
1789
}
1790
1791
void
1792
babel_show_interfaces(struct proto *P, char *iff)
1793
{
1794
  struct babel_proto *p = (void *) P;
1795
  struct babel_iface *ifa = NULL;
1796
  struct babel_neighbor *nbr = NULL;
1797
1798
  if (p->p.proto_state != PS_UP)
1799
  {
1800
    cli_msg(-1023, "%s: is not up", p->p.name);
1801
    cli_msg(0, "");
1802
    return;
1803
  }
1804
1805
  cli_msg(-1023, "%s:", p->p.name);
1806 4324025f Ondrej Zajicek (work)
  cli_msg(-1023, "%-10s %-6s %7s %6s %6s %-15s %s",
1807
          "Interface", "State", "RX cost", "Nbrs", "Timer",
1808
          "Next hop (v4)", "Next hop (v6)");
1809 937e75d8 Ondrej Zajicek (work)
1810
  WALK_LIST(ifa, p->interfaces)
1811
  {
1812
    if (iff && !patmatch(iff, ifa->iface->name))
1813
      continue;
1814
1815
    int nbrs = 0;
1816
    WALK_LIST(nbr, ifa->neigh_list)
1817
        nbrs++;
1818
1819
    int timer = MIN(ifa->next_regular, ifa->next_hello) - now;
1820 4324025f Ondrej Zajicek (work)
    cli_msg(-1023, "%-10s %-6s %7u %6u %6u %-15I %I",
1821
            ifa->iface->name, (ifa->up ? "Up" : "Down"),
1822
            ifa->cf->rxcost, nbrs, MAX(timer, 0),
1823
            ifa->next_hop_ip4, ifa->next_hop_ip6);
1824 937e75d8 Ondrej Zajicek (work)
  }
1825
1826
  cli_msg(0, "");
1827
}
1828
1829
void
1830
babel_show_neighbors(struct proto *P, char *iff)
1831
{
1832
  struct babel_proto *p = (void *) P;
1833
  struct babel_iface *ifa = NULL;
1834
  struct babel_neighbor *n = NULL;
1835
  struct babel_route *r = NULL;
1836
1837
  if (p->p.proto_state != PS_UP)
1838
  {
1839
    cli_msg(-1024, "%s: is not up", p->p.name);
1840
    cli_msg(0, "");
1841
    return;
1842
  }
1843
1844
  cli_msg(-1024, "%s:", p->p.name);
1845
  cli_msg(-1024, "%-25s %-10s %6s %6s %10s",
1846
          "IP address", "Interface", "Metric", "Routes", "Next hello");
1847
1848
  WALK_LIST(ifa, p->interfaces)
1849
  {
1850
    if (iff && !patmatch(iff, ifa->iface->name))
1851
      continue;
1852
1853
    WALK_LIST(n, ifa->neigh_list)
1854
    {
1855
      int rts = 0;
1856
      WALK_LIST(r, n->routes)
1857
        rts++;
1858
1859
      int timer = n->hello_expiry - now;
1860
      cli_msg(-1024, "%-25I %-10s %6u %6u %10u",
1861
              n->addr, ifa->iface->name, n->txcost, rts, MAX(timer, 0));
1862
    }
1863
  }
1864
1865
  cli_msg(0, "");
1866
}
1867
1868 4324025f Ondrej Zajicek (work)
static void
1869
babel_show_entries_(struct babel_proto *p, struct fib *rtable)
1870 937e75d8 Ondrej Zajicek (work)
{
1871
  struct babel_source *s = NULL;
1872
  struct babel_route *r = NULL;
1873
1874
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1875
1876 4324025f Ondrej Zajicek (work)
  FIB_WALK(rtable, struct babel_entry, e)
1877 937e75d8 Ondrej Zajicek (work)
  {
1878
    r = e->selected_in ? e->selected_in : e->selected_out;
1879
1880
    int srcs = 0;
1881
    WALK_LIST(s, e->sources)
1882
      srcs++;
1883
1884
    if (r)
1885
    {
1886
      if (r->router_id == p->router_id)
1887
        bsprintf(ridbuf, "%s", "<self>");
1888
      else
1889
        bsprintf(ridbuf, "%lR", r->router_id);
1890
1891
      int time = r->expires ? r->expires - now : 0;
1892 5e8df049 Ondrej Zajicek (work)
      cli_msg(-1025, "%-29N %-23s %6u %5u %7u %7u",
1893
              e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
1894 937e75d8 Ondrej Zajicek (work)
    }
1895
    else
1896
    {
1897 5e8df049 Ondrej Zajicek (work)
      cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs);
1898 937e75d8 Ondrej Zajicek (work)
    }
1899
  }
1900
  FIB_WALK_END;
1901 4324025f Ondrej Zajicek (work)
}
1902
1903
void
1904
babel_show_entries(struct proto *P)
1905
{
1906
  struct babel_proto *p = (void *) P;
1907
1908
  if (p->p.proto_state != PS_UP)
1909
  {
1910
    cli_msg(-1025, "%s: is not up", p->p.name);
1911
    cli_msg(0, "");
1912
    return;
1913
  }
1914
1915
  cli_msg(-1025, "%s:", p->p.name);
1916
  cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
1917
          "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
1918
1919
  babel_show_entries_(p, &p->ip4_rtable);
1920
  babel_show_entries_(p, &p->ip6_rtable);
1921 937e75d8 Ondrej Zajicek (work)
1922
  cli_msg(0, "");
1923
}
1924
1925
1926
/*
1927
 *        Babel protocol glue
1928
 */
1929
1930
/**
1931
 * babel_timer - global timer hook
1932
 * @t: Timer
1933
 *
1934
 * This function is called by the global protocol instance timer and handles
1935
 * expiration of routes and neighbours as well as pruning of the seqno request
1936
 * cache.
1937
 */
1938
static void
1939
babel_timer(timer *t)
1940
{
1941
  struct babel_proto *p = t->data;
1942
1943
  babel_expire_routes(p);
1944
  babel_expire_seqno_requests(p);
1945
  babel_expire_neighbors(p);
1946
}
1947
1948
static inline void
1949
babel_kick_timer(struct babel_proto *p)
1950
{
1951
  if (p->timer->expires > (now + 1))
1952
    tm_start(p->timer, 1);
1953
}
1954
1955
1956
static struct ea_list *
1957
babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id)
1958
{
1959
  struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr));
1960
  struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64));
1961
  rid->length = sizeof(u64);
1962
  memcpy(&rid->data, &router_id, sizeof(u64));
1963
1964
  l->next = next;
1965
  l->flags = EALF_SORTED;
1966
  l->count = 2;
1967
1968
  l->attrs[0].id = EA_BABEL_METRIC;
1969
  l->attrs[0].flags = 0;
1970
  l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
1971
  l->attrs[0].u.data = metric;
1972
1973
  l->attrs[1].id = EA_BABEL_ROUTER_ID;
1974
  l->attrs[1].flags = 0;
1975
  l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
1976
  l->attrs[1].u.ptr = rid;
1977
1978
  return l;
1979
}
1980
1981
1982
static int
1983
babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool)
1984
{
1985
  struct babel_proto *p = (void *) P;
1986
1987
  /* Prepare attributes with initial values */
1988
  if ((*rt)->attrs->source != RTS_BABEL)
1989
    *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
1990
1991
  return 0;
1992
}
1993
1994
static struct ea_list *
1995
babel_make_tmp_attrs(struct rte *rt, struct linpool *pool)
1996
{
1997
  return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id);
1998
}
1999
2000
static void
2001
babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs)
2002
{
2003
  rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
2004
}
2005
2006
/*
2007
 * babel_rt_notify - core tells us about new route (possibly our own),
2008
 * so store it into our data structures.
2009
 */
2010
static void
2011 5e8df049 Ondrej Zajicek (work)
babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net,
2012 3e236955 Jan Moskyto Matejka
                struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
2013 937e75d8 Ondrej Zajicek (work)
{
2014
  struct babel_proto *p = (void *) P;
2015
  struct babel_entry *e;
2016
  struct babel_route *r;
2017
2018
  if (new)
2019
  {
2020
    /* Update */
2021 5e8df049 Ondrej Zajicek (work)
    e = babel_get_entry(p, net->n.addr);
2022 937e75d8 Ondrej Zajicek (work)
2023
    if (new->attrs->src->proto != P)
2024
    {
2025
      r = babel_get_route(e, NULL);
2026
      r->seqno = p->update_seqno;
2027
      r->router_id = p->router_id;
2028
      r->metric = 0;        /* FIXME: should be selectable */
2029
    }
2030
    else
2031
      r = e->selected_in;
2032
2033
    if (r != e->selected_out)
2034
    {
2035
      e->selected_out = r;
2036
      e->updated = now;
2037
      babel_trigger_update(p);
2038
    }
2039
  }
2040
  else
2041
  {
2042
    /* Withdraw */
2043 5e8df049 Ondrej Zajicek (work)
    e = babel_find_entry(p, net->n.addr);
2044 937e75d8 Ondrej Zajicek (work)
    if (!e || !e->selected_out)
2045
      return;
2046
2047
    if (OUR_ROUTE(e->selected_out))
2048
    {
2049
      /*
2050
       * We originate this route, so set its metric to infinity and set an
2051
       * expiry time. This causes a retraction to be sent, and later the route
2052
       * to be flushed once the hold time has passed.
2053
       */
2054
      e->selected_out->metric = BABEL_INFINITY;
2055
      e->selected_out->expires = now + BABEL_HOLD_TIME;
2056
      e->updated = now;
2057
      babel_trigger_update(p);
2058
    }
2059
    else
2060
    {
2061
      /*
2062
       * This is a route originating from someone else that was lost; presumably
2063
       * because an export filter was updated to filter it. This means we can't
2064
       * set the metric to infinity (it would be overridden on subsequent
2065
       * updates from the peer originating the route), so just clear the
2066
       * exported route.
2067
       *
2068
       * This causes peers to expire the route after a while (like if we just
2069
       * shut down), but it's the best we can do in these circumstances; and
2070
       * since export filters presumably aren't updated that often this is
2071
       * acceptable.
2072
       */
2073
      e->selected_out = NULL;
2074
    }
2075
  }
2076
}
2077
2078
static int
2079
babel_rte_better(struct rte *new, struct rte *old)
2080
{
2081
  return new->u.babel.metric < old->u.babel.metric;
2082
}
2083
2084
static int
2085
babel_rte_same(struct rte *new, struct rte *old)
2086
{
2087
  return ((new->u.babel.router_id == old->u.babel.router_id) &&
2088
          (new->u.babel.metric == old->u.babel.metric));
2089
}
2090
2091
2092
static struct proto *
2093 5e8df049 Ondrej Zajicek (work)
babel_init(struct proto_config *CF)
2094 937e75d8 Ondrej Zajicek (work)
{
2095 5e8df049 Ondrej Zajicek (work)
  struct proto *P = proto_new(CF);
2096 4324025f Ondrej Zajicek (work)
  struct babel_proto *p = (void *) P;
2097 5e8df049 Ondrej Zajicek (work)
2098 4324025f Ondrej Zajicek (work)
  proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4));
2099
  proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6));
2100 937e75d8 Ondrej Zajicek (work)
2101
  P->if_notify = babel_if_notify;
2102
  P->rt_notify = babel_rt_notify;
2103
  P->import_control = babel_import_control;
2104
  P->make_tmp_attrs = babel_make_tmp_attrs;
2105
  P->store_tmp_attrs = babel_store_tmp_attrs;
2106
  P->rte_better = babel_rte_better;
2107
  P->rte_same = babel_rte_same;
2108
2109
  return P;
2110
}
2111
2112
static int
2113
babel_start(struct proto *P)
2114
{
2115
  struct babel_proto *p = (void *) P;
2116
  struct babel_config *cf = (void *) P->cf;
2117
2118 4324025f Ondrej Zajicek (work)
  fib_init(&p->ip4_rtable, P->pool, NET_IP4, sizeof(struct babel_entry),
2119 5e8df049 Ondrej Zajicek (work)
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2120 4324025f Ondrej Zajicek (work)
  fib_init(&p->ip6_rtable, P->pool, NET_IP6, sizeof(struct babel_entry),
2121
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2122
2123 937e75d8 Ondrej Zajicek (work)
  init_list(&p->interfaces);
2124
  p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1);
2125
  tm_start(p->timer, 2);
2126
  p->update_seqno = 1;
2127
  p->router_id = proto_get_router_id(&cf->c);
2128
2129
  p->route_slab = sl_new(P->pool, sizeof(struct babel_route));
2130
  p->source_slab = sl_new(P->pool, sizeof(struct babel_source));
2131
  p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node));
2132
  p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request));
2133
  init_list(&p->seqno_cache);
2134
2135
  p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 };
2136
2137
  return PS_UP;
2138
}
2139
2140 5d6ca220 Ondrej Zajicek (work)
static inline void
2141
babel_iface_shutdown(struct babel_iface *ifa)
2142
{
2143
  if (ifa->sk)
2144
  {
2145
    babel_send_wildcard_retraction(ifa);
2146
    babel_send_queue(ifa);
2147
  }
2148
}
2149
2150
static int
2151
babel_shutdown(struct proto *P)
2152
{
2153
  struct babel_proto *p = (void *) P;
2154
  struct babel_iface *ifa;
2155
2156
  TRACE(D_EVENTS, "Shutdown requested");
2157
2158
  WALK_LIST(ifa, p->interfaces)
2159
    babel_iface_shutdown(ifa);
2160
2161
  return PS_DOWN;
2162
}
2163
2164 937e75d8 Ondrej Zajicek (work)
static int
2165 5e8df049 Ondrej Zajicek (work)
babel_reconfigure(struct proto *P, struct proto_config *CF)
2166 937e75d8 Ondrej Zajicek (work)
{
2167
  struct babel_proto *p = (void *) P;
2168 5e8df049 Ondrej Zajicek (work)
  struct babel_config *new = (void *) CF;
2169 937e75d8 Ondrej Zajicek (work)
2170
  TRACE(D_EVENTS, "Reconfiguring");
2171
2172 4324025f Ondrej Zajicek (work)
  if (!proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4)) ||
2173
      !proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6)))
2174 5e8df049 Ondrej Zajicek (work)
    return 0;
2175
2176
  p->p.cf = CF;
2177 937e75d8 Ondrej Zajicek (work)
  babel_reconfigure_ifaces(p, new);
2178
2179
  babel_trigger_update(p);
2180
  babel_kick_timer(p);
2181
2182
  return 1;
2183
}
2184
2185
2186
struct protocol proto_babel = {
2187
  .name =                "Babel",
2188
  .template =                "babel%d",
2189
  .attr_class =                EAP_BABEL,
2190
  .preference =                DEF_PREF_BABEL,
2191 4324025f Ondrej Zajicek (work)
  .channel_mask =        NB_IP,
2192 5e8df049 Ondrej Zajicek (work)
  .proto_size =                sizeof(struct babel_proto),
2193 937e75d8 Ondrej Zajicek (work)
  .config_size =        sizeof(struct babel_config),
2194
  .init =                babel_init,
2195
  .dump =                babel_dump,
2196
  .start =                babel_start,
2197 5d6ca220 Ondrej Zajicek (work)
  .shutdown =                babel_shutdown,
2198 937e75d8 Ondrej Zajicek (work)
  .reconfigure =        babel_reconfigure,
2199
  .get_route_info =        babel_get_route_info,
2200
  .get_attr =                babel_get_attr
2201
};