Statistics
| Branch: | Revision:

iof-bird-daemon / proto / babel / babel.c @ 5e8df049

History | View | Annotate | Download (53.7 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
  return fib_find(&p->rtable, n);
82
}
83

    
84
static struct babel_entry *
85
babel_get_entry(struct babel_proto *p, const net_addr *n)
86
{
87
  struct babel_entry *e = fib_get(&p->rtable, n);
88
  e->proto = p;
89
  return e;
90
}
91

    
92
static struct babel_source *
93
babel_find_source(struct babel_entry *e, u64 router_id)
94
{
95
  struct babel_source *s;
96

    
97
  WALK_LIST(s, e->sources)
98
    if (s->router_id == router_id)
99
      return s;
100

    
101
  return NULL;
102
}
103

    
104
static struct babel_source *
105
babel_get_source(struct babel_entry *e, u64 router_id)
106
{
107
  struct babel_proto *p = e->proto;
108
  struct babel_source *s = babel_find_source(e, router_id);
109

    
110
  if (s)
111
    return s;
112

    
113
  s = sl_alloc(p->source_slab);
114
  s->router_id = router_id;
115
  s->expires = now + BABEL_GARBAGE_INTERVAL;
116
  s->seqno = 0;
117
  s->metric = BABEL_INFINITY;
118
  add_tail(&e->sources, NODE s);
119

    
120
  return s;
121
}
122

    
123
static void
124
babel_expire_sources(struct babel_entry *e)
125
{
126
  struct babel_proto *p = e->proto;
127
  struct babel_source *n, *nx;
128

    
129
  WALK_LIST_DELSAFE(n, nx, e->sources)
130
  {
131
    if (n->expires && n->expires <= now)
132
    {
133
      rem_node(NODE n);
134
      sl_free(p->source_slab, n);
135
    }
136
  }
137
}
138

    
139
static struct babel_route *
140
babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
141
{
142
  struct babel_route *r;
143

    
144
  WALK_LIST(r, e->routes)
145
    if (r->neigh == n)
146
      return r;
147

    
148
  return NULL;
149
}
150

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

    
157
  if (r)
158
    return r;
159

    
160
  r = sl_alloc(p->route_slab);
161
  memset(r, 0, sizeof(*r));
162
  r->e = e;
163
  add_tail(&e->routes, NODE r);
164

    
165
  if (nbr)
166
  {
167
    r->neigh = nbr;
168
    r->expires = now + BABEL_GARBAGE_INTERVAL;
169
    add_tail(&nbr->routes, NODE &r->neigh_route);
170
  }
171

    
172
  return r;
173
}
174

    
175
static void
176
babel_flush_route(struct babel_route *r)
177
{
178
  struct babel_proto *p = r->e->proto;
179

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

    
183
  rem_node(NODE r);
184

    
185
  if (r->neigh)
186
    rem_node(&r->neigh_route);
187

    
188
  if (r->e->selected_in == r)
189
    r->e->selected_in = NULL;
190

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

    
194
  sl_free(p->route_slab, r);
195
}
196

    
197
static void
198
babel_expire_route(struct babel_route *r)
199
{
200
  struct babel_proto *p = r->e->proto;
201
  struct babel_entry *e = r->e;
202

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

    
206
  if (r->metric < BABEL_INFINITY)
207
  {
208
    r->metric = BABEL_INFINITY;
209
    r->expires = now + r->expiry_interval;
210
  }
211
  else
212
  {
213
    babel_flush_route(r);
214
  }
215
}
216

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

    
223
  r->refresh_time = 0;
224
}
225

    
226
static void
227
babel_expire_routes(struct babel_proto *p)
228
{
229
  struct babel_route *r, *rx;
230
  struct fib_iterator fit;
231

    
232
  FIB_ITERATE_INIT(&fit, &p->rtable);
233

    
234
loop:
235
  FIB_ITERATE_START(&p->rtable, &fit, struct babel_entry, e)
236
  {
237
    int changed = 0;
238

    
239
    WALK_LIST_DELSAFE(r, rx, e->routes)
240
    {
241
      if (r->refresh_time && r->refresh_time <= now)
242
        babel_refresh_route(r);
243

    
244
      if (r->expires && r->expires <= now)
245
      {
246
        babel_expire_route(r);
247
        changed = 1;
248
      }
249
    }
250

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

    
259
      FIB_ITERATE_PUT(&fit);
260
      babel_select_route(e);
261
      goto loop;
262
    }
263

    
264
    babel_expire_sources(e);
265

    
266
    /* Remove empty entries */
267
    if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes))
268
    {
269
      FIB_ITERATE_PUT(&fit);
270
      fib_delete(&p->rtable, e);
271
      goto loop;
272
    }
273
  }
274
  FIB_ITERATE_END;
275
}
276

    
277
static struct babel_neighbor *
278
babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
279
{
280
  struct babel_neighbor *nbr;
281

    
282
  WALK_LIST(nbr, ifa->neigh_list)
283
    if (ipa_equal(nbr->addr, addr))
284
      return nbr;
285

    
286
  return NULL;
287
}
288

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

    
294
  if (nbr)
295
    return nbr;
296

    
297
  nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
298
  nbr->ifa = ifa;
299
  nbr->addr = addr;
300
  nbr->txcost = BABEL_INFINITY;
301
  init_list(&nbr->routes);
302
  add_tail(&ifa->neigh_list, NODE nbr);
303

    
304
  return nbr;
305
}
306

    
307
static void
308
babel_flush_neighbor(struct babel_neighbor *nbr)
309
{
310
  struct babel_proto *p = nbr->ifa->proto;
311
  node *n;
312

    
313
  TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
314

    
315
  WALK_LIST_FIRST(n, nbr->routes)
316
  {
317
    struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n);
318
    struct babel_entry *e = r->e;
319
    int selected = (r == e->selected_in);
320

    
321
    babel_flush_route(r);
322

    
323
    if (selected)
324
      babel_select_route(e);
325
  }
326

    
327
  rem_node(NODE nbr);
328
  mb_free(nbr);
329
}
330

    
331
static void
332
babel_expire_ihu(struct babel_neighbor *nbr)
333
{
334
  nbr->txcost = BABEL_INFINITY;
335
}
336

    
337
static void
338
babel_expire_hello(struct babel_neighbor *nbr)
339
{
340
  nbr->hello_map <<= 1;
341

    
342
  if (nbr->hello_cnt < 16)
343
    nbr->hello_cnt++;
344

    
345
  if (!nbr->hello_map)
346
    babel_flush_neighbor(nbr);
347
}
348

    
349
static void
350
babel_expire_neighbors(struct babel_proto *p)
351
{
352
  struct babel_iface *ifa;
353
  struct babel_neighbor *nbr, *nbx;
354

    
355
  WALK_LIST(ifa, p->interfaces)
356
  {
357
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
358
    {
359
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now)
360
        babel_expire_ihu(nbr);
361

    
362
      if (nbr->hello_expiry && nbr->hello_expiry <= now)
363
        babel_expire_hello(nbr);
364
    }
365
  }
366
}
367

    
368

    
369
/*
370
 *        Best route selection
371
 */
372

    
373
/*
374
 * From the RFC (section 3.5.1):
375
 *
376
 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
377
 * metric) is feasible if one of the following conditions holds:
378
 *
379
 * - metric is infinite; or
380
 *
381
 * - no entry exists in the source table indexed by (id, prefix, plen); or
382
 *
383
 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
384
 *   table, and either
385
 *   - seqno' < seqno or
386
 *   - seqno = seqno' and metric < metric'.
387
 */
