Statistics
| Branch: | Revision:

iof-bird-daemon / proto / babel / babel.c @ 8b58f565

History | View | Annotate | Download (57 KB)

1
/*
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
static int  babel_cache_seqno_request(struct babel_proto *p, net_addr *n, u64 router_id, u16 seqno);
57
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
babel_init_entry(void *E)
70
{
71
  struct babel_entry *e = E;
72

    
73
  e->updated = current_time();
74
  init_list(&e->sources);
75
  init_list(&e->routes);
76
}
77

    
78
static inline struct babel_entry *
79
babel_find_entry(struct babel_proto *p, const net_addr *n)
80
{
81
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
82
  return fib_find(rtable, n);
83
}
84

    
85
static struct babel_entry *
86
babel_get_entry(struct babel_proto *p, const net_addr *n)
87
{
88
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
89
  struct babel_entry *e = fib_get(rtable, n);
90
  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 = current_time() + 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
  btime now_ = current_time();
131

    
132
  WALK_LIST_DELSAFE(n, nx, e->sources)
133
  {
134
    if (n->expires && n->expires <= now_)
135
    {
136
      rem_node(NODE n);
137
      sl_free(p->source_slab, n);
138
    }
139
  }
140
}
141

    
142
static struct babel_route *
143
babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
144
{
145
  struct babel_route *r;
146

    
147
  WALK_LIST(r, e->routes)
148
    if (r->neigh == n)
149
      return r;
150

    
151
  return NULL;
152
}
153

    
154
static struct babel_route *
155
babel_get_route(struct babel_entry *e, struct babel_neighbor *nbr)
156
{
157
  struct babel_proto *p = e->proto;
158
  struct babel_route *r = babel_find_route(e, nbr);
159

    
160
  if (r)
161
    return r;
162

    
163
  r = sl_alloc(p->route_slab);
164
  memset(r, 0, sizeof(*r));
165
  r->e = e;
166
  add_tail(&e->routes, NODE r);
167

    
168
  if (nbr)
169
  {
170
    r->neigh = nbr;
171
    r->expires = current_time() + BABEL_GARBAGE_INTERVAL;
172
    add_tail(&nbr->routes, NODE &r->neigh_route);
173
  }
174

    
175
  return r;
176
}
177

    
178
static void
179
babel_flush_route(struct babel_route *r)
180
{
181
  struct babel_proto *p = r->e->proto;
182

    
183
  DBG("Babel: Flush route %N router_id %lR neigh %I\n",
184
      r->e->n.addr, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE);
185

    
186
  rem_node(NODE r);
187

    
188
  if (r->neigh)
189
    rem_node(&r->neigh_route);
190

    
191
  if (r->e->selected_in == r)
192
    r->e->selected_in = NULL;
193

    
194
  if (r->e->selected_out == r)
195
    r->e->selected_out = NULL;
196

    
197
  sl_free(p->route_slab, r);
198
}
199

    
200
static void
201
babel_expire_route(struct babel_route *r)
202
{
203
  struct babel_proto *p = r->e->proto;
204
  struct babel_entry *e = r->e;
205

    
206
  TRACE(D_EVENTS, "Route expiry timer for %N router-id %lR fired",
207
        e->n.addr, r->router_id);
208

    
209
  if (r->metric < BABEL_INFINITY)
210
  {
211
    r->metric = BABEL_INFINITY;
212
    r->expires = current_time() + r->expiry_interval;
213
  }
214
  else
215
  {
216
    babel_flush_route(r);
217
  }
218
}
219

    
220
static void
221
babel_refresh_route(struct babel_route *r)
222
{
223
  if (!OUR_ROUTE(r) && (r == r->e->selected_in))
224
    babel_send_route_request(r->e, r->neigh);
225

    
226
  r->refresh_time = 0;
227
}
228

    
229
static void
230
babel_expire_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
231
{
232
  struct babel_route *r, *rx;
233
  struct fib_iterator fit;
234
  btime now_ = current_time();
235

    
236
  FIB_ITERATE_INIT(&fit, rtable);
237

    
238
loop:
239
  FIB_ITERATE_START(rtable, &fit, struct babel_entry, e)
240
  {
241
    int changed = 0;
242

    
243
    WALK_LIST_DELSAFE(r, rx, e->routes)
244
    {
245
      if (r->refresh_time && r->refresh_time <= now_)
246
        babel_refresh_route(r);
247

    
248
      if (r->expires && r->expires <= now_)
249
      {
250
        babel_expire_route(r);
251
        changed = 1;
252
      }
253
    }
254

    
255
    if (changed)
256
    {
257
      /*
258
       * We have to restart the iteration because there may be a cascade of
259
       * synchronous events babel_select_route() -> nest table change ->
260
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
261
       */
262

    
263
      FIB_ITERATE_PUT(&fit);
264
      babel_select_route(e);
265
      goto loop;
266
    }
267

    
268
    babel_expire_sources(e);
269

    
270
    /* Remove empty entries */
271
    if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes))
272
    {
273
      FIB_ITERATE_PUT(&fit);
274
      fib_delete(rtable, e);
275
      goto loop;
276
    }
277
  }
278
  FIB_ITERATE_END;
279
}
280

    
281
static void
282
babel_expire_routes(struct babel_proto *p)
283
{
284
  babel_expire_routes_(p, &p->ip4_rtable);
285
  babel_expire_routes_(p, &p->ip6_rtable);
286
}
287

    
288
static struct babel_neighbor *
289
babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
290
{
291
  struct babel_neighbor *nbr;
292

    
293
  WALK_LIST(nbr, ifa->neigh_list)
294
    if (ipa_equal(nbr->addr, addr))
295
      return nbr;
296

    
297
  return NULL;
298
}
299

    
300
static struct babel_neighbor *
301
babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
302
{
303
  struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);
304

    
305
  if (nbr)
306
    return nbr;
307

    
308
  nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
309
  nbr->ifa = ifa;
310
  nbr->addr = addr;
311
  nbr->txcost = BABEL_INFINITY;
312
  init_list(&nbr->routes);
313
  add_tail(&ifa->neigh_list, NODE nbr);
314

    
315
  return nbr;
316
}
317

    
318
static void
319
babel_flush_neighbor(struct babel_neighbor *nbr)
320
{
321
  struct babel_proto *p = nbr->ifa->proto;
322
  node *n;
323

    
324
  TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
325

    
326
  WALK_LIST_FIRST(n, nbr->routes)
327
  {
328
    struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n);
329
    struct babel_entry *e = r->e;
330
    int selected = (r == e->selected_in);
331

    
332
    babel_flush_route(r);
333

    
334
    if (selected)
335
      babel_select_route(e);
336
  }
337

    
338
  rem_node(NODE nbr);
339
  mb_free(nbr);
340
}
341

    
342
static void
343
babel_expire_ihu(struct babel_neighbor *nbr)
344
{
345
  nbr->txcost = BABEL_INFINITY;
346
}
347

    
348
static void
349
babel_expire_hello(struct babel_neighbor *nbr)
350
{
351
  nbr->hello_map <<= 1;
352

    
353
  if (nbr->hello_cnt < 16)
354
    nbr->hello_cnt++;
355

    
356
  if (!nbr->hello_map)
357
    babel_flush_neighbor(nbr);
358
}
359

    
360
static void
361
babel_expire_neighbors(struct babel_proto *p)
362
{
363
  struct babel_iface *ifa;
364
  struct babel_neighbor *nbr, *nbx;
365
  btime now_ = current_time();
366

    
367
  WALK_LIST(ifa, p->interfaces)
368
  {
369
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
370
    {
371
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now_)
372
        babel_expire_ihu(nbr);
373

    
374
      if (nbr->hello_expiry && nbr->hello_expiry <= now_)
375
        babel_expire_hello(nbr);
376
    }
377
  }
378
}
379

    
380

    
381
/*
382
 *        Best route selection
383
 */
384

    
385
/*
386
 * From the RFC (section 3.5.1):
387
 *
388
 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
389
 * metric) is feasible if one of the following conditions holds:
390
 *
391
 * - metric is infinite; or
392
 *
393
 * - no entry exists in the source table indexed by (id, prefix, plen); or
394
 *
395
 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
396
 *   table, and either
397
 *   - seqno' < seqno or
398
 *   - seqno = seqno' and metric < metric'.
399
 */
