Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (56.3 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 = now;
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 = 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
  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

    
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
  TRACE(D_EVENTS, "Route expiry timer for %N router-id %lR fired",
206
        e->n.addr, r->router_id);
207

    
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
babel_expire_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
230
{
231
  struct babel_route *r, *rx;
232
  struct fib_iterator fit;
233

    
234
  FIB_ITERATE_INIT(&fit, rtable);
235

    
236
loop:
237
  FIB_ITERATE_START(rtable, &fit, struct babel_entry, e)
238
  {
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
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
259
       */
260

    
261
      FIB_ITERATE_PUT(&fit);
262
      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
      FIB_ITERATE_PUT(&fit);
272
      fib_delete(rtable, e);
273
      goto loop;
274
    }
275
  }
276
  FIB_ITERATE_END;
277
}
278

    
279
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
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
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
481

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

    
494
    if (r->metric < BABEL_INFINITY)
495
      ap0->nh.gw = r->next_hop;
496

    
497
    rta *a = rta_lookup(ap0);
498
    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
    rte_update2(c, e->n.addr, rte, p->p.main_source);
504
  }
505
  else
506
  {
507
    /* Retraction */
508
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
509
  }
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
    TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
546
          e->n.addr, cur->router_id, cur->metric);
547

    
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
      TRACE(D_EVENTS, "Lost feasible route for prefix %N",
562
            e->n.addr);
563

    
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

    
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
    }
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
      TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
581

    
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
  TRACE(D_PACKETS, "Sending route request for %N to %I",
668
        e->n.addr, n->addr);
669

    
670
  msg.type = BABEL_TLV_ROUTE_REQUEST;
671
  net_copy(&msg.route_request.net, e->n.addr);
672

    
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
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
702
    return;
703

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

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

    
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
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
728
    return;
729

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

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

    
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
babel_send_update_(struct babel_iface *ifa, bird_clock_t changed, struct fib *rtable)
754
{
755
  struct babel_proto *p = ifa->proto;
756

    
757
  FIB_WALK(rtable, struct babel_entry, e)
758
  {
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
    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

    
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
    net_copy(&msg.update.net, e->n.addr);
786

    
787
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
788
                           ifa->next_hop_ip4 : ifa->next_hop_ip6);
789

    
790
    babel_enqueue(&msg, ifa);
791

    
792
    /* Update feasibility distance for redistributed routes */
793
    if (!OUR_ROUTE(r))
794
    {
795
      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
    }
805
  }
806
  FIB_WALK_END;
