Statistics
| Branch: | Revision:

iof-bird-daemon / proto / babel / babel.c @ 4324025f

History | View | Annotate | Download (56.4 KB)

1
/*
2
 *        BIRD -- The Babel protocol
3
 *
4
 *        Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 *
8
 *        This file contains the main routines for handling and sending TLVs, as
9
 *        well as timers and interaction with the nest.
10
 */
11

    
12
/**
13
 * DOC: The Babel protocol
14
 *
15
 * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
16
 * robust and efficient both in ordinary wired networks and in wireless mesh
17
 * networks.
18
 *
19
 * The Babel protocol keeps state for each neighbour in a &babel_neighbor
20
 * struct, tracking received Hello and I Heard You (IHU) messages. A
21
 * &babel_interface struct keeps hello and update times for each interface, and
22
 * a separate hello seqno is maintained for each interface.
23
 *
24
 * For each prefix, Babel keeps track of both the possible routes (with next hop
25
 * and router IDs), as well as the feasibility distance for each prefix and
26
 * router id. The prefix itself is tracked in a &babel_entry struct, while the
27
 * possible routes for the prefix are tracked as &babel_route entries and the
28
 * feasibility distance is maintained through &babel_source structures.
29
 *
30
 * The main route selection is done in babel_select_route(). This is called when
31
 * an entry is updated by receiving updates from the network or when modified by
32
 * internal timers. It performs feasibility checks on the available routes for
33
 * the prefix and selects the one with the lowest metric to be announced to the
34
 * core.
35
 */
36

    
37
#include <stdlib.h>
38
#include "babel.h"
39

    
40

    
41
#define OUR_ROUTE(r) (r->neigh == NULL)
42

    
43
/*
44
 * Is one number greater or equal than another mod 2^16? This is based on the
45
 * definition of serial number space in RFC 1982. Note that arguments are of
46
 * uint type to avoid integer promotion to signed integer.
47
 */
48
static inline int ge_mod64k(uint a, uint b)
49
{ return (u16)(a - b) < 0x8000; }
50

    
51
static void babel_dump_entry(struct babel_entry *e);
52
static void babel_dump_route(struct babel_route *r);
53
static void babel_select_route(struct babel_entry *e);
54
static void babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n);
55
static void babel_send_wildcard_request(struct babel_iface *ifa);
56
static int  babel_cache_seqno_request(struct babel_proto *p, net_addr *n, u64 router_id, u16 seqno);
57
static void babel_trigger_iface_update(struct babel_iface *ifa);
58
static void babel_trigger_update(struct babel_proto *p);
59
static void babel_send_seqno_request(struct babel_entry *e);
60
static inline void babel_kick_timer(struct babel_proto *p);
61
static inline void babel_iface_kick_timer(struct babel_iface *ifa);
62

    
63

    
64
/*
65
 *        Functions to maintain data structures
66
 */
67

    
68
static void
69
babel_init_entry(void *E)
70
{
71
  struct babel_entry *e = E;
72

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

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

    
85
static struct babel_entry *
86
babel_get_entry(struct babel_proto *p, const net_addr *n)
87
{
88
  struct fib *rtable = (n->type == NET_IP4) ? &p->ip4_rtable : &p->ip6_rtable;
89
  struct babel_entry *e = fib_get(rtable, n);
90
  e->proto = p;
91
  return e;
92
}
93

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

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

    
103
  return NULL;
104
}
105

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

    
112
  if (s)
113
    return s;
114

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

    
122
  return s;
123
}
124

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

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

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

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

    
150
  return NULL;
151
}
152

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

    
159
  if (r)
160
    return r;
161

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

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

    
174
  return r;
175
}
176

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

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

    
185
  rem_node(NODE r);
186

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

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

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

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

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

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

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

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

    
225
  r->refresh_time = 0;
226
}
227

    
228
static void
229
babel_expire_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
230
{
231
  struct babel_route *r, *rx;
232
  struct fib_iterator fit;
233

    
234
  FIB_ITERATE_INIT(&fit, rtable);
235

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

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

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

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

    
261
      FIB_ITERATE_PUT(&fit);
262
      babel_select_route(e);
263
      goto loop;
264
    }
265

    
266
    babel_expire_sources(e);
267

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

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

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

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

    
295
  return NULL;
296
}
297

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

    
303
  if (nbr)
304
    return nbr;
305

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

    
313
  return nbr;
314
}
315

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

    
322
  TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
323

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

    
330
    babel_flush_route(r);
331

    
332
    if (selected)