400
static inline int
401
babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
402
{
403
  return !s ||
404
    (metric == BABEL_INFINITY) ||
405
    (seqno > s->seqno) ||
406
    ((seqno == s->seqno) && (metric < s->metric));
407
}
408

    
409
static u16
410
babel_compute_rxcost(struct babel_neighbor *n)
411
{
412
  struct babel_iface *ifa = n->ifa;
413
  u8 cnt, missed;
414
  u16 map=n->hello_map;
415

    
416
  if (!map) return BABEL_INFINITY;
417
  cnt = u32_popcount(map); // number of bits set
418
  missed = n->hello_cnt-cnt;
419

    
420
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
421
  {
422
    /* ETX - Appendix 2.2 in the RFC.
423

424
       beta = prob. of successful transmission.
425
       rxcost = BABEL_RXCOST_WIRELESS/beta
426

427
       Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
428
       Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
429
   */
430
    if (!cnt) return BABEL_INFINITY;
431
    return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt;
432
  }
433
  else
434
  {
435
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
436
    DBG("Babel: Missed %d hellos from %I\n", missed, n->addr);
437
    /* Link is bad if more than half the expected hellos were lost */
438
    return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost;
439
  }
440
}
441

    
442

    
443
static u16
444
babel_compute_cost(struct babel_neighbor *n)
445
{
446
  struct babel_iface *ifa = n->ifa;
447
  u16 rxcost = babel_compute_rxcost(n);
448
  if (rxcost == BABEL_INFINITY) return rxcost;
449
  else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
450
  {
451
    /* ETX - Appendix 2.2 in the RFC */
452
    return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS;
453
  }
454
  else
455
  {
456
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
457
    return n->txcost;
458
  }
459
}
460

    
461
/* Simple additive metric - Appendix 3.1 in the RFC */
462
static u16
463
babel_compute_metric(struct babel_neighbor *n, uint metric)
464
{
465
  metric += babel_compute_cost(n);
466
  return MIN(metric, BABEL_INFINITY);
467
}
468

    
469

    
470
/**
471
 * babel_announce_rte - announce selected route to the core
472
 * @p: Babel protocol instance
473
 * @e: Babel route entry to announce
474
 *
475
 * This function announces a Babel entry to the core if it has a selected
476
 * incoming path, and retracts it otherwise. If the selected entry has infinite
477
 * metric, the route is announced as unreachable.
478
 */
479
static void
480
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
481
{
482
  struct babel_route *r = e->selected_in;
483
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
484

    
485
  if (r)
486
  {
487
    rta *ap0 = allocz(RTA_MAX_SIZE);
488
    *ap0 = (rta) {
489
      .src = p->p.main_source,
490
      .source = RTS_BABEL,
491
      .scope = SCOPE_UNIVERSE,
492
      .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_UNICAST,
493
      .from = r->neigh->addr,
494
      .nh.iface = r->neigh->ifa->iface,
495
    };
496

    
497
    if (r->metric < BABEL_INFINITY)
498
      ap0->nh.gw = r->next_hop;
499

    
500
    rta *a = rta_lookup(ap0);
501
    rte *rte = rte_get_temp(a);
502
    rte->u.babel.metric = r->metric;
503
    rte->u.babel.router_id = r->router_id;
504
    rte->pflags = 0;
505

    
506
    rte_update2(c, e->n.addr, rte, p->p.main_source);
507
  }
508
  else
509
  {
510
    /* Retraction */
511
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
512
  }
513
}
514

    
515
/**
516
 * babel_select_route - select best route for given route entry
517
 * @e: Babel entry to select the best route for
518
 *
519
 * Select the best feasible route for a given prefix among the routes received
520
 * from peers, and propagate it to the nest. This just selects the feasible
521
 * route with the lowest metric.
522
 *
523
 * If no feasible route is available for a prefix that previously had a route
524
 * selected, a seqno request is sent to try to get a valid route. In the
525
 * meantime, the route is marked as infeasible in the nest (to blackhole packets
526
 * going to it, as per the RFC).
527
 *
528
 * If no feasible route is available, and no previous route is selected, the
529
 * route is removed from the nest entirely.
530
 */
531
static void
532
babel_select_route(struct babel_entry *e)
533
{
534
  struct babel_proto *p = e->proto;
535
  struct babel_route *r, *cur = e->selected_in;
536

    
537
  /* try to find the best feasible route */
538
  WALK_LIST(r, e->routes)
539
    if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */
540
        (!cur || r->metric < cur->metric) &&
541
        babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
542
      cur = r;
543

    
544
  if (cur && !OUR_ROUTE(cur) &&
545
      ((!e->selected_in && cur->metric < BABEL_INFINITY) ||
546
       (e->selected_in && cur->metric < e->selected_in->metric)))
547
  {
548
    TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
549
          e->n.addr, cur->router_id, cur->metric);
550

    
551
    e->selected_in = cur;
552
    e->updated = current_time();
553
    babel_announce_rte(p, e);
554
  }
555
  else if (!cur || cur->metric == BABEL_INFINITY)
556
  {
557
    /* Couldn't find a feasible route. If we have a selected route, that means
558
       it just became infeasible; so set it's metric to infinite and install it
559
       (as unreachable), then send a seqno request.
560

561
       babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
562
    if (e->selected_in)
563
    {
564
      TRACE(D_EVENTS, "Lost feasible route for prefix %N",
565
            e->n.addr);
566

    
567
      e->selected_in->metric = BABEL_INFINITY;
568
      e->updated = current_time();
569

    
570
      babel_send_seqno_request(e);
571
      babel_announce_rte(p, e);
572

    
573
      /* Section 3.6 of the RFC forbids an infeasible from being selected. This
574
         is cleared after announcing the route to the core to make sure an
575
         unreachable route is propagated first. */
576
      e->selected_in = NULL;
577
    }
578
    else
579
    {
580
      /* No route currently selected, and no new one selected; this means we
581
         don't have a route to this destination anymore (and were probably
582
         called from an expiry timer). Remove the route from the nest. */
583
      TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
584

    
585
      e->selected_in = NULL;
586
      e->updated = current_time();
587
      babel_announce_rte(p, e);
588
    }
589
  }
590
}
591

    
592
/*
593
 *        Functions to send replies
594
 */
595

    
596
static void
597
babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
598
{
599
  struct babel_proto *p = ifa->proto;
600
  union babel_msg msg = {};
601

    
602
  TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce);
603

    
604
  msg.type = BABEL_TLV_ACK;
605
  msg.ack.nonce = nonce;
606

    
607
  babel_send_unicast(&msg, ifa, dest);
608
}
609

    
610
static void
611
babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
612
{
613
  struct babel_proto *p = ifa->proto;
614

    
615
  msg->type = BABEL_TLV_IHU;
616
  msg->ihu.addr = n->addr;
617
  msg->ihu.rxcost = babel_compute_rxcost(n);
618
  msg->ihu.interval = ifa->cf->ihu_interval;
619

    
620
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %t",
621
        msg->ihu.addr, msg->ihu.rxcost, (btime) msg->ihu.interval);
622
}
623

    
624
static void
625
babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
626
{
627
  union babel_msg msg = {};
628
  babel_build_ihu(&msg, ifa, n);
629
  babel_send_unicast(&msg, ifa, n->addr);
630
}
631

    
632
static void
633
babel_send_ihus(struct babel_iface *ifa)
634
{
635
  struct babel_neighbor *n;
636
  WALK_LIST(n, ifa->neigh_list)
637
  {
638
    union babel_msg msg = {};
639
    babel_build_ihu(&msg, ifa, n);
640
    babel_enqueue(&msg, ifa);
641
  }
642
}
643

    
644
static void
645
babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
646
{
647
  struct babel_proto *p = ifa->proto;
648
  union babel_msg msg = {};
649

    
650
  msg.type = BABEL_TLV_HELLO;
651
  msg.hello.seqno = ifa->hello_seqno++;
652
  msg.hello.interval = ifa->cf->hello_interval;
653

    
654
  TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %t",
655
        ifa->ifname, msg.hello.seqno, (btime) msg.hello.interval);
656

    
657
  babel_enqueue(&msg, ifa);
658

    
659
  if (send_ihu)
660
    babel_send_ihus(ifa);
661
}
662

    
663
static void
664
babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n)
665
{
666
  struct babel_proto *p = e->proto;
667
  struct babel_iface *ifa = n->ifa;
668
  union babel_msg msg = {};
669

    
670
  TRACE(D_PACKETS, "Sending route request for %N to %I",
671
        e->n.addr, n->addr);
672

    
673
  msg.type = BABEL_TLV_ROUTE_REQUEST;
674
  net_copy(&msg.route_request.net, e->n.addr);
675

    
676
  babel_send_unicast(&msg, ifa, n->addr);
677
}
678

    
679
static void
680
babel_send_wildcard_request(struct babel_iface *ifa)
681
{
682
  struct babel_proto *p = ifa->proto;
683
  union babel_msg msg = {};
684

    
685
  TRACE(D_PACKETS, "Sending wildcard route request on %s",
686
        ifa->ifname);
687

    
688
  msg.type = BABEL_TLV_ROUTE_REQUEST;
689
  msg.route_request.full = 1;
690

    
691
  babel_enqueue(&msg, ifa);
692
}
693

    
694
static void
695
babel_send_seqno_request(struct babel_entry *e)
696
{
697
  struct babel_proto *p = e->proto;
698
  struct babel_route *r = e->selected_in;
699
  struct babel_iface *ifa = NULL;
700
  struct babel_source *s = NULL;
701
  union babel_msg msg = {};
702

    
703
  s = babel_find_source(e, r->router_id);
704
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
705
    return;
706

    
707
  TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d",
708
        e->n.addr, r->router_id, s->seqno + 1);