388
static inline int
389
babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
390
{
391
  return !s ||
392
    (metric == BABEL_INFINITY) ||
393
    (seqno > s->seqno) ||
394
    ((seqno == s->seqno) && (metric < s->metric));
395
}
396

    
397
static u16
398
babel_compute_rxcost(struct babel_neighbor *n)
399
{
400
  struct babel_iface *ifa = n->ifa;
401
  u8 cnt, missed;
402
  u16 map=n->hello_map;
403

    
404
  if (!map) return BABEL_INFINITY;
405
  cnt = u32_popcount(map); // number of bits set
406
  missed = n->hello_cnt-cnt;
407

    
408
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
409
  {
410
    /* ETX - Appendix 2.2 in the RFC.
411

412
       beta = prob. of successful transmission.
413
       rxcost = BABEL_RXCOST_WIRELESS/beta
414

415
       Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
416
       Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
417
   */
418
    if (!cnt) return BABEL_INFINITY;
419
    return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt;
420
  }
421
  else
422
  {
423
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
424
    DBG("Babel: Missed %d hellos from %I\n", missed, n->addr);
425
    /* Link is bad if more than half the expected hellos were lost */
426
    return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost;
427
  }
428
}
429

    
430

    
431
static u16
432
babel_compute_cost(struct babel_neighbor *n)
433
{
434
  struct babel_iface *ifa = n->ifa;
435
  u16 rxcost = babel_compute_rxcost(n);
436
  if (rxcost == BABEL_INFINITY) return rxcost;
437
  else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
438
  {
439
    /* ETX - Appendix 2.2 in the RFC */
440
    return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS;
441
  }
442
  else
443
  {
444
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
445
    return n->txcost;
446
  }
447
}
448

    
449
/* Simple additive metric - Appendix 3.1 in the RFC */
450
static u16
451
babel_compute_metric(struct babel_neighbor *n, uint metric)
452
{
453
  metric += babel_compute_cost(n);
454
  return MIN(metric, BABEL_INFINITY);
455
}
456

    
457

    
458
/**
459
 * babel_announce_rte - announce selected route to the core
460
 * @p: Babel protocol instance
461
 * @e: Babel route entry to announce
462
 *
463
 * This function announces a Babel entry to the core if it has a selected
464
 * incoming path, and retracts it otherwise. If the selected entry has infinite
465
 * metric, the route is announced as unreachable.
466
 */
467
static void
468
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
469
{
470
  struct babel_route *r = e->selected_in;
471

    
472
  if (r)
473
  {
474
    rta a0 = {
475
      .src = p->p.main_source,
476
      .source = RTS_BABEL,
477
      .scope = SCOPE_UNIVERSE,
478
      .cast = RTC_UNICAST,
479
      .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_ROUTER,
480
      .flags = 0,
481
      .from = r->neigh->addr,
482
      .iface = r->neigh->ifa->iface,
483
    };
484

    
485
    if (r->metric < BABEL_INFINITY)
486
      a0.gw = r->next_hop;
487

    
488
    rta *a = rta_lookup(&a0);
489
    rte *rte = rte_get_temp(a);
490
    rte->u.babel.metric = r->metric;
491
    rte->u.babel.router_id = r->router_id;
492
    rte->pflags = 0;
493

    
494
    rte_update(&p->p, e->n.addr, rte);
495
  }
496
  else
497
  {
498
    /* Retraction */
499
    rte_update(&p->p, e->n.addr, NULL);
500
  }
501
}
502

    
503
/**
504
 * babel_select_route - select best route for given route entry
505
 * @e: Babel entry to select the best route for
506
 *
507
 * Select the best feasible route for a given prefix among the routes received
508
 * from peers, and propagate it to the nest. This just selects the feasible
509
 * route with the lowest metric.
510
 *
511
 * If no feasible route is available for a prefix that previously had a route
512
 * selected, a seqno request is sent to try to get a valid route. In the
513
 * meantime, the route is marked as infeasible in the nest (to blackhole packets
514
 * going to it, as per the RFC).
515
 *
516
 * If no feasible route is available, and no previous route is selected, the
517
 * route is removed from the nest entirely.
518
 */
519
static void
520
babel_select_route(struct babel_entry *e)
521
{
522
  struct babel_proto *p = e->proto;
523
  struct babel_route *r, *cur = e->selected_in;
524

    
525
  /* try to find the best feasible route */
526
  WALK_LIST(r, e->routes)
527
    if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */
528
        (!cur || r->metric < cur->metric) &&
529
        babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
530
      cur = r;
531

    
532
  if (cur && !OUR_ROUTE(cur) &&
533
      ((!e->selected_in && cur->metric < BABEL_INFINITY) ||
534
       (e->selected_in && cur->metric < e->selected_in->metric)))
535
  {
536
    TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
537
          e->n.addr, cur->router_id, cur->metric);
538

    
539
    e->selected_in = cur;
540
    e->updated = now;
541
    babel_announce_rte(p, e);
542
  }
543
  else if (!cur || cur->metric == BABEL_INFINITY)
544
  {
545
    /* Couldn't find a feasible route. If we have a selected route, that means
546
       it just became infeasible; so set it's metric to infinite and install it
547
       (as unreachable), then send a seqno request.
548

549
       babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
550
    if (e->selected_in)
551
    {
552
      TRACE(D_EVENTS, "Lost feasible route for prefix %N",
553
            e->n.addr);
554

    
555
      e->selected_in->metric = BABEL_INFINITY;
556
      e->updated = now;
557

    
558
      babel_send_seqno_request(e);
559
      babel_announce_rte(p, e);
560

    
561
      /* Section 3.6 of the RFC forbids an infeasible from being selected. This
562
         is cleared after announcing the route to the core to make sure an
563
         unreachable route is propagated first. */
564
      e->selected_in = NULL;
565
    }
566
    else
567
    {
568
      /* No route currently selected, and no new one selected; this means we
569
         don't have a route to this destination anymore (and were probably
570
         called from an expiry timer). Remove the route from the nest. */
571
      TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
572

    
573
      e->selected_in = NULL;
574
      e->updated = now;
575
      babel_announce_rte(p, e);
576
    }
577
  }
578
}
579

    
580
/*
581
 *        Functions to send replies
582
 */
583

    
584
static void
585
babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
586
{
587
  struct babel_proto *p = ifa->proto;
588
  union babel_msg msg = {};
589

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

    
592
  msg.type = BABEL_TLV_ACK;
593
  msg.ack.nonce = nonce;
594

    
595
  babel_send_unicast(&msg, ifa, dest);
596
}
597

    
598
static void
599
babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
600
{
601
  struct babel_proto *p = ifa->proto;
602

    
603
  msg->type = BABEL_TLV_IHU;
604
  msg->ihu.addr = n->addr;
605
  msg->ihu.rxcost = babel_compute_rxcost(n);
606
  msg->ihu.interval = ifa->cf->ihu_interval;
607

    
608
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %d",
609
        msg->ihu.addr, msg->ihu.rxcost, msg->ihu.interval);
610
}
611

    
612
static void
613
babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
614
{
615
  union babel_msg msg = {};
616
  babel_build_ihu(&msg, ifa, n);
617
  babel_send_unicast(&msg, ifa, n->addr);
618
}
619

    
620
static void
621
babel_send_ihus(struct babel_iface *ifa)
622
{
623
  struct babel_neighbor *n;
624
  WALK_LIST(n, ifa->neigh_list)
625
  {
626
    union babel_msg msg = {};
627
    babel_build_ihu(&msg, ifa, n);
628
    babel_enqueue(&msg, ifa);
629
  }
630
}
631

    
632
static void
633
babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
634
{
635
  struct babel_proto *p = ifa->proto;
636
  union babel_msg msg = {};
637

    
638
  msg.type = BABEL_TLV_HELLO;
639
  msg.hello.seqno = ifa->hello_seqno++;
640
  msg.hello.interval = ifa->cf->hello_interval;
641

    
642
  TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %d",
643
        ifa->ifname, msg.hello.seqno, msg.hello.interval);
644

    
645
  babel_enqueue(&msg, ifa);
646

    
647
  if (send_ihu)
648
    babel_send_ihus(ifa);