333
      babel_select_route(e);
334
  }
335

    
336
  rem_node(NODE nbr);
337
  mb_free(nbr);
338
}
339

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

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

    
351
  if (nbr->hello_cnt < 16)
352
    nbr->hello_cnt++;
353

    
354
  if (!nbr->hello_map)
355
    babel_flush_neighbor(nbr);
356
}
357

    
358
static void
359
babel_expire_neighbors(struct babel_proto *p)
360
{
361
  struct babel_iface *ifa;
362
  struct babel_neighbor *nbr, *nbx;
363

    
364
  WALK_LIST(ifa, p->interfaces)
365
  {
366
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
367
    {
368
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now)
369
        babel_expire_ihu(nbr);
370

    
371
      if (nbr->hello_expiry && nbr->hello_expiry <= now)
372
        babel_expire_hello(nbr);
373
    }
374
  }
375
}
376

    
377

    
378
/*
379
 *        Best route selection
380
 */
381

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

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

    
413
  if (!map) return BABEL_INFINITY;
414
  cnt = u32_popcount(map); // number of bits set
415
  missed = n->hello_cnt-cnt;
416

    
417
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
418
  {
419
    /* ETX - Appendix 2.2 in the RFC.
420

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

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

    
439

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

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

    
466

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

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

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

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

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

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

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

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

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

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

    
564
      e->selected_in->metric = BABEL_INFINITY;
565
      e->updated = now;
566

    
567
      babel_send_seqno_request(e);
568
      babel_announce_rte(p, e);
569

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

    
582
      e->selected_in = NULL;
583
      e->updated = now;
584
      babel_announce_rte(p, e);
585
    }
586
  }
587
}
588

    
589
/*
590
 *        Functions to send replies
591
 */
592

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

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

    
601
  msg.type = BABEL_TLV_ACK;
602
  msg.ack.nonce = nonce;
603

    
604
  babel_send_unicast(&msg, ifa, dest);
605
}
606

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

    
612
  msg->type = BABEL_TLV_IHU;
613
  msg->ihu.addr = n->addr;
614
  msg->ihu.rxcost = babel_compute_rxcost(n);
615
  msg->ihu.interval = ifa->cf->ihu_interval;
616

    
617
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %d",
618
        msg->ihu.addr, msg->ihu.rxcost, msg->ihu.interval);
619
}
620

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

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

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

    
647
  msg.type = BABEL_TLV_HELLO;
648
  msg.hello.seqno = ifa->hello_seqno++;
649
  msg.hello.interval = ifa->cf->hello_interval;
650

    
651
  TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %d",
652
        ifa->ifname, msg.hello.seqno, msg.hello.interval);
653

    
654
  babel_enqueue(&msg, ifa);
655

    
656
  if (send_ihu)
657
    babel_send_ihus(ifa);
658
}
659

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

    
667
  TRACE(D_PACKETS, "Sending route request for %N to %I",
668
        e->n.addr, n->addr);
669

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

    
673
  babel_send_unicast(&msg, ifa, n->addr);
674
}
675

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

    
682
  TRACE(D_PACKETS, "Sending wildcard route request on %s",
683
        ifa->ifname);
684

    
685
  msg.type = BABEL_TLV_ROUTE_REQUEST;
686
  msg.route_request.full = 1;
687

    
688
  babel_enqueue(&msg, ifa);
689
}
690

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

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

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

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

    
713
  WALK_LIST(ifa, p->interfaces)
714
    babel_enqueue(&msg, ifa);
715
}
716

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

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

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

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

    
739
  babel_send_unicast(&msg, ifa, r->neigh->addr);
740
}
741

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

    
757
  FIB_WALK(rtable, struct babel_entry, e)
758
  {
759
    struct babel_route *r = e->selected_out;
760

    
761
    if (!r)
762
      continue;
763

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

    
772
    /* Skip routes that weren't updated since 'changed' time */
773
    if (e->updated < changed)
774
      continue;
775

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

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

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

    
790
    babel_enqueue(&msg, ifa);
791

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

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

    
809
static void
810
babel_send_update(struct babel_iface *ifa, bird_clock_t changed)
811
{
812
  struct babel_proto *p = ifa->proto;
813

    
814
  babel_send_update_(ifa, changed, &p->ip4_rtable);
815
  babel_send_update_(ifa, changed, &p->ip6_rtable);
816
}
817

    
818
static void
819
babel_trigger_iface_update(struct babel_iface *ifa)
820
{
821
  struct babel_proto *p = ifa->proto;
822

    
823
  /* Interface not active or already scheduled */
824
  if (!ifa->up || ifa->want_triggered)
825
    return;
826

    
827
  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
828
        ifa->iface->name, p->update_seqno);
829

    
830
  ifa->want_triggered = now;
831
  babel_iface_kick_timer(ifa);
832
}
833

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

    
841
  struct babel_iface *ifa;