709

    
710
  msg.type = BABEL_TLV_SEQNO_REQUEST;
711
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
712
  msg.seqno_request.seqno = s->seqno + 1;
713
  msg.seqno_request.router_id = r->router_id;
714
  net_copy(&msg.seqno_request.net, e->n.addr);
715

    
716
  WALK_LIST(ifa, p->interfaces)
717
    babel_enqueue(&msg, ifa);
718
}
719

    
720
static void
721
babel_unicast_seqno_request(struct babel_route *r)
722
{
723
  struct babel_entry *e = r->e;
724
  struct babel_proto *p = e->proto;
725
  struct babel_iface *ifa = r->neigh->ifa;
726
  struct babel_source *s = NULL;
727
  union babel_msg msg = {};
728

    
729
  s = babel_find_source(e, r->router_id);
730
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
731
    return;
732

    
733
  TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d",
734
        e->n.addr, r->router_id, s->seqno + 1);
735

    
736
  msg.type = BABEL_TLV_SEQNO_REQUEST;
737
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
738
  msg.seqno_request.seqno = s->seqno + 1;
739
  msg.seqno_request.router_id = r->router_id;
740
  net_copy(&msg.seqno_request.net, e->n.addr);
741

    
742
  babel_send_unicast(&msg, ifa, r->neigh->addr);
743
}
744

    
745
/**
746
 * babel_send_update - send route table updates
747
 * @ifa: Interface to transmit on
748
 * @changed: Only send entries changed since this time
749
 *
750
 * This function produces update TLVs for all entries changed since the time
751
 * indicated by the &changed parameter and queues them for transmission on the
752
 * selected interface. During the process, the feasibility distance for each
753
 * transmitted entry is updated.
754
 */
755
static void
756
babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable)
757
{
758
  struct babel_proto *p = ifa->proto;
759

    
760
  FIB_WALK(rtable, struct babel_entry, e)
761
  {
762
    struct babel_route *r = e->selected_out;
763

    
764
    if (!r)
765
      continue;
766

    
767
    /* Our own seqno might have changed, in which case we update the routes we
768
       originate. */
769
    if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno))
770
    {
771
      r->seqno = p->update_seqno;
772
      e->updated = current_time();
773
    }
774

    
775
    /* Skip routes that weren't updated since 'changed' time */
776
    if (e->updated < changed)
777
      continue;
778

    
779
    TRACE(D_PACKETS, "Sending update for %N router-id %lR seqno %d metric %d",
780
          e->n.addr, r->router_id, r->seqno, r->metric);
781

    
782
    union babel_msg msg = {};
783
    msg.type = BABEL_TLV_UPDATE;
784
    msg.update.interval = ifa->cf->update_interval;
785
    msg.update.seqno = r->seqno;
786
    msg.update.metric = r->metric;
787
    msg.update.router_id = r->router_id;
788
    net_copy(&msg.update.net, e->n.addr);
789

    
790
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
791
                           ifa->next_hop_ip4 : ifa->next_hop_ip6);
792

    
793
    babel_enqueue(&msg, ifa);
794

    
795
    /* Update feasibility distance for redistributed routes */
796
    if (!OUR_ROUTE(r))
797
    {
798
      struct babel_source *s = babel_get_source(e, r->router_id);
799
      s->expires = current_time() + BABEL_GARBAGE_INTERVAL;
800

    
801
      if ((msg.update.seqno > s->seqno) ||
802
          ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
803
      {
804
        s->seqno = msg.update.seqno;
805
        s->metric = msg.update.metric;
806
      }
807
    }
808
  }
809
  FIB_WALK_END;
810
}
811

    
812
static void
813
babel_send_update(struct babel_iface *ifa, btime changed)
814
{
815
  struct babel_proto *p = ifa->proto;
816

    
817
  babel_send_update_(ifa, changed, &p->ip4_rtable);
818
  babel_send_update_(ifa, changed, &p->ip6_rtable);
819
}
820

    
821
static void
822
babel_trigger_iface_update(struct babel_iface *ifa)
823
{
824
  struct babel_proto *p = ifa->proto;
825

    
826
  /* Interface not active or already scheduled */
827
  if (!ifa->up || ifa->want_triggered)
828
    return;
829

    
830
  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
831
        ifa->iface->name, p->update_seqno);
832

    
833
  ifa->want_triggered = current_time();
834
  babel_iface_kick_timer(ifa);
835
}
836

    
837
/* Sends and update on all interfaces. */
838
static void
839
babel_trigger_update(struct babel_proto *p)
840
{
841
  if (p->triggered)
842
    return;
843

    
844
  struct babel_iface *ifa;
845
  WALK_LIST(ifa, p->interfaces)
846
    babel_trigger_iface_update(ifa);
847

    
848
  p->triggered = 1;
849
}
850

    
851
/* A retraction is an update with an infinite metric */
852
static void
853
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
854
{
855
  struct babel_proto *p = ifa->proto;
856
  union babel_msg msg = {};
857

    
858
  TRACE(D_PACKETS, "Sending retraction for %N seqno %d", n, p->update_seqno);
859

    
860
  msg.type = BABEL_TLV_UPDATE;
861
  msg.update.interval = ifa->cf->update_interval;
862
  msg.update.seqno = p->update_seqno;
863
  msg.update.metric = BABEL_INFINITY;
864
  msg.update.net = *n;
865

    
866
  babel_enqueue(&msg, ifa);
867
}
868

    
869
static void
870
babel_send_wildcard_retraction(struct babel_iface *ifa)
871
{
872
  struct babel_proto *p = ifa->proto;
873
  union babel_msg msg = {};
874

    
875
  TRACE(D_PACKETS, "Sending wildcard retraction on %s", ifa->ifname);
876

    
877
  msg.type = BABEL_TLV_UPDATE;
878
  msg.update.wildcard = 1;
879
  msg.update.interval = ifa->cf->update_interval;
880
  msg.update.seqno = p->update_seqno;
881
  msg.update.metric = BABEL_INFINITY;
882

    
883
  babel_enqueue(&msg, ifa);
884
}
885

    
886

    
887
/*
888
 *        TLV handler helpers
889
 */
890

    
891
/* Update hello history according to Appendix A1 of the RFC */
892
static void
893
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
894
{
895
  /*
896
   * Compute the difference between expected and received seqno (modulo 2^16).
897
   * If the expected and received seqnos are within 16 of each other, the modular
898
   * difference is going to be less than 16 for one of the directions. Otherwise,
899
   * the values differ too much, so just reset the state.
900
   */
901

    
902
  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
903

    
904
  if (delta == 0)
905
  {
906
    /* Do nothing */
907
  }
908
  else if (delta <= 16)
909
  {
910
    /* Sending node decreased interval; fast-forward */
911
    n->hello_map <<= delta;
912
    n->hello_cnt = MIN(n->hello_cnt + delta, 16);
913
  }
914
  else if (delta >= 0xfff0)
915
  {
916
    u8 diff = (0xffff - delta);
917
    /* Sending node increased interval; undo history */
918
    n->hello_map >>= diff;
919
    n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
920
  }
921
  else
922
  {
923
    /* Note state reset - flush entries */
924
    n->hello_map = n->hello_cnt = 0;
925
  }
926

    
927
  /* Current entry */
928
  n->hello_map = (n->hello_map << 1) | 1;
929
  n->next_hello_seqno = seqno+1;
930
  if (n->hello_cnt < 16) n->hello_cnt++;
931
  n->hello_expiry = current_time() + BABEL_HELLO_EXPIRY_FACTOR(interval);
932
}
933

    
934
static void
935
babel_expire_seqno_requests(struct babel_proto *p)
936
{
937
  btime now_ = current_time();
938

    
939
  struct babel_seqno_request *n, *nx;
940
  WALK_LIST_DELSAFE(n, nx, p->seqno_cache)
941
  {
942
    if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now_)
943
    {
944
      rem_node(NODE n);
945
      sl_free(p->seqno_slab, n);
946
    }
947
  }
948
}
949

    
950
/*
951
 * Checks the seqno request cache for a matching request and returns failure if
952
 * found. Otherwise, a new entry is stored in the cache.
953
 */