649
}
650

    
651
static void
652
babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n)
653
{
654
  struct babel_proto *p = e->proto;
655
  struct babel_iface *ifa = n->ifa;
656
  union babel_msg msg = {};
657

    
658
  TRACE(D_PACKETS, "Sending route request for %N to %I",
659
        e->n.addr, n->addr);
660

    
661
  msg.type = BABEL_TLV_ROUTE_REQUEST;
662
  net_copy(&msg.route_request.net, e->n.addr);
663

    
664
  babel_send_unicast(&msg, ifa, n->addr);
665
}
666

    
667
static void
668
babel_send_wildcard_request(struct babel_iface *ifa)
669
{
670
  struct babel_proto *p = ifa->proto;
671
  union babel_msg msg = {};
672

    
673
  TRACE(D_PACKETS, "Sending wildcard route request on %s",
674
        ifa->ifname);
675

    
676
  msg.type = BABEL_TLV_ROUTE_REQUEST;
677
  msg.route_request.full = 1;
678

    
679
  babel_enqueue(&msg, ifa);
680
}
681

    
682
static void
683
babel_send_seqno_request(struct babel_entry *e)
684
{
685
  struct babel_proto *p = e->proto;
686
  struct babel_route *r = e->selected_in;
687
  struct babel_iface *ifa = NULL;
688
  struct babel_source *s = NULL;
689
  union babel_msg msg = {};
690

    
691
  s = babel_find_source(e, r->router_id);
692
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
693
    return;
694

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

    
698
  msg.type = BABEL_TLV_SEQNO_REQUEST;
699
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
700
  msg.seqno_request.seqno = s->seqno + 1;
701
  msg.seqno_request.router_id = r->router_id;
702
  net_copy(&msg.seqno_request.net, e->n.addr);
703

    
704
  WALK_LIST(ifa, p->interfaces)
705
    babel_enqueue(&msg, ifa);
706
}
707

    
708
static void
709
babel_unicast_seqno_request(struct babel_route *r)
710
{
711
  struct babel_entry *e = r->e;
712
  struct babel_proto *p = e->proto;
713
  struct babel_iface *ifa = r->neigh->ifa;
714
  struct babel_source *s = NULL;
715
  union babel_msg msg = {};
716

    
717
  s = babel_find_source(e, r->router_id);
718
  if (!s || !babel_cache_seqno_request(p, e->n.addr, r->router_id, s->seqno + 1))
719
    return;
720

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

    
724
  msg.type = BABEL_TLV_SEQNO_REQUEST;
725
  msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
726
  msg.seqno_request.seqno = s->seqno + 1;
727
  msg.seqno_request.router_id = r->router_id;
728
  net_copy(&msg.seqno_request.net, e->n.addr);
729

    
730
  babel_send_unicast(&msg, ifa, r->neigh->addr);
731
}
732

    
733
/**
734
 * babel_send_update - send route table updates
735
 * @ifa: Interface to transmit on
736
 * @changed: Only send entries changed since this time
737
 *
738
 * This function produces update TLVs for all entries changed since the time
739
 * indicated by the &changed parameter and queues them for transmission on the
740
 * selected interface. During the process, the feasibility distance for each
741
 * transmitted entry is updated.
742
 */
743
static void
744
babel_send_update(struct babel_iface *ifa, bird_clock_t changed)
745
{
746
  struct babel_proto *p = ifa->proto;
747

    
748
  FIB_WALK(&p->rtable, struct babel_entry, e)
749
  {
750
    struct babel_route *r = e->selected_out;
751

    
752
    if (!r)
753
      continue;
754

    
755
    /* Our own seqno might have changed, in which case we update the routes we
756
       originate. */
757
    if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno))
758
    {
759
      r->seqno = p->update_seqno;
760
      e->updated = now;
761
    }
762

    
763
    /* Skip routes that weren't updated since 'changed' time */
764
    if (e->updated < changed)
765
      continue;
766

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

    
770
    union babel_msg msg = {};
771
    msg.type = BABEL_TLV_UPDATE;
772
    msg.update.interval = ifa->cf->update_interval;
773
    msg.update.seqno = r->seqno;
774
    msg.update.metric = r->metric;
775
    msg.update.router_id = r->router_id;
776
    net_copy(&msg.update.net, e->n.addr);
777

    
778
    babel_enqueue(&msg, ifa);
779

    
780
    /* Update feasibility distance for redistributed routes */
781
    if (!OUR_ROUTE(r))
782
    {
783
      struct babel_source *s = babel_get_source(e, r->router_id);
784
      s->expires = now + BABEL_GARBAGE_INTERVAL;
785

    
786
      if ((msg.update.seqno > s->seqno) ||
787
          ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
788
      {
789
        s->seqno = msg.update.seqno;
790
        s->metric = msg.update.metric;
791
      }
792
    }
793
  }
794
  FIB_WALK_END;
795
}
796

    
797
static void
798
babel_trigger_iface_update(struct babel_iface *ifa)
799
{
800
  struct babel_proto *p = ifa->proto;
801

    
802
  /* Interface not active or already scheduled */
803
  if (!ifa->up || ifa->want_triggered)
804
    return;
805

    
806
  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
807
        ifa->iface->name, p->update_seqno);
808

    
809
  ifa->want_triggered = now;
810
  babel_iface_kick_timer(ifa);
811
}
812

    
813
/* Sends and update on all interfaces. */
814
static void
815
babel_trigger_update(struct babel_proto *p)
816
{
817
  if (p->triggered)
818
    return;
819

    
820
  struct babel_iface *ifa;
821
  WALK_LIST(ifa, p->interfaces)
822
    babel_trigger_iface_update(ifa);
823

    
824
  p->triggered = 1;
825
}
826

    
827
/* A retraction is an update with an infinite metric */
828
static void
829
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
830
{
831
  struct babel_proto *p = ifa->proto;
832
  union babel_msg msg = {};
833

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

    
836
  msg.type = BABEL_TLV_UPDATE;
837
  msg.update.interval = ifa->cf->update_interval;
838
  msg.update.seqno = p->update_seqno;
839
  msg.update.metric = BABEL_INFINITY;
840
  msg.update.net = *n;
841

    
842
  babel_enqueue(&msg, ifa);
843
}
844

    
845
static void
846
babel_send_wildcard_retraction(struct babel_iface *ifa)
847
{
848
  struct babel_proto *p = ifa->proto;
849
  union babel_msg msg = {};
850

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

    
853
  msg.type = BABEL_TLV_UPDATE;
854
  msg.update.wildcard = 1;
855
  msg.update.interval = ifa->cf->update_interval;
856
  msg.update.seqno = p->update_seqno;
857
  msg.update.metric = BABEL_INFINITY;
858

    
859
  babel_enqueue(&msg, ifa);
860
}
861

    
862

    
863
/*
864
 *        TLV handler helpers
865
 */
866

    
867
/* Update hello history according to Appendix A1 of the RFC */
868
static void
869
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, u16 interval)
870
{
871
  /*
872
   * Compute the difference between expected and received seqno (modulo 2^16).
873
   * If the expected and received seqnos are within 16 of each other, the modular
874
   * difference is going to be less than 16 for one of the directions. Otherwise,
875
   * the values differ too much, so just reset the state.
876
   */
877

    
878
  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
879

    
880
  if (delta == 0)
881
  {
882
    /* Do nothing */
883
  }
884
  else if (delta <= 16)
885
  {
886
    /* Sending node decreased interval; fast-forward */
887
    n->hello_map <<= delta;
888
    n->hello_cnt = MIN(n->hello_cnt + delta, 16);
889
  }
890
  else if (delta >= 0xfff0)
891
  {
892
    u8 diff = (0xffff - delta);
893
    /* Sending node increased interval; undo history */
894
    n->hello_map >>= diff;
895
    n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
896
  }
897
  else
898
  {
899
    /* Note state reset - flush entries */
900
    n->hello_map = n->hello_cnt = 0;
901
  }
902

    
903
  /* Current entry */
904
  n->hello_map = (n->hello_map << 1) | 1;
905
  n->next_hello_seqno = seqno+1;
906
  if (n->hello_cnt < 16) n->hello_cnt++;
907
  n->hello_expiry = now + BABEL_HELLO_EXPIRY_FACTOR(interval);
908
}
909

    
910
static void
911
babel_expire_seqno_requests(struct babel_proto *p)
912
{
913
  struct babel_seqno_request *n, *nx;
914
  WALK_LIST_DELSAFE(n, nx, p->seqno_cache)
915
  {
916
    if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now)
917
    {
918
      rem_node(NODE n);
919
      sl_free(p->seqno_slab, n);
920
    }
921
  }