842
  WALK_LIST(ifa, p->interfaces)
843
    babel_trigger_iface_update(ifa);
844

    
845
  p->triggered = 1;
846
}
847

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

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

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

    
863
  babel_enqueue(&msg, ifa);
864
}
865

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

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

    
874
  msg.type = BABEL_TLV_UPDATE;
875
  msg.update.wildcard = 1;
876
  msg.update.interval = ifa->cf->update_interval;
877
  msg.update.seqno = p->update_seqno;
878
  msg.update.metric = BABEL_INFINITY;
879

    
880
  babel_enqueue(&msg, ifa);
881
}
882

    
883

    
884
/*
885
 *        TLV handler helpers
886
 */
887

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

    
899
  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
900

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

    
924
  /* Current entry */
925
  n->hello_map = (n->hello_map << 1) | 1;
926
  n->next_hello_seqno = seqno+1;
927
  if (n->hello_cnt < 16) n->hello_cnt++;
928
  n->hello_expiry = now + BABEL_HELLO_EXPIRY_FACTOR(interval);
929
}
930

    
931
static void
932
babel_expire_seqno_requests(struct babel_proto *p)
933
{
934
  struct babel_seqno_request *n, *nx;
935
  WALK_LIST_DELSAFE(n, nx, p->seqno_cache)
936
  {
937
    if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now)
938
    {
939
      rem_node(NODE n);
940
      sl_free(p->seqno_slab, n);
941
    }
942
  }
943
}
944

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

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

    
961
  /* no entries found */
962
  r = sl_alloc(p->seqno_slab);
963
  net_copy(&r->net, n);
964
  r->router_id = router_id;
965
  r->seqno = seqno;
966
  r->updated = now;
967
  add_tail(&p->seqno_cache, NODE r);
968

    
969
  return 1;
970
}
971

    
972
static void
973
babel_forward_seqno_request(struct babel_entry *e,
974
                            struct babel_msg_seqno_request *in,
975
                            ip_addr sender)
976
{
977
  struct babel_proto *p = e->proto;
978
  struct babel_route *r;
979

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

    
983
  WALK_LIST(r, e->routes)
984
  {
985
    if ((r->router_id == in->router_id) &&
986
        !OUR_ROUTE(r) &&
987
        !ipa_equal(r->neigh->addr, sender))
988
    {
989
      if (!babel_cache_seqno_request(p, e->n.addr, in->router_id, in->seqno))
990
        return;
991

    
992
      union babel_msg msg = {};
993
      msg.type = BABEL_TLV_SEQNO_REQUEST;
994
      msg.seqno_request.hop_count = in->hop_count-1;
995
      msg.seqno_request.seqno = in->seqno;
996
      msg.seqno_request.router_id = in->router_id;
997
      net_copy(&msg.seqno_request.net, e->n.addr);
998

    
999
      babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr);
1000
      return;
1001
    }
1002
  }
1003
}
1004

    
1005

    
1006
/*
1007
 *        TLV handlers
1008
 */
1009

    
1010
void
1011
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
1012
{
1013
  struct babel_proto *p = ifa->proto;
1014
  struct babel_msg_ack_req *msg = &m->ack_req;
1015

    
1016
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %d",
1017
        msg->nonce, msg->interval);
1018

    
1019
  babel_send_ack(ifa, msg->sender, msg->nonce);
1020
}
1021

    
1022
void
1023
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
1024
{
1025
  struct babel_proto *p = ifa->proto;
1026
  struct babel_msg_hello *msg = &m->hello;
1027

    
1028
  TRACE(D_PACKETS, "Handling hello seqno %d interval %d",
1029
        msg->seqno, msg->interval);
1030

    
1031
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1032
  babel_update_hello_history(n, msg->seqno, msg->interval);
1033
  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
1034
    babel_send_ihu(ifa, n);
1035
}
1036

    
1037
void
1038
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
1039
{
1040
  struct babel_proto *p = ifa->proto;
1041
  struct babel_msg_ihu *msg = &m->ihu;
1042

    
1043
  /* Ignore IHUs that are not about us */
1044
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
1045
    return;
1046

    
1047
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d",
1048
        msg->rxcost, msg->interval);