954
static int
955
babel_cache_seqno_request(struct babel_proto *p, net_addr *n,
956
                          u64 router_id, u16 seqno)
957
{
958
  struct babel_seqno_request *r;
959

    
960
  WALK_LIST(r, p->seqno_cache)
961
  {
962
    if (net_equal(&r->net, n) && (r->router_id == router_id) && (r->seqno == seqno))
963
      return 0;
964
  }
965

    
966
  /* no entries found */
967
  r = sl_alloc(p->seqno_slab);
968
  net_copy(&r->net, n);
969
  r->router_id = router_id;
970
  r->seqno = seqno;
971
  r->updated = current_time();
972
  add_tail(&p->seqno_cache, NODE r);
973

    
974
  return 1;
975
}
976

    
977
static void
978
babel_forward_seqno_request(struct babel_entry *e,
979
                            struct babel_msg_seqno_request *in,
980
                            ip_addr sender)
981
{
982
  struct babel_proto *p = e->proto;
983
  struct babel_route *r;
984

    
985
  TRACE(D_PACKETS, "Forwarding seqno request for %N router-id %lR seqno %d",
986
        e->n.addr, in->router_id, in->seqno);
987

    
988
  WALK_LIST(r, e->routes)
989
  {
990
    if ((r->router_id == in->router_id) &&
991
        !OUR_ROUTE(r) &&
992
        !ipa_equal(r->neigh->addr, sender))
993
    {
994
      if (!babel_cache_seqno_request(p, e->n.addr, in->router_id, in->seqno))
995
        return;
996

    
997
      union babel_msg msg = {};
998
      msg.type = BABEL_TLV_SEQNO_REQUEST;
999
      msg.seqno_request.hop_count = in->hop_count-1;
1000
      msg.seqno_request.seqno = in->seqno;
1001
      msg.seqno_request.router_id = in->router_id;
1002
      net_copy(&msg.seqno_request.net, e->n.addr);
1003

    
1004
      babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr);
1005
      return;
1006
    }
1007
  }
1008
}
1009

    
1010

    
1011
/*
1012
 *        TLV handlers
1013
 */
1014

    
1015
void
1016
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
1017
{
1018
  struct babel_proto *p = ifa->proto;
1019
  struct babel_msg_ack_req *msg = &m->ack_req;
1020

    
1021
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %t",
1022
        msg->nonce, (btime) msg->interval);
1023

    
1024
  babel_send_ack(ifa, msg->sender, msg->nonce);
1025
}
1026

    
1027
void
1028
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
1029
{
1030
  struct babel_proto *p = ifa->proto;
1031
  struct babel_msg_hello *msg = &m->hello;
1032

    
1033
  TRACE(D_PACKETS, "Handling hello seqno %d interval %t",
1034
        msg->seqno, (btime) msg->interval);
1035

    
1036
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1037
  babel_update_hello_history(n, msg->seqno, msg->interval);
1038
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
1039
    babel_send_ihu(ifa, n);
1040
}
1041

    
1042
void
1043
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
1044
{
1045
  struct babel_proto *p = ifa->proto;
1046
  struct babel_msg_ihu *msg = &m->ihu;
1047

    
1048
  /* Ignore IHUs that are not about us */
1049
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
1050
    return;
1051

    
1052
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %t",
1053
        msg->rxcost, (btime) msg->interval);
1054

    
1055
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1056
  n->txcost = msg->rxcost;
1057
  n->ihu_expiry = current_time() + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1058
}
1059

    
1060
/**
1061
 * babel_handle_update - handle incoming route updates
1062
 * @m: Incoming update TLV
1063
 * @ifa: Interface the update was received on
1064
 *
1065
 * This function is called as a handler for update TLVs and handles the updating
1066
 * and maintenance of route entries in Babel's internal routing cache. The
1067
 * handling follows the actions described in the Babel RFC, and at the end of
1068
 * each update handling, babel_select_route() is called on the affected entry to
1069
 * optionally update the selected routes and propagate them to the core.
1070
 */
1071
void
1072
babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
1073
{
1074
  struct babel_proto *p = ifa->proto;
1075
  struct babel_msg_update *msg = &m->update;
1076

    
1077
  struct babel_neighbor *nbr;
1078
  struct babel_entry *e;
1079
  struct babel_source *s;
1080
  struct babel_route *r;
1081
  node *n;
1082
  int feasible;
1083

    
1084
  if (msg->wildcard)
1085
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
1086
  else
1087
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
1088
          &msg->net, msg->seqno, msg->metric);
1089

    
1090
  nbr = babel_find_neighbor(ifa, msg->sender);
1091
  if (!nbr)
1092
  {
1093
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
1094
    return;
1095
  }
1096

    
1097
  if (msg->router_id == p->router_id)
1098
  {
1099
    DBG("Babel: Ignoring update for our own router ID.\n");
1100
    return;
1101
  }
1102

    
1103
  struct channel *c = (msg->net.type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
1104
  if (!c || (c->channel_state != CS_UP))
1105
  {
1106
    DBG("Babel: Ignoring update for inactive address family.\n");
1107
    return;
1108
  }
1109

    
1110
  /*
1111
   * RFC section 3.5.4:
1112
   *
1113
   * When a Babel node receives an update (id, prefix, seqno, metric) from a
1114
   * neighbour neigh with a link cost value equal to cost, it checks whether it
1115
   * already has a routing table entry indexed by (neigh, id, prefix).
1116
   *
1117
   * If no such entry exists:
1118
   *
1119
   * o if the update is unfeasible, it is ignored;
1120
   *
1121
   * o if the metric is infinite (the update is a retraction), the update is
1122
   *   ignored;
1123
   *
1124
   * o otherwise, a new route table entry is created, indexed by (neigh, id,
1125
   *   prefix), with seqno equal to seqno and an advertised metric equal to the
1126
   *   metric carried by the update.
1127
   *
1128
   * If such an entry exists:
1129
   *
1130
   * o if the entry is currently installed and the update is unfeasible, then
1131
   *   the behaviour depends on whether the router-ids of the two entries match.
1132
   *   If the router-ids are different, the update is treated as though it were
1133
   *   a retraction (i.e., as though the metric were FFFF hexadecimal). If the
1134
   *   router-ids are equal, the update is ignored;
1135
   *
1136
   * o otherwise (i.e., if either the update is feasible or the entry is not
1137
   *   currently installed), then the entry's sequence number, advertised
1138
   *   metric, metric, and router-id are updated and, unless the advertised
1139
   *   metric is infinite, the route's expiry timer is reset to a small multiple
1140
   *   of the Interval value included in the update.
1141
   */
1142

    
1143
  /* Retraction */
1144
  if (msg->metric == BABEL_INFINITY)
1145
  {
1146
    if (msg->wildcard)
1147
    {
1148
      /*
1149
       * Special case: This is a retraction of all prefixes announced by this
1150
       * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
1151
       */
1152
      WALK_LIST(n, nbr->routes)
1153
      {
1154
        r = SKIP_BACK(struct babel_route, neigh_route, n);
1155
        r->metric = BABEL_INFINITY;
1156
        babel_select_route(r->e);
1157
      }
1158
    }
1159
    else
1160
    {
1161
      e = babel_find_entry(p, &msg->net);
1162

    
1163
      if (!e)
1164
        return;
1165

    
1166
      /* The route entry indexed by neighbour */
1167
      r = babel_find_route(e, nbr);
1168

    
1169
      if (!r)
1170
        return;
1171

    
1172
      r->metric = BABEL_INFINITY;
1173
      babel_select_route(e);
1174
    }
1175

    
1176
    /* Done with retractions */
1177
    return;
1178
  }
1179

    
1180
  e = babel_get_entry(p, &msg->net);
1181
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1182
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1183
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1184

    
1185
  if (!r)
1186
  {
1187
    if (!feasible)
1188
      return;
1189

    
1190
    r = babel_get_route(e, nbr);
1191
    r->advert_metric = msg->metric;
1192
    r->router_id = msg->router_id;
1193
    r->metric = babel_compute_metric(nbr, msg->metric);
1194
    r->next_hop = msg->next_hop;
1195
    r->seqno = msg->seqno;
1196
  }
1197
  else if (r == r->e->selected_in && !feasible)
1198
  {
1199
    /*
1200
     * Route is installed and update is infeasible - we may lose the route,
1201
     * so send a unicast seqno request (section 3.8.2.2 second paragraph).
1202
     */
1203
    babel_unicast_seqno_request(r);
1204

    
1205
    if (msg->router_id == r->router_id)
1206
      return;
1207

    
1208
    /* Treat as retraction */
1209
    r->metric = BABEL_INFINITY;
1210
  }
1211
  else
1212
  {
1213
    /* Last paragraph above - update the entry */
1214
    r->advert_metric = msg->metric;
1215
    r->metric = babel_compute_metric(nbr, msg->metric);
1216
    r->next_hop = msg->next_hop;
1217

    
1218
    r->router_id = msg->router_id;
1219
    r->seqno = msg->seqno;
1220

    
1221
    r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1222
    r->expires = current_time() + r->expiry_interval;
1223
    if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
1224
      r->refresh_time = current_time() + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
1225

    
1226
    /* If the route is not feasible at this point, it means it is from another
1227
       neighbour than the one currently selected; so send a unicast seqno
1228
       request to try to get a better route (section 3.8.2.2 last paragraph). */
1229
    if (!feasible)
1230
      babel_unicast_seqno_request(r);
1231
  }
1232

    
1233
  babel_select_route(e);
1234
}
1235

    
1236
void
1237
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
1238
{
1239
  struct babel_proto *p = ifa->proto;
1240
  struct babel_msg_route_request *msg = &m->route_request;
1241

    
1242
  /* RFC 6126 3.8.1.1 */
1243

    
1244
  /* Wildcard request - full update on the interface */
1245
  if (msg->full)
1246
  {
1247
    TRACE(D_PACKETS, "Handling wildcard route request");
1248
    ifa->want_triggered = 1;
1249
    return;
1250
  }
1251

    
1252
  TRACE(D_PACKETS, "Handling route request for %N", &msg->net);
1253

    
1254
  /* Non-wildcard request - see if we have an entry for the route.
1255
     If not, send a retraction, otherwise send an update. */
1256
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1257
  if (!e)
1258
  {
1259
    babel_send_retraction(ifa, &msg->net);
1260
  }
1261
  else
1262
  {
1263
    babel_trigger_iface_update(ifa);
1264
    e->updated = current_time();
1265
  }
1266
}
1267

    
1268

    
1269
void
1270
babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
1271
{
1272
  struct babel_proto *p = ifa->proto;
1273
  struct babel_msg_seqno_request *msg = &m->seqno_request;
1274

    
1275
  /* RFC 6126 3.8.1.2 */
1276

    
1277
  TRACE(D_PACKETS, "Handling seqno request for %N router-id %lR seqno %d hop count %d",
1278
        &msg->net, msg->router_id, msg->seqno, msg->hop_count);
1279

    
1280
  /* Ignore if we have no such entry or entry has infinite metric */
1281
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1282
  if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
1283
    return;
1284

    
1285
  /* Trigger update on incoming interface if we have a selected route with
1286
     different router id or seqno no smaller than requested */
1287
  struct babel_route *r = e->selected_out;
1288
  if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno))