922
}
923

    
924
/*
925
 * Checks the seqno request cache for a matching request and returns failure if
926
 * found. Otherwise, a new entry is stored in the cache.
927
 */
928
static int
929
babel_cache_seqno_request(struct babel_proto *p, net_addr *n,
930
                          u64 router_id, u16 seqno)
931
{
932
  struct babel_seqno_request *r;
933

    
934
  WALK_LIST(r, p->seqno_cache)
935
  {
936
    if (net_equal(&r->net, n) && (r->router_id == router_id) && (r->seqno == seqno))
937
      return 0;
938
  }
939

    
940
  /* no entries found */
941
  r = sl_alloc(p->seqno_slab);
942
  net_copy(&r->net, n);
943
  r->router_id = router_id;
944
  r->seqno = seqno;
945
  r->updated = now;
946
  add_tail(&p->seqno_cache, NODE r);
947

    
948
  return 1;
949
}
950

    
951
static void
952
babel_forward_seqno_request(struct babel_entry *e,
953
                            struct babel_msg_seqno_request *in,
954
                            ip_addr sender)
955
{
956
  struct babel_proto *p = e->proto;
957
  struct babel_route *r;
958

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

    
962
  WALK_LIST(r, e->routes)
963
  {
964
    if ((r->router_id == in->router_id) &&
965
        !OUR_ROUTE(r) &&
966
        !ipa_equal(r->neigh->addr, sender))
967
    {
968
      if (!babel_cache_seqno_request(p, e->n.addr, in->router_id, in->seqno))
969
        return;
970

    
971
      union babel_msg msg = {};
972
      msg.type = BABEL_TLV_SEQNO_REQUEST;
973
      msg.seqno_request.hop_count = in->hop_count-1;
974
      msg.seqno_request.seqno = in->seqno;
975
      msg.seqno_request.router_id = in->router_id;
976
      net_copy(&msg.seqno_request.net, e->n.addr);
977

    
978
      babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr);
979
      return;
980
    }
981
  }
982
}
983

    
984

    
985
/*
986
 *        TLV handlers
987
 */
988

    
989
void
990
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
991
{
992
  struct babel_proto *p = ifa->proto;
993
  struct babel_msg_ack_req *msg = &m->ack_req;
994

    
995
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %d",
996
        msg->nonce, msg->interval);
997

    
998
  babel_send_ack(ifa, msg->sender, msg->nonce);
999
}
1000

    
1001
void
1002
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
1003
{
1004
  struct babel_proto *p = ifa->proto;
1005
  struct babel_msg_hello *msg = &m->hello;
1006

    
1007
  TRACE(D_PACKETS, "Handling hello seqno %d interval %d",
1008
        msg->seqno, msg->interval);
1009

    
1010
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1011
  babel_update_hello_history(n, msg->seqno, msg->interval);
1012
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
1013
    babel_send_ihu(ifa, n);
1014
}
1015

    
1016
void
1017
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
1018
{
1019
  struct babel_proto *p = ifa->proto;
1020
  struct babel_msg_ihu *msg = &m->ihu;
1021

    
1022
  /* Ignore IHUs that are not about us */
1023
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
1024
    return;
1025

    
1026
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d",
1027
        msg->rxcost, msg->interval);
1028

    
1029
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1030
  n->txcost = msg->rxcost;
1031
  n->ihu_expiry = now + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1032
}
1033

    
1034
/**
1035
 * babel_handle_update - handle incoming route updates
1036
 * @m: Incoming update TLV
1037
 * @ifa: Interface the update was received on
1038
 *
1039
 * This function is called as a handler for update TLVs and handles the updating
1040
 * and maintenance of route entries in Babel's internal routing cache. The
1041
 * handling follows the actions described in the Babel RFC, and at the end of
1042
 * each update handling, babel_select_route() is called on the affected entry to
1043
 * optionally update the selected routes and propagate them to the core.
1044
 */
1045
void
1046
babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
1047
{
1048
  struct babel_proto *p = ifa->proto;
1049
  struct babel_msg_update *msg = &m->update;
1050

    
1051
  struct babel_neighbor *nbr;
1052
  struct babel_entry *e;
1053
  struct babel_source *s;
1054
  struct babel_route *r;
1055
  node *n;
1056
  int feasible;
1057

    
1058
  if (msg->wildcard)
1059
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
1060
  else
1061
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
1062
          &msg->net, msg->seqno, msg->metric);
1063

    
1064
  nbr = babel_find_neighbor(ifa, msg->sender);
1065
  if (!nbr)
1066
  {
1067
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
1068
    return;
1069
  }
1070

    
1071
  if (msg->router_id == p->router_id)
1072
  {
1073
    DBG("Babel: Ignoring update for our own router ID.\n");
1074
    return;
1075
  }
1076

    
1077
  /*
1078
   * RFC section 3.5.4:
1079
   *
1080
   * When a Babel node receives an update (id, prefix, seqno, metric) from a
1081
   * neighbour neigh with a link cost value equal to cost, it checks whether it
1082
   * already has a routing table entry indexed by (neigh, id, prefix).
1083
   *
1084
   * If no such entry exists:
1085
   *
1086
   * o if the update is unfeasible, it is ignored;
1087
   *
1088
   * o if the metric is infinite (the update is a retraction), the update is
1089
   *   ignored;
1090
   *
1091
   * o otherwise, a new route table entry is created, indexed by (neigh, id,
1092
   *   prefix), with seqno equal to seqno and an advertised metric equal to the
1093
   *   metric carried by the update.
1094
   *
1095
   * If such an entry exists:
1096
   *
1097
   * o if the entry is currently installed and the update is unfeasible, then
1098
   *   the behaviour depends on whether the router-ids of the two entries match.
1099
   *   If the router-ids are different, the update is treated as though it were
1100
   *   a retraction (i.e., as though the metric were FFFF hexadecimal). If the
1101
   *   router-ids are equal, the update is ignored;
1102
   *
1103
   * o otherwise (i.e., if either the update is feasible or the entry is not
1104
   *   currently installed), then the entry's sequence number, advertised
1105
   *   metric, metric, and router-id are updated and, unless the advertised
1106
   *   metric is infinite, the route's expiry timer is reset to a small multiple
1107
   *   of the Interval value included in the update.
1108
   */
1109

    
1110
  /* Retraction */
1111
  if (msg->metric == BABEL_INFINITY)
1112
  {
1113
    if (msg->wildcard)
1114
    {
1115
      /*
1116
       * Special case: This is a retraction of all prefixes announced by this
1117
       * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
1118
       */
1119
      WALK_LIST(n, nbr->routes)
1120
      {
1121
        r = SKIP_BACK(struct babel_route, neigh_route, n);
1122
        r->metric = BABEL_INFINITY;
1123
        babel_select_route(r->e);
1124
      }
1125
    }
1126
    else
1127
    {
1128
      e = babel_find_entry(p, &msg->net);
1129

    
1130
      if (!e)
1131
        return;
1132

    
1133
      /* The route entry indexed by neighbour */
1134
      r = babel_find_route(e, nbr);
1135

    
1136
      if (!r)
1137
        return;
1138

    
1139
      r->metric = BABEL_INFINITY;
1140
      babel_select_route(e);
1141
    }
1142

    
1143
    /* Done with retractions */
1144
    return;
1145
  }
1146

    
1147
  e = babel_get_entry(p, &msg->net);
1148
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1149
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1150
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1151

    
1152
  if (!r)