807
}
808

    
809
static void
810
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
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
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
851
{
852
  struct babel_proto *p = ifa->proto;
853
  union babel_msg msg = {};
854

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

    
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
  msg.update.net = *n;
862

    
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

    
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
babel_cache_seqno_request(struct babel_proto *p, net_addr *n,
951
                          u64 router_id, u16 seqno)
952
{
953
  struct babel_seqno_request *r;
954

    
955
  WALK_LIST(r, p->seqno_cache)
956
  {
957
    if (net_equal(&r->net, n) && (r->router_id == router_id) && (r->seqno == seqno))
958
      return 0;
959
  }
960

    
961
  /* no entries found */
962
  r = sl_alloc(p->seqno_slab);
963
  net_copy(&r->net, n);
964
  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
  TRACE(D_PACKETS, "Forwarding seqno request for %N router-id %lR seqno %d",
981
        e->n.addr, in->router_id, in->seqno);
982

    
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
      if (!babel_cache_seqno_request(p, e->n.addr, in->router_id, in->seqno))
990
        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
      msg.seqno_request.seqno = in->seqno;
996
      msg.seqno_request.router_id = in->router_id;
997
      net_copy(&msg.seqno_request.net, e->n.addr);
998

    
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
  struct babel_neighbor *nbr;
1073
  struct babel_entry *e;
1074
  struct babel_source *s;
1075
  struct babel_route *r;
1076
  node *n;
1077
  int feasible;
1078

    
1079
  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

    
1085
  nbr = babel_find_neighbor(ifa, msg->sender);
1086
  if (!nbr)
1087
  {
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
  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
  /*
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
  /* Retraction */
1139
  if (msg->metric == BABEL_INFINITY)
1140
  {
1141
    if (msg->wildcard)
1142
    {
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
      e = babel_find_entry(p, &msg->net);
1157

    
1158
      if (!e)
1159
        return;
1160

    
1161
      /* The route entry indexed by neighbour */
1162
      r = babel_find_route(e, nbr);
1163

    
1164
      if (!r)
1165
        return;
1166

    
1167
      r->metric = BABEL_INFINITY;
1168
      babel_select_route(e);
1169
    }
1170

    
1171
    /* Done with retractions */
1172
    return;
1173
  }
1174

    
1175
  e = babel_get_entry(p, &msg->net);
1176
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1177
  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
    if (!feasible)
1183
      return;
1184

    
1185
    r = babel_get_route(e, nbr);
1186
    r->advert_metric = msg->metric;
1187
    r->router_id = msg->router_id;
1188
    r->metric = babel_compute_metric(nbr, msg->metric);
1189
    r->next_hop = msg->next_hop;
1190
    r->seqno = msg->seqno;
1191
  }
1192
  else if (r == r->e->selected_in && !feasible)
1193
  {
1194
    /*
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
    babel_unicast_seqno_request(r);
1199

    
1200
    if (msg->router_id == r->router_id)
1201
      return;
1202

    
1203
    /* Treat as retraction */
1204
    r->metric = BABEL_INFINITY;
1205
  }
1206
  else
1207
  {
1208
    /* Last paragraph above - update the entry */
1209
    r->advert_metric = msg->metric;
1210
    r->metric = babel_compute_metric(nbr, msg->metric);
1211
    r->next_hop = msg->next_hop;
1212

    
1213
    r->router_id = msg->router_id;
1214
    r->seqno = msg->seqno;
1215

    
1216
    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

    
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
  TRACE(D_PACKETS, "Handling route request for %N", &msg->net);
1248

    
1249
  /* Non-wildcard request - see if we have an entry for the route.
1250
     If not, send a retraction, otherwise send an update. */
1251
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1252
  if (!e)
1253
  {
1254
    babel_send_retraction(ifa, &msg->net);
1255
  }
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
  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

    
1275
  /* Ignore if we have no such entry or entry has infinite metric */
1276
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1277
  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
  babel_send_wildcard_retraction(ifa);
1390
  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
  ifa->addr = new->llv6->ip;
1505

    
1506
  add_tail(&p->interfaces, NODE ifa);
1507

    
1508
  ip_addr addr4 = new->addr4 ? new->addr4->ip : IPA_NONE;
1509
  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
  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
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1562

    
1563
    /* we only speak multicast */
1564
    if (!(iface->flags & IF_MULTICAST))
1565
      return;
1566

    
1567
    /* Ignore ifaces without link-local address */
1568
    if (!iface->llv6)
1569
      return;
1570

    
1571
    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
  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
  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
  if (ifa->next_hello > (now + new->hello_interval))
1618
    ifa->next_hello = now + (random() % new->hello_interval) + 1;
1619

    
1620
  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
    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
      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
  debug("Babel: Entry %N:\n", e->n.addr);
1704

    
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
  debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d",
1732
        ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
1733
        ifa->cf->hello_interval, ifa->cf->update_interval);
1734
  debug(" next hop v4 %I next hop v6 %I\n", ifa->next_hop_ip4, ifa->next_hop_ip6);
1735

    
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
  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
  {
1758
    babel_dump_entry(e);
1759
  }
1760
  FIB_WALK_END;
1761
}
1762

    
1763
static void
1764
babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
1765
{
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
  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

    
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
    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
  }
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
static void
1869
babel_show_entries_(struct babel_proto *p, struct fib *rtable)
1870
{
1871
  struct babel_source *s = NULL;
1872
  struct babel_route *r = NULL;
1873

    
1874
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1875

    
1876
  FIB_WALK(rtable, struct babel_entry, e)
1877
  {
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
      cli_msg(-1025, "%-29N %-23s %6u %5u %7u %7u",
1893
              e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
1894
    }
1895
    else
1896
    {
1897
      cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs);
1898
    }
1899
  }
1900
  FIB_WALK_END;
1901
}
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

    
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
babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net,
2012
                struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
2013
{
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
    e = babel_get_entry(p, net->n.addr);
2022

    
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
    e = babel_find_entry(p, net->n.addr);
2044
    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
babel_init(struct proto_config *CF)
2094
{
2095
  struct proto *P = proto_new(CF);
2096
  struct babel_proto *p = (void *) P;
2097

    
2098
  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

    
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
  fib_init(&p->ip4_rtable, P->pool, NET_IP4, sizeof(struct babel_entry),
2119
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2120
  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
  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
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
static int
2165
babel_reconfigure(struct proto *P, struct proto_config *CF)
2166
{
2167
  struct babel_proto *p = (void *) P;
2168
  struct babel_config *new = (void *) CF;
2169

    
2170
  TRACE(D_EVENTS, "Reconfiguring");
2171

    
2172
  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
    return 0;
2175

    
2176
  p->p.cf = CF;
2177
  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
  .channel_mask =        NB_IP,
2192
  .proto_size =                sizeof(struct babel_proto),
2193
  .config_size =        sizeof(struct babel_config),
2194
  .init =                babel_init,
2195
  .dump =                babel_dump,
2196
  .start =                babel_start,
2197
  .shutdown =                babel_shutdown,
2198
  .reconfigure =        babel_reconfigure,
2199
  .get_route_info =        babel_get_route_info,
2200
  .get_attr =                babel_get_attr
2201
};