1289
  {
1290
    babel_trigger_iface_update(ifa);
1291
    e->updated = current_time();
1292
    return;
1293
  }
1294

    
1295
  /* Seqno is larger; check if we own the router id */
1296
  if (msg->router_id == p->router_id)
1297
  {
1298
    /* Ours; update seqno and trigger global update */
1299
    p->update_seqno++;
1300
    babel_trigger_update(p);
1301
  }
1302
  else
1303
  {
1304
    /* Not ours; forward if TTL allows it */
1305
    if (msg->hop_count > 1)
1306
      babel_forward_seqno_request(e, msg, msg->sender);
1307
  }
1308
}
1309

    
1310

    
1311
/*
1312
 *        Babel interfaces
1313
 */
1314

    
1315
/**
1316
 * babel_iface_timer - Babel interface timer handler
1317
 * @t: Timer
1318
 *
1319
 * This function is called by the per-interface timer and triggers sending of
1320
 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1321
 * and updates are simply handled by setting the next_{hello,regular} variables
1322
 * on the interface, and triggering an update (and resetting the variable)
1323
 * whenever 'now' exceeds that value.
1324
 *
1325
 * For triggered updates, babel_trigger_iface_update() will set the
1326
 * want_triggered field on the interface to a timestamp value. If this is set
1327
 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1328
 * babel_send_update() will be called with this timestamp as the second
1329
 * parameter. This causes updates to be send consisting of only the routes that
1330
 * have changed since the time saved in want_triggered.
1331
 *
1332
 * Mostly when an update is triggered, the route being modified will be set to
1333
 * the value of 'now' at the time of the trigger; the >= comparison for
1334
 * selecting which routes to send in the update will make sure this is included.
1335
 */