1049

    
1050
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1051
  n->txcost = msg->rxcost;
1052
  n->ihu_expiry = now + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1053
}
1054

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

    
1072
  struct babel_neighbor *nbr;
1073
  struct babel_entry *e;
1074
  struct babel_source *s;
1075
  struct babel_route *r;
1076
  node *n;
1077
  int feasible;
1078

    
1079
  if (msg->wildcard)
1080
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
1081
  else
1082
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
1083
          &msg->net, msg->seqno, msg->metric);
1084

    
1085
  nbr = babel_find_neighbor(ifa, msg->sender);
1086
  if (!nbr)
1087
  {
1088
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
1089
    return;
1090
  }
1091

    
1092
  if (msg->router_id == p->router_id)
1093
  {
1094
    DBG("Babel: Ignoring update for our own router ID.\n");
1095
    return;
1096
  }
1097

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

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

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

    
1158
      if (!e)
1159
        return;
1160

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

    
1164
      if (!r)
1165
        return;
1166

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

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

    
1175
  e = babel_get_entry(p, &msg->net);
1176
  r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
1177
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1178
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1179

    
1180
  if (!r)
1181
  {
1182
    if (!feasible)
1183
      return;
1184

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

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

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

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

    
1216
    r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1217
    r->expires = now + r->expiry_interval;
1218
    if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
1219
      r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
1220

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

    
1228
  babel_select_route(e);
1229
}
1230

    
1231
void
1232
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
1233
{
1234
  struct babel_proto *p = ifa->proto;
1235
  struct babel_msg_route_request *msg = &m->route_request;
1236

    
1237
  /* RFC 6126 3.8.1.1 */
1238

    
1239
  /* Wildcard request - full update on the interface */
1240
  if (msg->full)
1241
  {
1242
    TRACE(D_PACKETS, "Handling wildcard route request");
1243
    ifa->want_triggered = 1;
1244
    return;
1245
  }
1246

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

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

    
1263

    
1264
void
1265
babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
1266
{
1267
  struct babel_proto *p = ifa->proto;
1268
  struct babel_msg_seqno_request *msg = &m->seqno_request;
1269

    
1270
  /* RFC 6126 3.8.1.2 */
1271

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

    
1275
  /* Ignore if we have no such entry or entry has infinite metric */
1276
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1277
  if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
1278
    return;
1279

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

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

    
1305

    
1306
/*
1307
 *        Babel interfaces
1308
 */
1309

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

    
1339
  if (now >= ifa->next_hello)
1340
  {
1341
    babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
1342
                           ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
1343
    ifa->next_hello +=  hello_period * (1 + (now - ifa->next_hello) / hello_period);
1344
  }
1345

    
1346
  if (now >= ifa->next_regular)
1347
  {
1348
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
1349
    babel_send_update(ifa, 0);
1350
    ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period);
1351
    ifa->want_triggered = 0;
1352
    p->triggered = 0;
1353
  }
1354
  else if (ifa->want_triggered && (now >= ifa->next_triggered))
1355
  {
1356
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
1357
    babel_send_update(ifa, ifa->want_triggered);
1358
    ifa->next_triggered = now + MIN(5, update_period / 2 + 1);
1359
    ifa->want_triggered = 0;
1360
    p->triggered = 0;
1361
  }
1362

    
1363
  bird_clock_t next_event = MIN(ifa->next_hello, ifa->next_regular);
1364
  tm_start(ifa->timer, ifa->want_triggered ? 1 : (next_event - now));
1365
}
1366

    
1367
static inline void
1368
babel_iface_kick_timer(struct babel_iface *ifa)
1369
{
1370
  if (ifa->timer->expires > (now + 1))
1371
    tm_start(ifa->timer, 1);
1372
}
1373

    
1374
static void
1375
babel_iface_start(struct babel_iface *ifa)
1376
{
1377
  struct babel_proto *p = ifa->proto;
1378

    
1379
  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
1380

    
1381
  ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1;
1382
  ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1;
1383
  ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1);
1384
  ifa->want_triggered = 0;        /* We send an immediate update (below) */
1385
  tm_start(ifa->timer, 1);
1386
  ifa->up = 1;
1387

    
1388
  babel_send_hello(ifa, 0);
1389
  babel_send_wildcard_retraction(ifa);
1390
  babel_send_wildcard_request(ifa);
1391
  babel_send_update(ifa, 0);        /* Full update */