1153
  {
1154
    if (!feasible)
1155
      return;
1156

    
1157
    r = babel_get_route(e, nbr);
1158
    r->advert_metric = msg->metric;
1159
    r->router_id = msg->router_id;
1160
    r->metric = babel_compute_metric(nbr, msg->metric);
1161
    r->next_hop = msg->next_hop;
1162
    r->seqno = msg->seqno;
1163
  }
1164
  else if (r == r->e->selected_in && !feasible)
1165
  {
1166
    /*
1167
     * Route is installed and update is infeasible - we may lose the route,
1168
     * so send a unicast seqno request (section 3.8.2.2 second paragraph).
1169
     */
1170
    babel_unicast_seqno_request(r);
1171

    
1172
    if (msg->router_id == r->router_id)
1173
      return;
1174

    
1175
    /* Treat as retraction */
1176
    r->metric = BABEL_INFINITY;
1177
  }
1178
  else
1179
  {
1180
    /* Last paragraph above - update the entry */
1181
    r->advert_metric = msg->metric;
1182
    r->metric = babel_compute_metric(nbr, msg->metric);
1183
    r->next_hop = msg->next_hop;
1184

    
1185
    r->router_id = msg->router_id;
1186
    r->seqno = msg->seqno;
1187

    
1188
    r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1189
    r->expires = now + r->expiry_interval;
1190
    if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
1191
      r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
1192

    
1193
    /* If the route is not feasible at this point, it means it is from another
1194
       neighbour than the one currently selected; so send a unicast seqno
1195
       request to try to get a better route (section 3.8.2.2 last paragraph). */
1196
    if (!feasible)
1197
      babel_unicast_seqno_request(r);
1198
  }
1199

    
1200
  babel_select_route(e);
1201
}
1202

    
1203
void
1204
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
1205
{
1206
  struct babel_proto *p = ifa->proto;
1207
  struct babel_msg_route_request *msg = &m->route_request;
1208

    
1209
  /* RFC 6126 3.8.1.1 */
1210

    
1211
  /* Wildcard request - full update on the interface */
1212
  if (msg->full)
1213
  {
1214
    TRACE(D_PACKETS, "Handling wildcard route request");
1215
    ifa->want_triggered = 1;
1216
    return;
1217
  }
1218

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

    
1221
  /* Non-wildcard request - see if we have an entry for the route.
1222
     If not, send a retraction, otherwise send an update. */
1223
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1224
  if (!e)
1225
  {
1226
    babel_send_retraction(ifa, &msg->net);
1227
  }
1228
  else
1229
  {
1230
    babel_trigger_iface_update(ifa);
1231
    e->updated = now;
1232
  }
1233
}
1234

    
1235

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

    
1242
  /* RFC 6126 3.8.1.2 */
1243

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

    
1247
  /* Ignore if we have no such entry or entry has infinite metric */
1248
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1249
  if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
1250
    return;
1251

    
1252
  /* Trigger update on incoming interface if we have a selected route with
1253
     different router id or seqno no smaller than requested */
1254
  struct babel_route *r = e->selected_out;
1255
  if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno))
1256
  {
1257
    babel_trigger_iface_update(ifa);
1258
    e->updated = now;
1259
    return;
1260
  }
1261

    
1262
  /* Seqno is larger; check if we own the router id */
1263
  if (msg->router_id == p->router_id)
1264
  {
1265
    /* Ours; update seqno and trigger global update */
1266
    p->update_seqno++;
1267
    babel_trigger_update(p);
1268
  }
1269
  else
1270
  {
1271
    /* Not ours; forward if TTL allows it */
1272
    if (msg->hop_count > 1)
1273
      babel_forward_seqno_request(e, msg, msg->sender);
1274
  }
1275
}
1276

    
1277

    
1278
/*
1279
 *        Babel interfaces
1280
 */
1281

    
1282
/**
1283
 * babel_iface_timer - Babel interface timer handler
1284
 * @t: Timer
1285
 *
1286
 * This function is called by the per-interface timer and triggers sending of
1287
 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1288
 * and updates are simply handled by setting the next_{hello,regular} variables
1289
 * on the interface, and triggering an update (and resetting the variable)
1290
 * whenever 'now' exceeds that value.
1291
 *
1292
 * For triggered updates, babel_trigger_iface_update() will set the
1293
 * want_triggered field on the interface to a timestamp value. If this is set
1294
 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1295
 * babel_send_update() will be called with this timestamp as the second
1296
 * parameter. This causes updates to be send consisting of only the routes that
1297
 * have changed since the time saved in want_triggered.
1298
 *
1299
 * Mostly when an update is triggered, the route being modified will be set to
1300
 * the value of 'now' at the time of the trigger; the >= comparison for
1301
 * selecting which routes to send in the update will make sure this is included.
1302
 */
1303
static void
1304
babel_iface_timer(timer *t)
1305
{
1306
  struct babel_iface *ifa = t->data;
1307
  struct babel_proto *p = ifa->proto;
1308
  bird_clock_t hello_period = ifa->cf->hello_interval;
1309
  bird_clock_t update_period = ifa->cf->update_interval;
1310

    
1311
  if (now >= ifa->next_hello)
1312
  {
1313
    babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
1314
                           ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
1315
    ifa->next_hello +=  hello_period * (1 + (now - ifa->next_hello) / hello_period);
1316
  }
1317

    
1318
  if (now >= ifa->next_regular)
1319
  {
1320
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
1321
    babel_send_update(ifa, 0);
1322
    ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period);
1323
    ifa->want_triggered = 0;
1324
    p->triggered = 0;
1325
  }
1326
  else if (ifa->want_triggered && (now >= ifa->next_triggered))
1327
  {
1328
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
1329
    babel_send_update(ifa, ifa->want_triggered);
1330
    ifa->next_triggered = now + MIN(5, update_period / 2 + 1);
1331
    ifa->want_triggered = 0;
1332
    p->triggered = 0;
1333
  }
1334

    
1335
  bird_clock_t next_event = MIN(ifa->next_hello, ifa->next_regular);
1336
  tm_start(ifa->timer, ifa->want_triggered ? 1 : (next_event - now));
1337
}
1338

    
1339
static inline void
1340
babel_iface_kick_timer(struct babel_iface *ifa)
1341
{
1342
  if (ifa->timer->expires > (now + 1))
1343
    tm_start(ifa->timer, 1);
1344
}
1345

    
1346
static void
1347
babel_iface_start(struct babel_iface *ifa)
1348
{
1349
  struct babel_proto *p = ifa->proto;
1350

    
1351
  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
1352

    
1353
  ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1;
1354
  ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1;
1355
  ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1);
1356
  ifa->want_triggered = 0;        /* We send an immediate update (below) */
1357
  tm_start(ifa->timer, 1);
1358
  ifa->up = 1;
1359

    
1360
  babel_send_hello(ifa, 0);
1361
  babel_send_wildcard_retraction(ifa);
1362
  babel_send_wildcard_request(ifa);
1363
  babel_send_update(ifa, 0);        /* Full update */