1336
static void
1337
babel_iface_timer(timer *t)
1338
{
1339
  struct babel_iface *ifa = t->data;
1340
  struct babel_proto *p = ifa->proto;
1341
  btime hello_period = ifa->cf->hello_interval;
1342
  btime update_period = ifa->cf->update_interval;
1343
  btime now_ = current_time();
1344

    
1345
  if (now_ >= ifa->next_hello)
1346
  {
1347
    babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
1348
                           ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
1349
    ifa->next_hello += hello_period * (1 + (now_ - ifa->next_hello) / hello_period);
1350
  }
1351

    
1352
  if (now_ >= ifa->next_regular)
1353
  {
1354
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
1355
    babel_send_update(ifa, 0);
1356
    ifa->next_regular += update_period * (1 + (now_ - ifa->next_regular) / update_period);
1357
    ifa->want_triggered = 0;
1358
    p->triggered = 0;
1359
  }
1360
  else if (ifa->want_triggered && (now_ >= ifa->next_triggered))
1361
  {
1362
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
1363
    babel_send_update(ifa, ifa->want_triggered);
1364
    ifa->next_triggered = now_ + MIN(5 S, update_period / 2);
1365
    ifa->want_triggered = 0;
1366
    p->triggered = 0;
1367
  }
1368

    
1369
  btime next_event = MIN(ifa->next_hello, ifa->next_regular);
1370
  if (ifa->want_triggered) next_event = MIN(next_event, ifa->next_triggered);
1371
  tm2_set(ifa->timer, next_event);
1372
}
1373

    
1374
static inline void
1375
babel_iface_kick_timer(struct babel_iface *ifa)
1376
{
1377
  if (ifa->timer->expires > (current_time() + 100 MS))
1378
    tm2_start(ifa->timer, 100 MS);
1379
}
1380

    
1381
static void
1382
babel_iface_start(struct babel_iface *ifa)
1383
{
1384
  struct babel_proto *p = ifa->proto;
1385

    
1386
  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
1387

    
1388
  ifa->next_hello = current_time() + (random() % ifa->cf->hello_interval);
1389
  ifa->next_regular = current_time() + (random() % ifa->cf->update_interval);
1390
  ifa->next_triggered = current_time() + MIN(5 S, ifa->cf->update_interval / 2);
1391
  ifa->want_triggered = 0;        /* We send an immediate update (below) */
1392
  tm2_start(ifa->timer, 100 MS);
1393
  ifa->up = 1;
1394

    
1395
  babel_send_hello(ifa, 0);
1396
  babel_send_wildcard_retraction(ifa);
1397
  babel_send_wildcard_request(ifa);
1398
  babel_send_update(ifa, 0);        /* Full update */
1399
}
1400

    
1401
static void
1402
babel_iface_stop(struct babel_iface *ifa)
1403
{
1404
  struct babel_proto *p = ifa->proto;
1405
  struct babel_neighbor *nbr;
1406
  struct babel_route *r;
1407
  node *n;
1408
  btime now_ = current_time();
1409

    
1410
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1411

    
1412
  /*
1413
   * Rather than just flushing the neighbours, we set the metric of their routes
1414
   * to infinity. This allows us to keep the neighbour hello state for when the
1415
   * interface comes back up. The routes will also be kept until they expire.
1416
   */
1417
  WALK_LIST(nbr, ifa->neigh_list)
1418
  {
1419
    WALK_LIST(n, nbr->routes)
1420
    {
1421
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1422
      r->metric = BABEL_INFINITY;
1423
      r->expires = now_ + r->expiry_interval;
1424
      babel_select_route(r->e);
1425
    }
1426
  }
1427

    
1428
  tm2_stop(ifa->timer);
1429
  ifa->up = 0;
1430
}
1431

    
1432
static inline int
1433
babel_iface_link_up(struct babel_iface *ifa)
1434
{
1435
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
1436
}
1437

    
1438
static void
1439
babel_iface_update_state(struct babel_iface *ifa)
1440
{
1441
  int up = ifa->sk && babel_iface_link_up(ifa);
1442

    
1443
  if (up == ifa->up)
1444
    return;
1445

    
1446
  if (up)
1447
    babel_iface_start(ifa);
1448
  else
1449
    babel_iface_stop(ifa);
1450
}
1451

    
1452
static void
1453
babel_iface_update_buffers(struct babel_iface *ifa)
1454
{
1455
  if (!ifa->sk)
1456
    return;
1457

    
1458
  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
1459
  uint rbsize = ifa->cf->rx_buffer ?: mtu;
1460
  uint tbsize = ifa->cf->tx_length ?: mtu;
1461
  rbsize = MAX(rbsize, tbsize);
1462

    
1463
  sk_set_rbsize(ifa->sk, rbsize);
1464
  sk_set_tbsize(ifa->sk, tbsize);
1465

    
1466
  ifa->tx_length = tbsize - BABEL_OVERHEAD;
1467
}
1468

    
1469
static struct babel_iface*
1470
babel_find_iface(struct babel_proto *p, struct iface *what)
1471
{
1472
  struct babel_iface *ifa;
1473

    
1474
  WALK_LIST (ifa, p->interfaces)
1475
    if (ifa->iface == what)
1476
      return ifa;
1477

    
1478
  return NULL;
1479
}
1480

    
1481
static void
1482
babel_iface_locked(struct object_lock *lock)
1483
{
1484
  struct babel_iface *ifa = lock->data;
1485
  struct babel_proto *p = ifa->proto;
1486

    
1487
  if (!babel_open_socket(ifa))
1488
  {
1489
    log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
1490
    return;
1491
  }
1492

    
1493
  babel_iface_update_buffers(ifa);
1494
  babel_iface_update_state(ifa);
1495
}
1496

    
1497
static void
1498
babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
1499
{
1500
  struct babel_iface *ifa;
1501

    
1502
  TRACE(D_EVENTS, "Adding interface %s", new->name);
1503

    
1504
  pool *pool = rp_new(p->p.pool, new->name);
1505

    
1506
  ifa = mb_allocz(pool, sizeof(struct babel_iface));
1507
  ifa->proto = p;
1508
  ifa->iface = new;
1509
  ifa->cf = ic;
1510
  ifa->pool = pool;
1511
  ifa->ifname = new->name;
1512
  ifa->addr = new->llv6->ip;
1513

    
1514
  add_tail(&p->interfaces, NODE ifa);
1515

    
1516
  ip_addr addr4 = new->addr4 ? new->addr4->ip : IPA_NONE;
1517
  ifa->next_hop_ip4 = ipa_nonzero(ic->next_hop_ip4) ? ic->next_hop_ip4 : addr4;
1518
  ifa->next_hop_ip6 = ipa_nonzero(ic->next_hop_ip6) ? ic->next_hop_ip6 : ifa->addr;
1519

    
1520
  if (ipa_zero(ifa->next_hop_ip4) && p->ip4_channel)
1521
    log(L_WARN "%s: Cannot find IPv4 next hop addr on %s", p->p.name, new->name);
1522

    
1523
  init_list(&ifa->neigh_list);
1524
  ifa->hello_seqno = 1;
1525

    
1526
  ifa->timer = tm2_new_init(ifa->pool, babel_iface_timer, ifa, 0, 0);
1527

    
1528
  init_list(&ifa->msg_queue);
1529
  ifa->send_event = ev_new(ifa->pool);
1530
  ifa->send_event->hook = babel_send_queue;
1531
  ifa->send_event->data = ifa;
1532

    
1533
  struct object_lock *lock = olock_new(ifa->pool);
1534
  lock->type = OBJLOCK_UDP;
1535
  lock->addr = IP6_BABEL_ROUTERS;
1536
  lock->port = ifa->cf->port;
1537
  lock->iface = ifa->iface;
1538
  lock->hook = babel_iface_locked;
1539
  lock->data = ifa;
1540

    
1541
  olock_acquire(lock);
1542
}
1543

    
1544
static void
1545
babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
1546
{
1547
  TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
1548

    
1549
  struct babel_neighbor *n;
1550
  WALK_LIST_FIRST(n, ifa->neigh_list)
1551
    babel_flush_neighbor(n);
1552

    
1553
  rem_node(NODE ifa);
1554

    
1555
  rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
1556
}
1557

    
1558
static void
1559
babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
1560
{
1561
  struct babel_proto *p = (void *) P;
1562
  struct babel_config *cf = (void *) P->cf;
1563

    
1564
  if (iface->flags & IF_IGNORE)
1565
    return;
1566

    
1567
  if (flags & IF_CHANGE_UP)
1568
  {
1569
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1570

    
1571
    /* we only speak multicast */
1572
    if (!(iface->flags & IF_MULTICAST))
1573
      return;
1574

    
1575
    /* Ignore ifaces without link-local address */
1576
    if (!iface->llv6)
1577
      return;
1578

    
1579
    if (ic)
1580
      babel_add_iface(p, iface, ic);
1581

    
1582
    return;
1583
  }
1584

    
1585
  struct babel_iface *ifa = babel_find_iface(p, iface);
1586

    
1587
  if (!ifa)
1588
    return;
1589

    
1590
  if (flags & IF_CHANGE_DOWN)
1591
  {
1592
    babel_remove_iface(p, ifa);
1593
    return;
1594
  }
1595

    
1596
  if (flags & IF_CHANGE_MTU)
1597
    babel_iface_update_buffers(ifa);
1598

    
1599
  if (flags & IF_CHANGE_LINK)
1600
    babel_iface_update_state(ifa);
1601
}
1602

    
1603
static int
1604
babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new)
1605
{
1606
  struct babel_iface_config *old = ifa->cf;
1607

    
1608
  /* Change of these options would require to reset the iface socket */
1609
  if ((new->port != old->port) ||
1610
      (new->tx_tos != old->tx_tos) ||
1611
      (new->tx_priority != old->tx_priority))
1612
    return 0;
1613

    
1614
  TRACE(D_EVENTS, "Reconfiguring interface %s", ifa->iface->name);
1615

    
1616
  ifa->cf = new;
1617

    
1618
  ip_addr addr4 = ifa->iface->addr4 ? ifa->iface->addr4->ip : IPA_NONE;
1619
  ifa->next_hop_ip4 = ipa_nonzero(new->next_hop_ip4) ? new->next_hop_ip4 : addr4;
1620
  ifa->next_hop_ip6 = ipa_nonzero(new->next_hop_ip6) ? new->next_hop_ip6 : ifa->addr;
1621

    
1622
  if (ipa_zero(ifa->next_hop_ip4) && p->ip4_channel)
1623
    log(L_WARN "%s: Cannot find IPv4 next hop addr on %s", p->p.name, ifa->ifname);
1624

    
1625
  if (ifa->next_hello > (current_time() + new->hello_interval))
1626
    ifa->next_hello = current_time() + (random() % new->hello_interval);
1627

    
1628
  if (ifa->next_regular > (current_time() + new->update_interval))
1629
    ifa->next_regular = current_time() + (random() % new->update_interval);
1630

    
1631
  if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
1632
    babel_iface_update_buffers(ifa);
1633

    
1634
  if (new->check_link != old->check_link)
1635
    babel_iface_update_state(ifa);
1636

    
1637
  if (ifa->up)
1638
    babel_iface_kick_timer(ifa);
1639

    
1640
  return 1;
1641
}
1642

    
1643
static void
1644
babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
1645
{
1646
  struct iface *iface;
1647

    
1648
  WALK_LIST(iface, iface_list)
1649
  {
1650
    if (!(iface->flags & IF_UP))
1651
      continue;
1652

    
1653
    /* Ignore non-multicast ifaces */
1654
    if (!(iface->flags & IF_MULTICAST))
1655
      continue;
1656

    
1657
    /* Ignore ifaces without link-local address */
1658
    if (!iface->llv6)
1659
      continue;
1660

    
1661
    struct babel_iface *ifa = babel_find_iface(p, iface);
1662
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1663

    
1664
    if (ifa && ic)
1665
    {
1666
      if (babel_reconfigure_iface(p, ifa, ic))
1667
        continue;
1668

    
1669
      /* Hard restart */
1670
      log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
1671
      babel_remove_iface(p, ifa);
1672
      babel_add_iface(p, iface, ic);
1673
    }
1674

    
1675
    if (ifa && !ic)
1676
      babel_remove_iface(p, ifa);
1677

    
1678
    if (!ifa && ic)
1679
      babel_add_iface(p, iface, ic);
1680
  }
1681
}
1682

    
1683

    
1684
/*
1685
 *        Debugging and info output functions
1686
 */
1687

    
1688
static void
1689
babel_dump_source(struct babel_source *s)
1690
{
1691
  debug("Source router_id %lR seqno %d metric %d expires %t\n",
1692
        s->router_id, s->seqno, s->metric,
1693
        s->expires ? s->expires - current_time() : 0);
1694
}
1695

    
1696
static void
1697
babel_dump_route(struct babel_route *r)
1698
{
1699
  debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %t\n",
1700
        r->neigh ? r->neigh->addr : IPA_NONE,
1701
        r->neigh ? r->neigh->ifa->ifname : "(none)",
1702
        r->seqno, r->advert_metric, r->metric, r->router_id,
1703
        r->expires ? r->expires - current_time() : 0);
