Statistics
| Branch: | Revision:

iof-bird-daemon / proto / babel / babel.c @ b2b84359

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 *ap0 = allocz(RTA_MAX_SIZE);
475
    *ap0 = (rta) {
476
      .src = p->p.main_source,
477
      .source = RTS_BABEL,
478
      .scope = SCOPE_UNIVERSE,
479
      .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_UNICAST,
480
      .from = r->neigh->addr,
481
      .nh.iface = r->neigh->ifa->iface,
482
    };
483

    
484
    if (r->metric < BABEL_INFINITY)
485
      ap0->nh.gw = r->next_hop;
486

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
644
  babel_enqueue(&msg, ifa);
645

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
751
    if (!r)
752
      continue;
753

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

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

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

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

    
777
    babel_enqueue(&msg, ifa);
778

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

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

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

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

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

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

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

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

    
823
  p->triggered = 1;
824
}
825

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

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

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

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

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

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

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

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

    
861

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

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

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

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

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

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

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

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

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

    
947
  return 1;
948
}
949

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

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

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

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

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

    
983

    
984
/*
985
 *        TLV handlers
986
 */
987

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1129
      if (!e)
1130
        return;
1131

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

    
1135
      if (!r)
1136
        return;
1137

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

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

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

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

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

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

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

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

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

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

    
1199
  babel_select_route(e);
1200
}
1201

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

    
1208
  /* RFC 6126 3.8.1.1 */
1209

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

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

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

    
1234

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

    
1241
  /* RFC 6126 3.8.1.2 */
1242

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

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

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

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

    
1276

    
1277
/*
1278
 *        Babel interfaces
1279
 */
1280

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1441
  return NULL;
1442
}
1443

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1504
  olock_acquire(lock);
1505
}
1506

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

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

    
1516
  rem_node(NODE ifa);
1517

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

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

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

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

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

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

    
1541
    return;
1542
  }
1543

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

    
1546
  if (!ifa)
1547
    return;
1548

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

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

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

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

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

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

    
1575
  ifa->cf = new;
1576

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

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

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

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

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

    
1592
  return 1;
1593
}
1594

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

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

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

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

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

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

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

    
1627

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
1818
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1819

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

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

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

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

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

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

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

    
1860

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

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

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

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

    
1890

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

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

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

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

    
1913
  return l;
1914
}
1915

    
1916

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

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

    
1926
  return 0;
1927
}
1928

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

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

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

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

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

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

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

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

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

    
2026

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

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

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

    
2042
  return P;
2043
}
2044

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

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

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

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

    
2067
  return PS_UP;
2068
}
2069

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

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

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

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

    
2091
  return PS_DOWN;
2092
}
2093

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

    
2100
  TRACE(D_EVENTS, "Reconfiguring");
2101

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

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

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

    
2111
  return 1;
2112
}
2113

    
2114

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