1392
}
1393

    
1394
static void
1395
babel_iface_stop(struct babel_iface *ifa)
1396
{
1397
  struct babel_proto *p = ifa->proto;
1398
  struct babel_neighbor *nbr;
1399
  struct babel_route *r;
1400
  node *n;
1401

    
1402
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1403

    
1404
  /*
1405
   * Rather than just flushing the neighbours, we set the metric of their routes
1406
   * to infinity. This allows us to keep the neighbour hello state for when the
1407
   * interface comes back up. The routes will also be kept until they expire.
1408
   */
1409
  WALK_LIST(nbr, ifa->neigh_list)
1410
  {
1411
    WALK_LIST(n, nbr->routes)
1412
    {
1413
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1414
      r->metric = BABEL_INFINITY;
1415
      r->expires = now + r->expiry_interval;
1416
      babel_select_route(r->e);
1417
    }
1418
  }
1419

    
1420
  tm_stop(ifa->timer);
1421
  ifa->up = 0;
1422
}
1423

    
1424
static inline int
1425
babel_iface_link_up(struct babel_iface *ifa)
1426
{
1427
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
1428
}
1429

    
1430
static void
1431
babel_iface_update_state(struct babel_iface *ifa)
1432
{
1433
  int up = ifa->sk && babel_iface_link_up(ifa);
1434

    
1435
  if (up == ifa->up)
1436
    return;
1437

    
1438
  if (up)
1439
    babel_iface_start(ifa);
1440
  else
1441
    babel_iface_stop(ifa);
1442
}
1443

    
1444
static void
1445
babel_iface_update_buffers(struct babel_iface *ifa)
1446
{
1447
  if (!ifa->sk)
1448
    return;
1449

    
1450
  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
1451
  uint rbsize = ifa->cf->rx_buffer ?: mtu;
1452
  uint tbsize = ifa->cf->tx_length ?: mtu;
1453
  rbsize = MAX(rbsize, tbsize);
1454

    
1455
  sk_set_rbsize(ifa->sk, rbsize);
1456
  sk_set_tbsize(ifa->sk, tbsize);
1457

    
1458
  ifa->tx_length = tbsize - BABEL_OVERHEAD;
1459
}
1460

    
1461
static struct babel_iface*
1462
babel_find_iface(struct babel_proto *p, struct iface *what)
1463
{
1464
  struct babel_iface *ifa;
1465

    
1466
  WALK_LIST (ifa, p->interfaces)
1467
    if (ifa->iface == what)
1468
      return ifa;
1469

    
1470
  return NULL;
1471
}
1472

    
1473
static void
1474
babel_iface_locked(struct object_lock *lock)
1475
{
1476
  struct babel_iface *ifa = lock->data;
1477
  struct babel_proto *p = ifa->proto;
1478

    
1479
  if (!babel_open_socket(ifa))
1480
  {
1481
    log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
1482
    return;
1483
  }
1484

    
1485
  babel_iface_update_buffers(ifa);
1486
  babel_iface_update_state(ifa);
1487
}
1488

    
1489
static void
1490
babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
1491
{
1492
  struct babel_iface *ifa;
1493

    
1494
  TRACE(D_EVENTS, "Adding interface %s", new->name);
1495

    
1496
  pool *pool = rp_new(p->p.pool, new->name);
1497

    
1498
  ifa = mb_allocz(pool, sizeof(struct babel_iface));
1499
  ifa->proto = p;
1500
  ifa->iface = new;
1501
  ifa->cf = ic;
1502
  ifa->pool = pool;
1503
  ifa->ifname = new->name;
1504

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

    
1507
  ip_addr addr4 = IPA_NONE;
1508
  struct ifa *addr;
1509
  WALK_LIST(addr, new->addrs)
1510
  {
1511
    if (ipa_is_link_local(addr->ip))
1512
      ifa->addr = addr->ip;
1513

    
1514
    if (ipa_zero(addr4) && ipa_is_ip4(addr->ip))
1515
      addr4 = addr->ip;
1516
  }
1517

    
1518
  ifa->next_hop_ip4 = ipa_nonzero(ic->next_hop_ip4) ? ic->next_hop_ip4 : addr4;
1519
  ifa->next_hop_ip6 = ipa_nonzero(ic->next_hop_ip6) ? ic->next_hop_ip6 : ifa->addr;
1520

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

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

    
1527
  init_list(&ifa->neigh_list);
1528
  ifa->hello_seqno = 1;
1529

    
1530
  ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0);
1531

    
1532
  init_list(&ifa->msg_queue);
1533
  ifa->send_event = ev_new(ifa->pool);