1704
}
1705

    
1706
static void
1707
babel_dump_entry(struct babel_entry *e)
1708
{
1709
  struct babel_source *s;
1710
  struct babel_route *r;
1711

    
1712
  debug("Babel: Entry %N:\n", e->n.addr);
1713

    
1714
  WALK_LIST(s,e->sources)
1715
  { debug(" "); babel_dump_source(s); }
1716

    
1717
  WALK_LIST(r,e->routes)
1718
  {
1719
    debug(" ");
1720
    if (r == e->selected_out) debug("*");
1721
    if (r == e->selected_in) debug("+");
1722
    babel_dump_route(r);
1723
  }
1724
}
1725

    
1726
static void
1727
babel_dump_neighbor(struct babel_neighbor *n)
1728
{
1729
  debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %t/%t\n",
1730
        n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
1731
        n->hello_expiry ? n->hello_expiry - current_time() : 0,
1732
        n->ihu_expiry ? n->ihu_expiry - current_time() : 0);
1733
}
1734

    
1735
static void
1736
babel_dump_iface(struct babel_iface *ifa)
1737
{
1738
  struct babel_neighbor *n;
1739

    
1740
  debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %t %t",
1741
        ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
1742
        ifa->cf->hello_interval, ifa->cf->update_interval);
1743
  debug(" next hop v4 %I next hop v6 %I\n", ifa->next_hop_ip4, ifa->next_hop_ip6);
1744

    
1745
  WALK_LIST(n, ifa->neigh_list)
1746
  { debug(" "); babel_dump_neighbor(n); }
1747
}
1748

    
1749
static void
1750
babel_dump(struct proto *P)
1751
{
1752
  struct babel_proto *p = (struct babel_proto *) P;
1753
  struct babel_iface *ifa;
1754

    
1755
  debug("Babel: router id %lR update seqno %d\n", p->router_id, p->update_seqno);
1756

    
1757
  WALK_LIST(ifa, p->interfaces)
1758
    babel_dump_iface(ifa);
1759

    
1760
  FIB_WALK(&p->ip4_rtable, struct babel_entry, e)
1761
  {
1762
    babel_dump_entry(e);
1763
  }
1764
  FIB_WALK_END;
1765
  FIB_WALK(&p->ip6_rtable, struct babel_entry, e)
1766
  {
1767
    babel_dump_entry(e);
1768
  }
1769
  FIB_WALK_END;
1770
}
1771

    
1772
static void
1773
babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
1774
{
1775
  buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id);
1776
}
1777

    
1778
static int
1779
babel_get_attr(eattr *a, byte *buf, int buflen UNUSED)
1780
{
1781
  switch (a->id)
1782
  {
1783
  case EA_BABEL_METRIC:
1784
    bsprintf(buf, "metric: %d", a->u.data);
1785
    return GA_FULL;
1786

    
1787
  case EA_BABEL_ROUTER_ID:
1788
  {
1789
    u64 rid = 0;
1790
    memcpy(&rid, a->u.ptr->data, sizeof(u64));
1791
    bsprintf(buf, "router_id: %lR", rid);
1792
    return GA_FULL;
1793
  }
1794

    
1795
  default:
1796
    return GA_UNKNOWN;
1797
  }
1798
}
1799

    
1800
void
1801
babel_show_interfaces(struct proto *P, char *iff)
1802
{
1803
  struct babel_proto *p = (void *) P;
1804
  struct babel_iface *ifa = NULL;
1805
  struct babel_neighbor *nbr = NULL;
1806

    
1807
  if (p->p.proto_state != PS_UP)
1808
  {
1809
    cli_msg(-1023, "%s: is not up", p->p.name);
1810
    cli_msg(0, "");
1811
    return;
1812
  }
1813

    
1814
  cli_msg(-1023, "%s:", p->p.name);
1815
  cli_msg(-1023, "%-10s %-6s %7s %6s %7s %-15s %s",
1816
          "Interface", "State", "RX cost", "Nbrs", "Timer",
1817
          "Next hop (v4)", "Next hop (v6)");
1818

    
1819
  WALK_LIST(ifa, p->interfaces)
1820
  {
1821
    if (iff && !patmatch(iff, ifa->iface->name))
1822
      continue;
1823

    
1824
    int nbrs = 0;
1825
    WALK_LIST(nbr, ifa->neigh_list)
1826
        nbrs++;
1827

    
1828
    btime timer = MIN(ifa->next_regular, ifa->next_hello) - current_time();
1829
    cli_msg(-1023, "%-10s %-6s %7u %6u %7t %-15I %I",
1830
            ifa->iface->name, (ifa->up ? "Up" : "Down"),
1831
            ifa->cf->rxcost, nbrs, MAX(timer, 0),
1832
            ifa->next_hop_ip4, ifa->next_hop_ip6);
1833
  }
1834

    
1835
  cli_msg(0, "");
1836
}
1837

    
1838
void
1839
babel_show_neighbors(struct proto *P, char *iff)
1840
{
1841
  struct babel_proto *p = (void *) P;
1842
  struct babel_iface *ifa = NULL;
1843
  struct babel_neighbor *n = NULL;
1844
  struct babel_route *r = NULL;
1845

    
1846
  if (p->p.proto_state != PS_UP)
1847
  {
1848
    cli_msg(-1024, "%s: is not up", p->p.name);
1849
    cli_msg(0, "");
1850
    return;
1851
  }
1852

    
1853
  cli_msg(-1024, "%s:", p->p.name);
1854
  cli_msg(-1024, "%-25s %-10s %6s %6s %6s %7s",
1855
          "IP address", "Interface", "Metric", "Routes", "Hellos", "Expires");
1856

    
1857
  WALK_LIST(ifa, p->interfaces)
1858
  {
1859
    if (iff && !patmatch(iff, ifa->iface->name))
1860
      continue;
1861

    
1862
    WALK_LIST(n, ifa->neigh_list)
1863
    {
1864
      int rts = 0;
1865
      WALK_LIST(r, n->routes)
1866
        rts++;
1867

    
1868
      uint hellos = u32_popcount(n->hello_map);
1869
      btime timer = n->hello_expiry - current_time();
1870
      cli_msg(-1024, "%-25I %-10s %6u %6u %6u %7t",
1871
              n->addr, ifa->iface->name, n->txcost, rts, hellos, MAX(timer, 0));
1872
    }
1873
  }
1874

    
1875
  cli_msg(0, "");
1876
}
1877

    
1878
static void
1879
babel_show_entries_(struct babel_proto *p, struct fib *rtable)
1880
{
1881
  struct babel_source *s = NULL;
1882
  struct babel_route *r = NULL;
1883

    
1884
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1885

    
1886
  FIB_WALK(rtable, struct babel_entry, e)
1887
  {
1888
    r = e->selected_in ? e->selected_in : e->selected_out;
1889

    
1890
    int srcs = 0;
1891
    WALK_LIST(s, e->sources)
1892
      srcs++;
1893

    
1894
    if (r)
1895
    {
1896
      if (r->router_id == p->router_id)
1897
        bsprintf(ridbuf, "%s", "<self>");
1898
      else
1899
        bsprintf(ridbuf, "%lR", r->router_id);
1900

    
1901
      btime time = r->expires ? r->expires - current_time() : 0;
1902
      cli_msg(-1025, "%-29N %-23s %6u %5u %7t %7u",
1903
              e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
1904
    }
1905
    else
1906
    {
1907
      cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs);
1908
    }
1909
  }
1910
  FIB_WALK_END;
1911
}
1912

    
1913
void
1914
babel_show_entries(struct proto *P)
1915
{
1916
  struct babel_proto *p = (void *) P;
1917

    
1918
  if (p->p.proto_state != PS_UP)
1919
  {
1920
    cli_msg(-1025, "%s: is not up", p->p.name);
1921
    cli_msg(0, "");
1922
    return;
1923
  }
1924

    
1925
  cli_msg(-1025, "%s:", p->p.name);
1926
  cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
1927
          "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
1928

    
1929
  babel_show_entries_(p, &p->ip4_rtable);
1930
  babel_show_entries_(p, &p->ip6_rtable);
1931

    
1932
  cli_msg(0, "");
1933
}
1934

    
1935

    
1936
/*
1937
 *        Babel protocol glue
1938
 */
1939

    
1940
/**
1941
 * babel_timer - global timer hook
1942
 * @t: Timer
1943
 *
1944
 * This function is called by the global protocol instance timer and handles
1945
 * expiration of routes and neighbours as well as pruning of the seqno request
1946
 * cache.
1947
 */