1364
}
1365

    
1366
static void
1367
babel_iface_stop(struct babel_iface *ifa)
1368
{
1369
  struct babel_proto *p = ifa->proto;
1370
  struct babel_neighbor *nbr;
1371
  struct babel_route *r;
1372
  node *n;
1373

    
1374
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1375

    
1376
  /*
1377
   * Rather than just flushing the neighbours, we set the metric of their routes
1378
   * to infinity. This allows us to keep the neighbour hello state for when the
1379
   * interface comes back up. The routes will also be kept until they expire.
1380
   */
1381
  WALK_LIST(nbr, ifa->neigh_list)
1382
  {
1383
    WALK_LIST(n, nbr->routes)
1384
    {
1385
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1386
      r->metric = BABEL_INFINITY;
1387
      r->expires = now + r->expiry_interval;
1388
      babel_select_route(r->e);
1389
    }
1390
  }
1391

    
1392
  tm_stop(ifa->timer);
1393
  ifa->up = 0;
1394
}
1395

    
1396
static inline int
1397
babel_iface_link_up(struct babel_iface *ifa)
1398
{
1399
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
1400
}
1401

    
1402
static void
1403
babel_iface_update_state(struct babel_iface *ifa)
1404
{
1405
  int up = ifa->sk && babel_iface_link_up(ifa);
1406

    
1407
  if (up == ifa->up)
1408
    return;
1409

    
1410
  if (up)
1411
    babel_iface_start(ifa);
1412
  else
1413
    babel_iface_stop(ifa);
1414
}
1415

    
1416
static void
1417
babel_iface_update_buffers(struct babel_iface *ifa)
1418
{
1419
  if (!ifa->sk)
1420
    return;
1421

    
1422
  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
1423
  uint rbsize = ifa->cf->rx_buffer ?: mtu;
1424
  uint tbsize = ifa->cf->tx_length ?: mtu;
1425
  rbsize = MAX(rbsize, tbsize);
1426

    
1427
  sk_set_rbsize(ifa->sk, rbsize);
1428
  sk_set_tbsize(ifa->sk, tbsize);
1429

    
1430
  ifa->tx_length = tbsize - BABEL_OVERHEAD;
1431
}
1432

    
1433
static struct babel_iface*
1434
babel_find_iface(struct babel_proto *p, struct iface *what)
1435
{
1436
  struct babel_iface *ifa;
1437

    
1438
  WALK_LIST (ifa, p->interfaces)
1439
    if (ifa->iface == what)
1440
      return ifa;
1441

    
1442
  return NULL;
1443
}
1444

    
1445
static void
1446
babel_iface_locked(struct object_lock *lock)
1447
{
1448
  struct babel_iface *ifa = lock->data;
1449
  struct babel_proto *p = ifa->proto;
1450

    
1451
  if (!babel_open_socket(ifa))
1452
  {
1453
    log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
1454
    return;
1455
  }
1456

    
1457
  babel_iface_update_buffers(ifa);
1458
  babel_iface_update_state(ifa);
1459
}
1460

    
1461
static void
1462
babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
1463
{
1464
  struct babel_iface *ifa;
1465

    
1466
  TRACE(D_EVENTS, "Adding interface %s", new->name);
1467

    
1468
  pool *pool = rp_new(p->p.pool, new->name);
1469

    
1470
  ifa = mb_allocz(pool, sizeof(struct babel_iface));
1471
  ifa->proto = p;
1472
  ifa->iface = new;
1473
  ifa->cf = ic;
1474
  ifa->pool = pool;
1475
  ifa->ifname = new->name;
1476

    
1477
  add_tail(&p->interfaces, NODE ifa);
1478

    
1479
  struct ifa *addr;
1480
  WALK_LIST(addr, new->addrs)
1481
    if (ipa_is_link_local(addr->ip))
1482
      ifa->addr = addr->ip;
1483

    
1484
  if (ipa_zero(ifa->addr))
1485
    log(L_WARN "%s: Cannot find link-local addr on %s", p->p.name, new->name);
1486

    
1487
  init_list(&ifa->neigh_list);
1488
  ifa->hello_seqno = 1;
1489

    
1490
  ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0);
1491

    
1492
  init_list(&ifa->msg_queue);
1493
  ifa->send_event = ev_new(ifa->pool);
1494
  ifa->send_event->hook = babel_send_queue;
1495
  ifa->send_event->data = ifa;
1496

    
1497
  struct object_lock *lock = olock_new(ifa->pool);
1498
  lock->type = OBJLOCK_UDP;
1499
  lock->addr = IP6_BABEL_ROUTERS;
1500
  lock->port = ifa->cf->port;
1501
  lock->iface = ifa->iface;
1502
  lock->hook = babel_iface_locked;
1503
  lock->data = ifa;
1504

    
1505
  olock_acquire(lock);
1506
}
1507

    
1508
static void
1509
babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
1510
{
1511
  TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
1512

    
1513
  struct babel_neighbor *n;
1514
  WALK_LIST_FIRST(n, ifa->neigh_list)
1515
    babel_flush_neighbor(n);
1516

    
1517
  rem_node(NODE ifa);
1518

    
1519
  rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
1520
}
1521

    
1522
static void
1523
babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
1524
{
1525
  struct babel_proto *p = (void *) P;
1526
  struct babel_config *cf = (void *) P->cf;
1527

    
1528
  if (iface->flags & IF_IGNORE)
1529
    return;
1530

    
1531
  if (flags & IF_CHANGE_UP)
1532
  {
1533
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, iface->addr);
1534

    
1535
    /* we only speak multicast */
1536
    if (!(iface->flags & IF_MULTICAST))
1537
      return;
1538

    
1539
    if (ic)
1540
      babel_add_iface(p, iface, ic);
1541

    
1542
    return;
1543
  }
1544

    
1545
  struct babel_iface *ifa = babel_find_iface(p, iface);
1546

    
1547
  if (!ifa)
1548
    return;
1549

    
1550
  if (flags & IF_CHANGE_DOWN)
1551
  {
1552
    babel_remove_iface(p, ifa);
1553
    return;
1554
  }
1555

    
1556
  if (flags & IF_CHANGE_MTU)
1557
    babel_iface_update_buffers(ifa);
1558

    
1559
  if (flags & IF_CHANGE_LINK)
1560
    babel_iface_update_state(ifa);
1561
}
1562

    
1563
static int
1564
babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new)
1565
{
1566
  struct babel_iface_config *old = ifa->cf;
1567

    
1568
  /* Change of these options would require to reset the iface socket */
1569
  if ((new->port != old->port) ||
1570
      (new->tx_tos != old->tx_tos) ||
1571
      (new->tx_priority != old->tx_priority))
1572
    return 0;
1573

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

    
1576
  ifa->cf = new;
1577

    
1578
  if (ifa->next_hello > (now + new->hello_interval))
1579
    ifa->next_hello = now + (random() % new->hello_interval) + 1;
1580

    
1581
  if (ifa->next_regular > (now + new->update_interval))
1582
    ifa->next_regular = now + (random() % new->update_interval) + 1;
1583

    
1584
  if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
1585
    babel_iface_update_buffers(ifa);
1586

    
1587
  if (new->check_link != old->check_link)
1588
    babel_iface_update_state(ifa);
1589

    
1590
  if (ifa->up)
1591
    babel_iface_kick_timer(ifa);
1592

    
1593
  return 1;
1594
}
1595

    
1596
static void
1597
babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
1598
{
1599
  struct iface *iface;
1600

    
1601
  WALK_LIST(iface, iface_list)
1602
  {
1603
    if (! (iface->flags & IF_UP))
1604
      continue;
1605

    
1606
    struct babel_iface *ifa = babel_find_iface(p, iface);
1607
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1608

    
1609
    if (ifa && ic)
1610
    {
1611
      if (babel_reconfigure_iface(p, ifa, ic))
1612
        continue;
1613

    
1614
      /* Hard restart */
1615
      log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
1616
      babel_remove_iface(p, ifa);
1617
      babel_add_iface(p, iface, ic);
1618
    }
1619

    
1620
    if (ifa && !ic)
1621
      babel_remove_iface(p, ifa);
1622

    
1623
    if (!ifa && ic)
1624
      babel_add_iface(p, iface, ic);
1625
  }
1626
}
1627

    
1628

    
1629
/*
1630
 *        Debugging and info output functions
1631
 */
1632

    
1633
static void
1634
babel_dump_source(struct babel_source *s)
1635
{
1636
  debug("Source router_id %lR seqno %d metric %d expires %d\n",
1637
        s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0);
1638
}
1639

    
1640
static void
1641
babel_dump_route(struct babel_route *r)
1642
{
1643
  debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %d\n",
1644
        r->neigh ? r->neigh->addr : IPA_NONE,
1645
        r->neigh ? r->neigh->ifa->ifname : "(none)",
1646
        r->seqno, r->advert_metric, r->metric,
1647
        r->router_id, r->expires ? r->expires-now : 0);