1534
  ifa->send_event->hook = babel_send_queue;
1535
  ifa->send_event->data = ifa;
1536

    
1537
  struct object_lock *lock = olock_new(ifa->pool);
1538
  lock->type = OBJLOCK_UDP;
1539
  lock->addr = IP6_BABEL_ROUTERS;
1540
  lock->port = ifa->cf->port;
1541
  lock->iface = ifa->iface;
1542
  lock->hook = babel_iface_locked;
1543
  lock->data = ifa;
1544

    
1545
  olock_acquire(lock);
1546
}
1547

    
1548
static void
1549
babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
1550
{
1551
  TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
1552

    
1553
  struct babel_neighbor *n;
1554
  WALK_LIST_FIRST(n, ifa->neigh_list)
1555
    babel_flush_neighbor(n);
1556

    
1557
  rem_node(NODE ifa);
1558

    
1559
  rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
1560
}
1561

    
1562
static void
1563
babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
1564
{
1565
  struct babel_proto *p = (void *) P;
1566
  struct babel_config *cf = (void *) P->cf;
1567

    
1568
  if (iface->flags & IF_IGNORE)
1569
    return;
1570

    
1571
  if (flags & IF_CHANGE_UP)
1572
  {
1573
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, iface->addr);
1574

    
1575
    /* we only speak multicast */
1576
    if (!(iface->flags & IF_MULTICAST))
1577
      return;
1578

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

    
1582
    return;
1583
  }
1584

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

    
1587
  if (!ifa)
1588
    return;
1589

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

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

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

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

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

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

    
1616
  ifa->cf = new;
1617

    
1618
  if (ipa_nonzero(new->next_hop_ip4))
1619
    ifa->next_hop_ip4 = new->next_hop_ip4;
1620
  else
1621
  {
1622
    ifa->next_hop_ip4 = IPA_NONE;
1623

    
1624
    struct ifa *addr;
1625
    WALK_LIST(addr, ifa->iface->addrs)
1626
      if (ipa_is_ip4(addr->ip))
1627
      {
1628
        ifa->next_hop_ip4 = addr->ip;
1629
        break;
1630
      }
1631
  }
1632

    
1633
  ifa->next_hop_ip6 = ipa_nonzero(new->next_hop_ip6) ? new->next_hop_ip6 : ifa->addr;
1634

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

    
1638
  if (ifa->next_hello > (now + new->hello_interval))
1639
    ifa->next_hello = now + (random() % new->hello_interval) + 1;
1640

    
1641
  if (ifa->next_regular > (now + new->update_interval))
1642
    ifa->next_regular = now + (random() % new->update_interval) + 1;
1643

    
1644
  if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
1645
    babel_iface_update_buffers(ifa);
1646

    
1647
  if (new->check_link != old->check_link)
1648
    babel_iface_update_state(ifa);
1649

    
1650
  if (ifa->up)
1651
    babel_iface_kick_timer(ifa);
1652

    
1653
  return 1;
1654
}
1655

    
1656
static void
1657
babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
1658
{
1659
  struct iface *iface;
1660

    
1661
  WALK_LIST(iface, iface_list)
1662
  {
1663
    if (! (iface->flags & IF_UP))
1664
      continue;
1665

    
1666
    struct babel_iface *ifa = babel_find_iface(p, iface);
1667
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1668

    
1669
    if (ifa && ic)
1670
    {
1671
      if (babel_reconfigure_iface(p, ifa, ic))
1672
        continue;
1673

    
1674
      /* Hard restart */
1675
      log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
1676
      babel_remove_iface(p, ifa);
1677
      babel_add_iface(p, iface, ic);
1678
    }
1679

    
1680
    if (ifa && !ic)
1681
      babel_remove_iface(p, ifa);
1682

    
1683
    if (!ifa && ic)
1684
      babel_add_iface(p, iface, ic);
1685
  }
1686
}
1687

    
1688

    
1689
/*
1690
 *        Debugging and info output functions
1691
 */
1692

    
1693
static void
1694
babel_dump_source(struct babel_source *s)
1695
{
1696
  debug("Source router_id %lR seqno %d metric %d expires %d\n",
1697
        s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0);
1698
}
1699

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

    
1710
static void
1711
babel_dump_entry(struct babel_entry *e)
1712
{
1713
  struct babel_source *s;
1714
  struct babel_route *r;
1715

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

    
1718
  WALK_LIST(s,e->sources)
1719
  { debug(" "); babel_dump_source(s); }
1720

    
1721
  WALK_LIST(r,e->routes)
1722
  {
1723
    debug(" ");
1724
    if (r == e->selected_out) debug("*");
1725
    if (r == e->selected_in) debug("+");
1726
    babel_dump_route(r);
1727
  }
1728
}
1729

    
1730
static void
1731
babel_dump_neighbor(struct babel_neighbor *n)
1732
{
1733
  debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n",
1734
        n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
1735
        n->hello_expiry ? n->hello_expiry - now : 0,
1736
        n->ihu_expiry ? n->ihu_expiry - now : 0);