1948
static void
1949
babel_timer(timer *t)
1950
{
1951
  struct babel_proto *p = t->data;
1952

    
1953
  babel_expire_routes(p);
1954
  babel_expire_seqno_requests(p);
1955
  babel_expire_neighbors(p);
1956
}
1957

    
1958
static inline void
1959
babel_kick_timer(struct babel_proto *p)
1960
{
1961
  if (p->timer->expires > (current_time() + 100 MS))
1962
    tm2_start(p->timer, 100 MS);
1963
}
1964

    
1965

    
1966
static struct ea_list *
1967
babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id)
1968
{
1969
  struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr));
1970
  struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64));
1971
  rid->length = sizeof(u64);
1972
  memcpy(&rid->data, &router_id, sizeof(u64));
1973

    
1974
  l->next = next;
1975
  l->flags = EALF_SORTED;
1976
  l->count = 2;
1977

    
1978
  l->attrs[0].id = EA_BABEL_METRIC;
1979
  l->attrs[0].flags = 0;
1980
  l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
1981
  l->attrs[0].u.data = metric;
1982

    
1983
  l->attrs[1].id = EA_BABEL_ROUTER_ID;
1984
  l->attrs[1].flags = 0;
1985
  l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
1986
  l->attrs[1].u.ptr = rid;
1987

    
1988
  return l;
1989
}
1990

    
1991

    
1992
static int
1993
babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool)
1994
{
1995
  struct babel_proto *p = (void *) P;
1996

    
1997
  /* Prepare attributes with initial values */
1998
  if ((*rt)->attrs->source != RTS_BABEL)
1999
    *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
2000

    
2001
  return 0;
2002
}
2003

    
2004
static struct ea_list *
2005
babel_make_tmp_attrs(struct rte *rt, struct linpool *pool)
2006
{
2007
  return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id);
2008
}
2009

    
2010
static void
2011
babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs)
2012
{
2013
  rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
2014
}
2015

    
2016
/*
2017
 * babel_rt_notify - core tells us about new route (possibly our own),
2018
 * so store it into our data structures.
2019
 */
2020
static void
2021
babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net,
2022
                struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
2023
{
2024
  struct babel_proto *p = (void *) P;
2025
  struct babel_entry *e;
2026
  struct babel_route *r;
2027

    
2028
  if (new)
2029
  {
2030
    /* Update */
2031
    e = babel_get_entry(p, net->n.addr);
2032

    
2033
    if (new->attrs->src->proto != P)
2034
    {
2035
      r = babel_get_route(e, NULL);
2036
      r->seqno = p->update_seqno;
2037
      r->router_id = p->router_id;
2038
      r->metric = 0;        /* FIXME: should be selectable */
2039
    }
2040
    else
2041
      r = e->selected_in;
2042

    
2043
    if (r != e->selected_out)
2044
    {
2045
      babel_trigger_update(p);
2046
      e->updated = current_time();
2047
      e->selected_out = r;
2048
    }
2049
  }
2050
  else
2051
  {
2052
    /* Withdraw */
2053
    e = babel_find_entry(p, net->n.addr);
2054
    if (!e || !e->selected_out)
2055
      return;
2056

    
2057
    if (OUR_ROUTE(e->selected_out))
2058
    {
2059
      /*
2060
       * We originate this route, so set its metric to infinity and set an
2061
       * expiry time. This causes a retraction to be sent, and later the route
2062
       * to be flushed once the hold time has passed.
2063
       */
2064
      babel_trigger_update(p);
2065
      e->updated = current_time();
2066
      e->selected_out->metric = BABEL_INFINITY;
2067
      e->selected_out->expires = current_time() + BABEL_HOLD_TIME;
2068
    }
2069
    else
2070
    {
2071
      /*
2072
       * This is a route originating from someone else that was lost; presumably
2073
       * because an export filter was updated to filter it. This means we can't
2074
       * set the metric to infinity (it would be overridden on subsequent
2075
       * updates from the peer originating the route), so just clear the
2076
       * exported route.
2077
       *
2078
       * This causes peers to expire the route after a while (like if we just
2079
       * shut down), but it's the best we can do in these circumstances; and
2080
       * since export filters presumably aren't updated that often this is
2081
       * acceptable.
2082
       */
2083
      e->selected_out = NULL;
2084
    }
2085
  }
2086
}
2087

    
2088
static int
2089
babel_rte_better(struct rte *new, struct rte *old)
2090
{
2091
  return new->u.babel.metric < old->u.babel.metric;
2092
}
2093

    
2094
static int
2095
babel_rte_same(struct rte *new, struct rte *old)
2096
{
2097
  return ((new->u.babel.router_id == old->u.babel.router_id) &&
2098
          (new->u.babel.metric == old->u.babel.metric));
2099
}
2100

    
2101

    
2102
static struct proto *
2103
babel_init(struct proto_config *CF)
2104
{
2105
  struct proto *P = proto_new(CF);
2106
  struct babel_proto *p = (void *) P;
2107

    
2108
  proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4));
2109
  proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6));
2110

    
2111
  P->if_notify = babel_if_notify;
2112
  P->rt_notify = babel_rt_notify;
2113
  P->import_control = babel_import_control;
2114
  P->make_tmp_attrs = babel_make_tmp_attrs;
2115
  P->store_tmp_attrs = babel_store_tmp_attrs;
2116
  P->rte_better = babel_rte_better;
2117
  P->rte_same = babel_rte_same;
2118

    
2119
  return P;
2120
}
2121

    
2122
static int
2123
babel_start(struct proto *P)
2124
{
2125
  struct babel_proto *p = (void *) P;
2126
  struct babel_config *cf = (void *) P->cf;
2127

    
2128
  fib_init(&p->ip4_rtable, P->pool, NET_IP4, sizeof(struct babel_entry),
2129
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2130
  fib_init(&p->ip6_rtable, P->pool, NET_IP6, sizeof(struct babel_entry),
2131
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2132

    
2133
  init_list(&p->interfaces);
2134
  p->timer = tm2_new_init(P->pool, babel_timer, p, 1 S, 0);
2135
  tm2_start(p->timer, 1 S);
2136
  p->update_seqno = 1;
2137
  p->router_id = proto_get_router_id(&cf->c);
2138

    
2139
  p->route_slab = sl_new(P->pool, sizeof(struct babel_route));
2140
  p->source_slab = sl_new(P->pool, sizeof(struct babel_source));
2141
  p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node));
2142
  p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request));
2143
  init_list(&p->seqno_cache);
2144

    
2145
  p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 };
2146

    
2147
  return PS_UP;
2148
}
2149

    
2150
static inline void
2151
babel_iface_shutdown(struct babel_iface *ifa)
2152
{
2153
  if (ifa->sk)
2154
  {
2155
    babel_send_wildcard_retraction(ifa);
2156
    babel_send_queue(ifa);
2157
  }
2158
}
2159

    
2160
static int
2161
babel_shutdown(struct proto *P)
2162
{
2163
  struct babel_proto *p = (void *) P;
2164
  struct babel_iface *ifa;
2165

    
2166
  TRACE(D_EVENTS, "Shutdown requested");
2167

    
2168
  WALK_LIST(ifa, p->interfaces)
2169
    babel_iface_shutdown(ifa);
2170

    
2171
  return PS_DOWN;
2172
}
2173

    
2174
static int
2175
babel_reconfigure(struct proto *P, struct proto_config *CF)
2176
{
2177
  struct babel_proto *p = (void *) P;
2178
  struct babel_config *new = (void *) CF;
2179

    
2180
  TRACE(D_EVENTS, "Reconfiguring");
2181

    
2182
  if (!proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4)) ||
2183
      !proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6)))
2184
    return 0;
2185

    
2186
  p->p.cf = CF;
2187
  babel_reconfigure_ifaces(p, new);
2188

    
2189
  babel_trigger_update(p);
2190
  babel_kick_timer(p);
2191

    
2192
  return 1;
2193
}
2194

    
2195

    
2196
struct protocol proto_babel = {
2197
  .name =                "Babel",
2198
  .template =                "babel%d",
2199
  .attr_class =                EAP_BABEL,
2200
  .preference =                DEF_PREF_BABEL,
2201
  .channel_mask =        NB_IP,
2202
  .proto_size =                sizeof(struct babel_proto),
2203
  .config_size =        sizeof(struct babel_config),
2204
  .init =                babel_init,
2205
  .dump =                babel_dump,
2206
  .start =                babel_start,
2207
  .shutdown =                babel_shutdown,
2208
  .reconfigure =        babel_reconfigure,
2209
  .get_route_info =        babel_get_route_info,
2210
  .get_attr =                babel_get_attr
2211
};