1648
}
1649

    
1650
static void
1651
babel_dump_entry(struct babel_entry *e)
1652
{
1653
  struct babel_source *s;
1654
  struct babel_route *r;
1655

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

    
1658
  WALK_LIST(s,e->sources)
1659
  { debug(" "); babel_dump_source(s); }
1660

    
1661
  WALK_LIST(r,e->routes)
1662
  {
1663
    debug(" ");
1664
    if (r == e->selected_out) debug("*");
1665
    if (r == e->selected_in) debug("+");
1666
    babel_dump_route(r);
1667
  }
1668
}
1669

    
1670
static void
1671
babel_dump_neighbor(struct babel_neighbor *n)
1672
{
1673
  debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n",
1674
        n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
1675
        n->hello_expiry ? n->hello_expiry - now : 0,
1676
        n->ihu_expiry ? n->ihu_expiry - now : 0);
1677
}
1678

    
1679
static void
1680
babel_dump_iface(struct babel_iface *ifa)
1681
{
1682
  struct babel_neighbor *n;
1683

    
1684
  debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n",
1685
        ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
1686
        ifa->cf->hello_interval, ifa->cf->update_interval);
1687

    
1688
  WALK_LIST(n, ifa->neigh_list)
1689
  { debug(" "); babel_dump_neighbor(n); }
1690
}
1691

    
1692
static void
1693
babel_dump(struct proto *P)
1694
{
1695
  struct babel_proto *p = (struct babel_proto *) P;
1696
  struct babel_iface *ifa;
1697

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

    
1700
  WALK_LIST(ifa, p->interfaces)
1701
    babel_dump_iface(ifa);
1702

    
1703
  FIB_WALK(&p->rtable, struct babel_entry, e)
1704
  {
1705
    babel_dump_entry(e);
1706
  }
1707
  FIB_WALK_END;
1708
}
1709

    
1710
static void
1711
babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
1712
{
1713
  buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id);
1714
}
1715

    
1716
static int
1717
babel_get_attr(eattr *a, byte *buf, int buflen UNUSED)
1718
{
1719
  switch (a->id)
1720
  {
1721
  case EA_BABEL_METRIC:
1722
    bsprintf(buf, "metric: %d", a->u.data);
1723
    return GA_FULL;
1724

    
1725
  case EA_BABEL_ROUTER_ID:
1726
  {
1727
    u64 rid = 0;
1728
    memcpy(&rid, a->u.ptr->data, sizeof(u64));
1729
    bsprintf(buf, "router_id: %lR", rid);
1730
    return GA_FULL;
1731
  }
1732

    
1733
  default:
1734
    return GA_UNKNOWN;
1735
  }
1736
}
1737

    
1738
void
1739
babel_show_interfaces(struct proto *P, char *iff)
1740
{
1741
  struct babel_proto *p = (void *) P;
1742
  struct babel_iface *ifa = NULL;
1743
  struct babel_neighbor *nbr = NULL;
1744

    
1745
  if (p->p.proto_state != PS_UP)
1746
  {
1747
    cli_msg(-1023, "%s: is not up", p->p.name);
1748
    cli_msg(0, "");
1749
    return;
1750
  }
1751

    
1752
  cli_msg(-1023, "%s:", p->p.name);
1753
  cli_msg(-1023, "%-10s %-6s %7s %6s %6s",
1754
          "Interface", "State", "RX cost", "Nbrs", "Timer");
1755

    
1756
  WALK_LIST(ifa, p->interfaces)
1757
  {
1758
    if (iff && !patmatch(iff, ifa->iface->name))
1759
      continue;
1760

    
1761
    int nbrs = 0;
1762
    WALK_LIST(nbr, ifa->neigh_list)
1763
        nbrs++;
1764

    
1765
    int timer = MIN(ifa->next_regular, ifa->next_hello) - now;
1766
    cli_msg(-1023, "%-10s %-6s %7u %6u %6u",
1767
            ifa->iface->name, (ifa->up ? "Up" : "Down"), ifa->cf->rxcost, nbrs, MAX(timer, 0));
1768
  }
1769

    
1770
  cli_msg(0, "");
1771
}
1772

    
1773
void
1774
babel_show_neighbors(struct proto *P, char *iff)
1775
{
1776
  struct babel_proto *p = (void *) P;
1777
  struct babel_iface *ifa = NULL;
1778
  struct babel_neighbor *n = NULL;
1779
  struct babel_route *r = NULL;
1780

    
1781
  if (p->p.proto_state != PS_UP)
1782
  {
1783
    cli_msg(-1024, "%s: is not up", p->p.name);
1784
    cli_msg(0, "");
1785
    return;
1786
  }
1787

    
1788
  cli_msg(-1024, "%s:", p->p.name);
1789
  cli_msg(-1024, "%-25s %-10s %6s %6s %10s",
1790
          "IP address", "Interface", "Metric", "Routes", "Next hello");
1791

    
1792
  WALK_LIST(ifa, p->interfaces)
1793
  {
1794
    if (iff && !patmatch(iff, ifa->iface->name))
1795
      continue;
1796

    
1797
    WALK_LIST(n, ifa->neigh_list)
1798
    {
1799
      int rts = 0;
1800
      WALK_LIST(r, n->routes)
1801
        rts++;
1802

    
1803
      int timer = n->hello_expiry - now;
1804
      cli_msg(-1024, "%-25I %-10s %6u %6u %10u",
1805
              n->addr, ifa->iface->name, n->txcost, rts, MAX(timer, 0));
1806
    }
1807
  }
1808

    
1809
  cli_msg(0, "");
1810
}
1811

    
1812
void
1813
babel_show_entries(struct proto *P)
1814
{
1815
  struct babel_proto *p = (void *) P;
1816
  struct babel_source *s = NULL;
1817
  struct babel_route *r = NULL;
1818

    
1819
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1820

    
1821
  if (p->p.proto_state != PS_UP)
1822
  {
1823
    cli_msg(-1025, "%s: is not up", p->p.name);
1824
    cli_msg(0, "");
1825
    return;
1826
  }
1827

    
1828
  cli_msg(-1025, "%s:", p->p.name);
1829
  cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
1830
          "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
1831

    
1832
  FIB_WALK(&p->rtable, struct babel_entry, e)
1833
  {
1834
    r = e->selected_in ? e->selected_in : e->selected_out;
1835

    
1836
    int srcs = 0;
1837
    WALK_LIST(s, e->sources)
1838
      srcs++;
1839

    
1840
    if (r)
1841
    {
1842
      if (r->router_id == p->router_id)
1843
        bsprintf(ridbuf, "%s", "<self>");
1844
      else
1845
        bsprintf(ridbuf, "%lR", r->router_id);
1846

    
1847
      int time = r->expires ? r->expires - now : 0;
1848
      cli_msg(-1025, "%-29N %-23s %6u %5u %7u %7u",
1849
              e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
1850
    }
1851
    else
1852
    {
1853
      cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs);
1854
    }
1855
  }
1856
  FIB_WALK_END;
1857

    
1858
  cli_msg(0, "");
1859
}
1860

    
1861

    
1862
/*
1863
 *        Babel protocol glue
1864
 */
1865

    
1866
/**
1867
 * babel_timer - global timer hook
1868
 * @t: Timer
1869
 *
1870
 * This function is called by the global protocol instance timer and handles
1871
 * expiration of routes and neighbours as well as pruning of the seqno request
1872
 * cache.
1873
 */
1874
static void
1875
babel_timer(timer *t)
1876
{
1877
  struct babel_proto *p = t->data;
1878

    
1879
  babel_expire_routes(p);
1880
  babel_expire_seqno_requests(p);
1881
  babel_expire_neighbors(p);
1882
}
1883

    
1884
static inline void
1885
babel_kick_timer(struct babel_proto *p)
1886
{
1887
  if (p->timer->expires > (now + 1))
1888
    tm_start(p->timer, 1);
1889
}
1890

    
1891

    
1892
static struct ea_list *
1893
babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id)
1894
{
1895
  struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr));