1737
}
1738

    
1739
static void
1740
babel_dump_iface(struct babel_iface *ifa)
1741
{
1742
  struct babel_neighbor *n;
1743

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

    
1749
  WALK_LIST(n, ifa->neigh_list)
1750
  { debug(" "); babel_dump_neighbor(n); }
1751
}
1752

    
1753
static void
1754
babel_dump(struct proto *P)
1755
{
1756
  struct babel_proto *p = (struct babel_proto *) P;
1757
  struct babel_iface *ifa;
1758

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

    
1761
  WALK_LIST(ifa, p->interfaces)
1762
    babel_dump_iface(ifa);
1763

    
1764
  FIB_WALK(&p->ip4_rtable, struct babel_entry, e)
1765
  {
1766
    babel_dump_entry(e);
1767
  }
1768
  FIB_WALK_END;
1769
  FIB_WALK(&p->ip6_rtable, struct babel_entry, e)
1770
  {
1771
    babel_dump_entry(e);
1772
  }
1773
  FIB_WALK_END;
1774
}
1775

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

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

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

    
1799
  default:
1800
    return GA_UNKNOWN;
1801
  }
1802
}
1803

    
1804
void
1805
babel_show_interfaces(struct proto *P, char *iff)
1806
{
1807
  struct babel_proto *p = (void *) P;
1808
  struct babel_iface *ifa = NULL;
1809
  struct babel_neighbor *nbr = NULL;
1810

    
1811
  if (p->p.proto_state != PS_UP)
1812
  {
1813
    cli_msg(-1023, "%s: is not up", p->p.name);
1814
    cli_msg(0, "");
1815
    return;
1816
  }
1817

    
1818
  cli_msg(-1023, "%s:", p->p.name);
1819
  cli_msg(-1023, "%-10s %-6s %7s %6s %6s %-15s %s",
1820
          "Interface", "State", "RX cost", "Nbrs", "Timer",
1821
          "Next hop (v4)", "Next hop (v6)");
1822

    
1823
  WALK_LIST(ifa, p->interfaces)
1824
  {
1825
    if (iff && !patmatch(iff, ifa->iface->name))
1826
      continue;
1827

    
1828
    int nbrs = 0;
1829
    WALK_LIST(nbr, ifa->neigh_list)
1830
        nbrs++;
1831

    
1832
    int timer = MIN(ifa->next_regular, ifa->next_hello) - now;
1833
    cli_msg(-1023, "%-10s %-6s %7u %6u %6u %-15I %I",
1834
            ifa->iface->name, (ifa->up ? "Up" : "Down"),
1835
            ifa->cf->rxcost, nbrs, MAX(timer, 0),
1836
            ifa->next_hop_ip4, ifa->next_hop_ip6);
1837
  }
1838

    
1839
  cli_msg(0, "");
1840
}
1841

    
1842
void
1843
babel_show_neighbors(struct proto *P, char *iff)
1844
{
1845
  struct babel_proto *p = (void *) P;
1846
  struct babel_iface *ifa = NULL;
1847
  struct babel_neighbor *n = NULL;
1848
  struct babel_route *r = NULL;
1849

    
1850
  if (p->p.proto_state != PS_UP)
1851
  {
1852
    cli_msg(-1024, "%s: is not up", p->p.name);
1853
    cli_msg(0, "");
1854
    return;
1855
  }
1856

    
1857
  cli_msg(-1024, "%s:", p->p.name);
1858
  cli_msg(-1024, "%-25s %-10s %6s %6s %10s",
1859
          "IP address", "Interface", "Metric", "Routes", "Next hello");
1860

    
1861
  WALK_LIST(ifa, p->interfaces)
1862
  {
1863
    if (iff && !patmatch(iff, ifa->iface->name))
1864
      continue;
1865

    
1866
    WALK_LIST(n, ifa->neigh_list)
1867
    {
1868
      int rts = 0;
1869
      WALK_LIST(r, n->routes)
1870
        rts++;
1871

    
1872
      int timer = n->hello_expiry - now;
1873
      cli_msg(-1024, "%-25I %-10s %6u %6u %10u",
1874
              n->addr, ifa->iface->name, n->txcost, rts, MAX(timer, 0));
1875
    }
1876
  }
1877

    
1878
  cli_msg(0, "");
1879
}
1880

    
1881
static void
1882
babel_show_entries_(struct babel_proto *p, struct fib *rtable)
1883
{
1884
  struct babel_source *s = NULL;
1885
  struct babel_route *r = NULL;
1886

    
1887
  char ridbuf[ROUTER_ID_64_LENGTH+1];
1888

    
1889
  FIB_WALK(rtable, struct babel_entry, e)
1890
  {
1891
    r = e->selected_in ? e->selected_in : e->selected_out;
1892

    
1893
    int srcs = 0;
1894
    WALK_LIST(s, e->sources)
1895
      srcs++;
1896

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

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

    
1916
void
1917
babel_show_entries(struct proto *P)
1918
{
1919
  struct babel_proto *p = (void *) P;
1920

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

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

    
1932
  babel_show_entries_(p, &p->ip4_rtable);
1933
  babel_show_entries_(p, &p->ip6_rtable);
1934

    
1935
  cli_msg(0, "");
1936
}
1937

    
1938

    
1939
/*
1940
 *        Babel protocol glue
1941
 */
1942

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

    
1956
  babel_expire_routes(p);
1957
  babel_expire_seqno_requests(p);
1958
  babel_expire_neighbors(p);
1959
}
1960

    
1961
static inline void
1962
babel_kick_timer(struct babel_proto *p)
1963
{
1964
  if (p->timer->expires > (now + 1))
1965
    tm_start(p->timer, 1);
1966
}
1967

    
1968

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

    
1977
  l->next = next;
1978
  l->flags = EALF_SORTED;
1979
  l->count = 2;
1980

    
1981
  l->attrs[0].id = EA_BABEL_METRIC;
1982
  l->attrs[0].flags = 0;
1983
  l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
1984
  l->attrs[0].u.data = metric;
1985

    
1986
  l->attrs[1].id = EA_BABEL_ROUTER_ID;
1987
  l->attrs[1].flags = 0;
1988
  l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
1989
  l->attrs[1].u.ptr = rid;
1990

    
1991
  return l;
1992
}
1993

    
1994

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

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

    
2004
  return 0;
2005
}
2006

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

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

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

    
2031
  if (new)
2032
  {
2033
    /* Update */
2034
    e = babel_get_entry(p, net->n.addr);
2035

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

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

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

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

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

    
2104

    
2105
static struct proto *
2106
babel_init(struct proto_config *CF)
2107
{
2108
  struct proto *P = proto_new(CF);
2109
  struct babel_proto *p = (void *) P;
2110

    
2111
  proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4));
2112
  proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6));
2113

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

    
2122
  return P;
2123
}
2124

    
2125
static int
2126
babel_start(struct proto *P)
2127
{
2128
  struct babel_proto *p = (void *) P;
2129
  struct babel_config *cf = (void *) P->cf;
2130

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

    
2136
  init_list(&p->interfaces);
2137
  p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1);
2138
  tm_start(p->timer, 2);
2139
  p->update_seqno = 1;
2140
  p->router_id = proto_get_router_id(&cf->c);
2141

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

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

    
2150
  return PS_UP;
2151
}
2152

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

    
2163
static int
2164
babel_shutdown(struct proto *P)
2165
{
2166
  struct babel_proto *p = (void *) P;
2167
  struct babel_iface *ifa;
2168

    
2169
  TRACE(D_EVENTS, "Shutdown requested");
2170

    
2171
  WALK_LIST(ifa, p->interfaces)
2172
    babel_iface_shutdown(ifa);
2173

    
2174
  return PS_DOWN;
2175
}
2176

    
2177
static int
2178
babel_reconfigure(struct proto *P, struct proto_config *CF)
2179
{
2180
  struct babel_proto *p = (void *) P;
2181
  struct babel_config *new = (void *) CF;
2182

    
2183
  TRACE(D_EVENTS, "Reconfiguring");
2184

    
2185
  if (!proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4)) ||
2186
      !proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6)))
2187
    return 0;
2188

    
2189
  p->p.cf = CF;
2190
  babel_reconfigure_ifaces(p, new);
2191

    
2192
  babel_trigger_update(p);
2193
  babel_kick_timer(p);
2194

    
2195
  return 1;
2196
}
2197

    
2198

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