1896
  struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64));
1897
  rid->length = sizeof(u64);
1898
  memcpy(&rid->data, &router_id, sizeof(u64));
1899

    
1900
  l->next = next;
1901
  l->flags = EALF_SORTED;
1902
  l->count = 2;
1903

    
1904
  l->attrs[0].id = EA_BABEL_METRIC;
1905
  l->attrs[0].flags = 0;
1906
  l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
1907
  l->attrs[0].u.data = metric;
1908

    
1909
  l->attrs[1].id = EA_BABEL_ROUTER_ID;
1910
  l->attrs[1].flags = 0;
1911
  l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
1912
  l->attrs[1].u.ptr = rid;
1913

    
1914
  return l;
1915
}
1916

    
1917

    
1918
static int
1919
babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool)
1920
{
1921
  struct babel_proto *p = (void *) P;
1922

    
1923
  /* Prepare attributes with initial values */
1924
  if ((*rt)->attrs->source != RTS_BABEL)
1925
    *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
1926

    
1927
  return 0;
1928
}
1929

    
1930
static struct ea_list *
1931
babel_make_tmp_attrs(struct rte *rt, struct linpool *pool)
1932
{
1933
  return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id);
1934
}
1935

    
1936
static void
1937
babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs)
1938
{
1939
  rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
1940
}
1941

    
1942
/*
1943
 * babel_rt_notify - core tells us about new route (possibly our own),
1944
 * so store it into our data structures.
1945
 */
1946
static void
1947
babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net,
1948
                struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
1949
{
1950
  struct babel_proto *p = (void *) P;
1951
  struct babel_entry *e;
1952
  struct babel_route *r;
1953

    
1954
  if (new)
1955
  {
1956
    /* Update */
1957
    e = babel_get_entry(p, net->n.addr);
1958

    
1959
    if (new->attrs->src->proto != P)
1960
    {
1961
      r = babel_get_route(e, NULL);
1962
      r->seqno = p->update_seqno;
1963
      r->router_id = p->router_id;
1964
      r->metric = 0;        /* FIXME: should be selectable */
1965
    }
1966
    else
1967
      r = e->selected_in;
1968

    
1969
    if (r != e->selected_out)
1970
    {
1971
      e->selected_out = r;
1972
      e->updated = now;
1973
      babel_trigger_update(p);
1974
    }
1975
  }
1976
  else
1977
  {
1978
    /* Withdraw */
1979
    e = babel_find_entry(p, net->n.addr);
1980
    if (!e || !e->selected_out)
1981
      return;
1982

    
1983
    if (OUR_ROUTE(e->selected_out))
1984
    {
1985
      /*
1986
       * We originate this route, so set its metric to infinity and set an
1987
       * expiry time. This causes a retraction to be sent, and later the route
1988
       * to be flushed once the hold time has passed.
1989
       */
1990
      e->selected_out->metric = BABEL_INFINITY;
1991
      e->selected_out->expires = now + BABEL_HOLD_TIME;
1992
      e->updated = now;
1993
      babel_trigger_update(p);
1994
    }
1995
    else
1996
    {
1997
      /*
1998
       * This is a route originating from someone else that was lost; presumably
1999
       * because an export filter was updated to filter it. This means we can't
2000
       * set the metric to infinity (it would be overridden on subsequent
2001
       * updates from the peer originating the route), so just clear the
2002
       * exported route.
2003
       *
2004
       * This causes peers to expire the route after a while (like if we just
2005
       * shut down), but it's the best we can do in these circumstances; and
2006
       * since export filters presumably aren't updated that often this is
2007
       * acceptable.
2008
       */
2009
      e->selected_out = NULL;
2010
    }
2011
  }
2012
}
2013

    
2014
static int
2015
babel_rte_better(struct rte *new, struct rte *old)
2016
{
2017
  return new->u.babel.metric < old->u.babel.metric;
2018
}
2019

    
2020
static int
2021
babel_rte_same(struct rte *new, struct rte *old)
2022
{
2023
  return ((new->u.babel.router_id == old->u.babel.router_id) &&
2024
          (new->u.babel.metric == old->u.babel.metric));
2025
}
2026

    
2027

    
2028
static struct proto *
2029
babel_init(struct proto_config *CF)
2030
{
2031
  struct proto *P = proto_new(CF);
2032

    
2033
  P->main_channel = proto_add_channel(P, proto_cf_main_channel(CF));
2034

    
2035
  P->if_notify = babel_if_notify;
2036
  P->rt_notify = babel_rt_notify;
2037
  P->import_control = babel_import_control;
2038
  P->make_tmp_attrs = babel_make_tmp_attrs;
2039
  P->store_tmp_attrs = babel_store_tmp_attrs;
2040
  P->rte_better = babel_rte_better;
2041
  P->rte_same = babel_rte_same;
2042

    
2043
  return P;
2044
}
2045

    
2046
static int
2047
babel_start(struct proto *P)
2048
{
2049
  struct babel_proto *p = (void *) P;
2050
  struct babel_config *cf = (void *) P->cf;
2051

    
2052
  fib_init(&p->rtable, P->pool, NET_IP6, sizeof(struct babel_entry),
2053
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2054
  init_list(&p->interfaces);
2055
  p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1);
2056
  tm_start(p->timer, 2);
2057
  p->update_seqno = 1;
2058
  p->router_id = proto_get_router_id(&cf->c);
2059

    
2060
  p->route_slab = sl_new(P->pool, sizeof(struct babel_route));
2061
  p->source_slab = sl_new(P->pool, sizeof(struct babel_source));
2062
  p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node));
2063
  p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request));
2064
  init_list(&p->seqno_cache);
2065

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

    
2068
  return PS_UP;
2069
}
2070

    
2071
static inline void
2072
babel_iface_shutdown(struct babel_iface *ifa)
2073
{
2074
  if (ifa->sk)
2075
  {
2076
    babel_send_wildcard_retraction(ifa);
2077
    babel_send_queue(ifa);
2078
  }
2079
}
2080

    
2081
static int
2082
babel_shutdown(struct proto *P)
2083
{
2084
  struct babel_proto *p = (void *) P;
2085
  struct babel_iface *ifa;
2086

    
2087
  TRACE(D_EVENTS, "Shutdown requested");
2088

    
2089
  WALK_LIST(ifa, p->interfaces)
2090
    babel_iface_shutdown(ifa);
2091

    
2092
  return PS_DOWN;
2093
}
2094

    
2095
static int
2096
babel_reconfigure(struct proto *P, struct proto_config *CF)
2097
{
2098
  struct babel_proto *p = (void *) P;
2099
  struct babel_config *new = (void *) CF;
2100

    
2101
  TRACE(D_EVENTS, "Reconfiguring");
2102

    
2103
  if (!proto_configure_channel(P, &P->main_channel, proto_cf_main_channel(CF)))
2104
    return 0;
2105

    
2106
  p->p.cf = CF;
2107
  babel_reconfigure_ifaces(p, new);
2108

    
2109
  babel_trigger_update(p);
2110
  babel_kick_timer(p);
2111

    
2112
  return 1;
2113
}
2114

    
2115

    
2116
struct protocol proto_babel = {
2117
  .name =                "Babel",
2118
  .template =                "babel%d",
2119
  .attr_class =                EAP_BABEL,
2120
  .preference =                DEF_PREF_BABEL,
2121
  .channel_mask =        NB_IP6,
2122
  .proto_size =                sizeof(struct babel_proto),
2123
  .config_size =        sizeof(struct babel_config),
2124
  .init =                babel_init,
2125
  .dump =                babel_dump,
2126
  .start =                babel_start,
2127
  .shutdown =                babel_shutdown,
2128
  .reconfigure =        babel_reconfigure,
2129
  .get_route_info =        babel_get_route_info,
2130
  .get_attr =                babel_get_attr
2131
};