Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / proto / babel / babel.c @ 6b3f1a54

History | View | Annotate | Download (59.2 KB)

1
/*
2
 *        BIRD -- The Babel protocol
3
 *
4
 *        Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 *         (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *        (c) 2016--2017 CZ.NIC z.s.p.o.
7
 *
8
 *        Can be freely distributed and used under the terms of the GNU GPL.
9
 *
10
 *        This file contains the main routines for handling and sending TLVs, as
11
 *        well as timers and interaction with the nest.
12
 */
13

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

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

    
41

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

    
50
static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e);
51
static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod);
52
static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e);
53
static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n);
54
static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr);
55
static void babel_update_cost(struct babel_neighbor *n);
56
static inline void babel_kick_timer(struct babel_proto *p);
57
static inline void babel_iface_kick_timer(struct babel_iface *ifa);
58

    
59
static inline void babel_lock_neighbor(struct babel_neighbor *nbr)
60
{ if (nbr) nbr->uc++; }
61

    
62
static inline void babel_unlock_neighbor(struct babel_neighbor *nbr)
63
{ if (nbr && !--nbr->uc) mb_free(nbr); }
64

    
65

    
66
/*
67
 *        Functions to maintain data structures
68
 */
69

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

    
75
  e->updated = current_time();
76
  init_list(&e->requests);
77
  init_list(&e->sources);
78
  init_list(&e->routes);
79
}
80

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

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

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

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

    
105
  return NULL;
106
}
107

    
108
static struct babel_source *
109
babel_get_source(struct babel_proto *p, struct babel_entry *e, u64 router_id)
110
{
111
  struct babel_source *s = babel_find_source(e, router_id);
112

    
113
  if (s)
114
    return s;
115

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

    
123
  return s;
124
}
125

    
126
static void
127
babel_expire_sources(struct babel_proto *p, struct babel_entry *e)
128
{
129
  struct babel_source *n, *nx;
130
  btime now_ = current_time();
131

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

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

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

    
151
  return NULL;
152
}
153

    
154
static struct babel_route *
155
babel_get_route(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *nbr)
156
{
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

    
165
  r->e = e;
166
  r->neigh = nbr;
167
  add_tail(&e->routes, NODE r);
168
  add_tail(&nbr->routes, NODE &r->neigh_route);
169

    
170
  return r;
171
}
172

    
173
static inline void
174
babel_retract_route(struct babel_proto *p, struct babel_route *r)
175
{
176
  r->metric = r->advert_metric = BABEL_INFINITY;
177

    
178
  if (r == r->e->selected)
179
    babel_select_route(p, r->e, r);
180
}
181

    
182
static void
183
babel_flush_route(struct babel_proto *p, struct babel_route *r)
184
{
185
  DBG("Babel: Flush route %N router_id %lR neigh %I\n",
186
      r->e->n.addr, r->router_id, r->neigh->addr);
187

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

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

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

    
197
static void
198
babel_expire_route(struct babel_proto *p, struct babel_route *r)
199
{
200
  struct babel_config *cf = (void *) p->p.cf;
201

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

    
205
  if (r->metric < BABEL_INFINITY)
206
  {
207
    r->metric = r->advert_metric = BABEL_INFINITY;
208
    r->expires = current_time() + cf->hold_time;
209
  }
210
  else
211
  {
212
    babel_flush_route(p, r);
213
  }
214
}
215

    
216
static void
217
babel_refresh_route(struct babel_proto *p, struct babel_route *r)
218
{
219
  if (r == r->e->selected)
220
    babel_send_route_request(p, r->e, r->neigh);
221

    
222
  r->refresh_time = 0;
223
}
224

    
225
static void
226
babel_expire_routes_(struct babel_proto *p, struct fib *rtable)
227
{
228
  struct babel_config *cf = (void *) p->p.cf;
229
  struct babel_route *r, *rx;
230
  struct fib_iterator fit;
231
  btime now_ = current_time();
232

    
233
  FIB_ITERATE_INIT(&fit, rtable);
234

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

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

    
245
      if (r->expires && r->expires <= now_)
246
      {
247
        changed = changed || (r == e->selected);
248
        babel_expire_route(p, r);
249
      }
250
    }
251

    
252
    if (changed)
253
    {
254
      /*
255
       * We have to restart the iteration because there may be a cascade of
256
       * synchronous events babel_select_route() -> nest table change ->
257
       * babel_rt_notify() -> rtable change, invalidating hidden variables.
258
       */
259
      FIB_ITERATE_PUT(&fit);
260
      babel_select_route(p, e, NULL);
261
      goto loop;
262
    }
263

    
264
    /* Clean up stale entries */
265
    if ((e->valid == BABEL_ENTRY_STALE) && ((e->updated + cf->hold_time) <= now_))
266
      e->valid = BABEL_ENTRY_DUMMY;
267

    
268
    /* Clean up unreachable route */
269
    if (e->unreachable && (!e->valid || (e->router_id == p->router_id)))
270
    {
271
      FIB_ITERATE_PUT(&fit);
272
      babel_announce_retraction(p, e);
273
      goto loop;
274
    }
275

    
276
    babel_expire_sources(p, e);
277
    babel_expire_requests(p, e);
278

    
279
    /* Remove empty entries */
280
    if (!e->valid && EMPTY_LIST(e->routes) && EMPTY_LIST(e->sources) && EMPTY_LIST(e->requests))
281
    {
282
      FIB_ITERATE_PUT(&fit);
283
      fib_delete(rtable, e);
284
      goto loop;
285
    }
286
  }
287
  FIB_ITERATE_END;
288
}
289

    
290
static void
291
babel_expire_routes(struct babel_proto *p)
292
{
293
  babel_expire_routes_(p, &p->ip4_rtable);
294
  babel_expire_routes_(p, &p->ip6_rtable);
295
}
296

    
297
static inline int seqno_request_valid(struct babel_seqno_request *sr)
298
{ return !sr->nbr || sr->nbr->ifa; }
299

    
300
/*
301
 * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send
302
 * it to network. Do nothing if it is already in the table.
303
 */
304

    
305
static void
306
babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e,
307
                        u64 router_id, u16 seqno, u8 hop_count,
308
                        struct babel_neighbor *nbr)
309
{
310
  struct babel_seqno_request *sr;
311

    
312
  WALK_LIST(sr, e->requests)
313
    if (sr->router_id == router_id)
314
    {
315
      /* Found matching or newer */
316
      if (ge_mod64k(sr->seqno, seqno) && seqno_request_valid(sr))
317
        return;
318

    
319
      /* Found older */
320
      babel_unlock_neighbor(sr->nbr);
321
      rem_node(NODE sr);
322
      goto found;
323
    }
324

    
325
  /* No entries found */
326
  sr = sl_alloc(p->seqno_slab);
327

    
328
found:
329
  sr->router_id = router_id;
330
  sr->seqno = seqno;
331
  sr->hop_count = hop_count;
332
  sr->count = 0;
333
  sr->expires = current_time() + BABEL_SEQNO_REQUEST_EXPIRY;
334
  babel_lock_neighbor(sr->nbr = nbr);
335
  add_tail(&e->requests, NODE sr);
336

    
337
  babel_send_seqno_request(p, e, sr);
338
}
339

    
340
static void
341
babel_remove_seqno_request(struct babel_proto *p, struct babel_seqno_request *sr)
342
{
343
  babel_unlock_neighbor(sr->nbr);
344
  rem_node(NODE sr);
345
  sl_free(p->seqno_slab, sr);
346
}
347

    
348
static int
349
babel_satisfy_seqno_request(struct babel_proto *p, struct babel_entry *e,
350
                           u64 router_id, u16 seqno)
351
{
352
  struct babel_seqno_request *sr;
353

    
354
  WALK_LIST(sr, e->requests)
355
    if ((sr->router_id == router_id) && ge_mod64k(seqno, sr->seqno))
356
    {
357
      /* Found the request, remove it */
358
      babel_remove_seqno_request(p, sr);
359
      return 1;
360
    }
361

    
362
  return 0;
363
}
364

    
365
static void
366
babel_expire_requests(struct babel_proto *p, struct babel_entry *e)
367
{
368
  struct babel_seqno_request *sr, *srx;
369
  btime now_ = current_time();
370

    
371
  WALK_LIST_DELSAFE(sr, srx, e->requests)
372
  {
373
    /* Remove seqno requests sent to dead neighbors */
374
    if (!seqno_request_valid(sr))
375
    {
376
      babel_remove_seqno_request(p, sr);
377
      continue;
378
    }
379

    
380
    /* Handle expired requests - resend or remove */
381
    if (sr->expires && sr->expires <= now_)
382
    {
383
      if (sr->count < BABEL_SEQNO_REQUEST_RETRY)
384
      {
385
        sr->count++;
386
        sr->expires += (BABEL_SEQNO_REQUEST_EXPIRY << sr->count);
387
        babel_send_seqno_request(p, e, sr);
388
      }
389
      else
390
      {
391
        TRACE(D_EVENTS, "Seqno request for %N router-id %lR expired",
392
              e->n.addr, sr->router_id);
393

    
394
        babel_remove_seqno_request(p, sr);
395
        continue;
396
      }
397
    }
398
  }
399
}
400

    
401
static struct babel_neighbor *
402
babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
403
{
404
  struct babel_neighbor *nbr;
405

    
406
  WALK_LIST(nbr, ifa->neigh_list)
407
    if (ipa_equal(nbr->addr, addr))
408
      return nbr;
409

    
410
  return NULL;
411
}
412

    
413
static struct babel_neighbor *
414
babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
415
{
416
  struct babel_proto *p = ifa->proto;
417
  struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);
418

    
419
  if (nbr)
420
    return nbr;
421

    
422
  TRACE(D_EVENTS, "New neighbor %I on %s", addr, ifa->iface->name);
423

    
424
  nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
425
  nbr->ifa = ifa;
426
  nbr->addr = addr;
427
  nbr->rxcost = BABEL_INFINITY;
428
  nbr->txcost = BABEL_INFINITY;
429
  nbr->cost = BABEL_INFINITY;
430
  init_list(&nbr->routes);
431
  babel_lock_neighbor(nbr);
432
  add_tail(&ifa->neigh_list, NODE nbr);
433

    
434
  return nbr;
435
}
436

    
437
static void
438
babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr)
439
{
440
  struct babel_route *r;
441
  node *n;
442

    
443
  TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name);
444

    
445
  WALK_LIST_FIRST(n, nbr->routes)
446
  {
447
    r = SKIP_BACK(struct babel_route, neigh_route, n);
448
    babel_retract_route(p, r);
449
    babel_flush_route(p, r);
450
  }
451

    
452
  nbr->ifa = NULL;
453
  rem_node(NODE nbr);
454
  babel_unlock_neighbor(nbr);
455
}
456

    
457
static void
458
babel_expire_ihu(struct babel_proto *p, struct babel_neighbor *nbr)
459
{
460
  TRACE(D_EVENTS, "IHU from nbr %I on %s expired", nbr->addr, nbr->ifa->iface->name);
461

    
462
  nbr->txcost = BABEL_INFINITY;
463
  nbr->ihu_expiry = 0;
464
  babel_update_cost(nbr);
465
}
466

    
467
static void
468
babel_expire_hello(struct babel_proto *p, struct babel_neighbor *nbr, btime now_)
469
{
470
again:
471
  nbr->hello_map <<= 1;
472

    
473
  if (nbr->hello_cnt < 16)
474
    nbr->hello_cnt++;
475

    
476
  nbr->hello_expiry += nbr->last_hello_int;
477

    
478
  /* We may expire multiple hellos if last_hello_int is too short */
479
  if (nbr->hello_map && nbr->hello_expiry <= now_)
480
    goto again;
481

    
482
  TRACE(D_EVENTS, "Hello from nbr %I on %s expired, %d left",
483
        nbr->addr, nbr->ifa->iface->name, u32_popcount(nbr->hello_map));
484

    
485
  if (nbr->hello_map)
486
    babel_update_cost(nbr);
487
  else
488
    babel_flush_neighbor(p, nbr);
489
}
490

    
491
static void
492
babel_expire_neighbors(struct babel_proto *p)
493
{
494
  struct babel_iface *ifa;
495
  struct babel_neighbor *nbr, *nbx;
496
  btime now_ = current_time();
497

    
498
  WALK_LIST(ifa, p->interfaces)
499
  {
500
    WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
501
    {
502
      if (nbr->ihu_expiry && nbr->ihu_expiry <= now_)
503
        babel_expire_ihu(p, nbr);
504

    
505
      if (nbr->hello_expiry && nbr->hello_expiry <= now_)
506
        babel_expire_hello(p, nbr, now_);
507
    }
508
  }
509
}
510

    
511

    
512
/*
513
 *        Best route selection
514
 */
515

    
516
/*
517
 * From the RFC (section 3.5.1):
518
 *
519
 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
520
 * metric) is feasible if one of the following conditions holds:
521
 *
522
 * - metric is infinite; or
523
 *
524
 * - no entry exists in the source table indexed by (id, prefix, plen); or
525
 *
526
 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
527
 *   table, and either
528
 *   - seqno' < seqno or
529
 *   - seqno = seqno' and metric < metric'.
530
 */
531
static inline int
532
babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
533
{
534
  return !s ||
535
    (metric == BABEL_INFINITY) ||
536
    (seqno > s->seqno) ||
537
    ((seqno == s->seqno) && (metric < s->metric));
538
}
539

    
540
/* Simple additive metric - Appendix 3.1 in the RFC */
541
static inline u16
542
babel_compute_metric(struct babel_neighbor *n, uint metric)
543
{
544
  return MIN(metric + n->cost, BABEL_INFINITY);
545
}
546

    
547
static void
548
babel_update_cost(struct babel_neighbor *nbr)
549
{
550
  struct babel_proto *p = nbr->ifa->proto;
551
  struct babel_iface_config *cf = nbr->ifa->cf;
552
  uint rcv = u32_popcount(nbr->hello_map); // number of bits set
553
  uint max = nbr->hello_cnt;
554
  uint rxcost = BABEL_INFINITY;        /* Cost to announce in IHU */
555
  uint txcost = BABEL_INFINITY;        /* Effective cost for route selection */
556

    
557
  if (!rcv || !nbr->ifa->up)
558
    goto done;
559

    
560
  switch (cf->type)
561
  {
562
  case BABEL_IFACE_TYPE_WIRED:
563
    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
564

    
565
    /* Link is bad if less than cf->limit/16 of expected hellos were received */
566
    if (rcv * 16 < cf->limit * max)
567
      break;
568

    
569
    rxcost =  cf->rxcost;
570
    txcost = nbr->txcost;
571
    break;
572

    
573
  case BABEL_IFACE_TYPE_WIRELESS:
574
    /*
575
     * ETX - Appendix 2.2 in the RFC.
576
     *
577
     * alpha  = prob. of successful transmission estimated by the neighbor
578
     * beta   = prob. of successful transmission estimated by the router
579
     * rxcost = nominal rxcost of the router / beta
580
     * txcost = nominal rxcost of the neighbor / (alpha * beta)
581
     *        = received txcost / beta
582
     *
583
     * Note that received txcost is just neighbor's rxcost. Beta is rcv/max,
584
     * we use inverse values of beta (i.e. max/rcv) to stay in integers.
585
     */
586
    rxcost = MIN( cf->rxcost * max / rcv, BABEL_INFINITY);
587
    txcost = MIN(nbr->txcost * max / rcv, BABEL_INFINITY);
588
    break;
589
  }
590

    
591
done:
592
  /* If RX cost changed, send IHU with next Hello */
593
  if (rxcost != nbr->rxcost)
594
  {
595
    nbr->rxcost = rxcost;
596
    nbr->ihu_cnt = 0;
597
  }
598

    
599
  /* If link cost changed, run route selection */
600
  if (txcost != nbr->cost)
601
  {
602
    TRACE(D_EVENTS, "Cost of nbr %I on %s changed from %u to %u",
603
          nbr->addr, nbr->ifa->iface->name, nbr->cost, txcost);
604

    
605
    nbr->cost = txcost;
606

    
607
    struct babel_route *r; node *n;
608
    WALK_LIST2(r, n, nbr->routes, neigh_route)
609
    {
610
      r->metric = babel_compute_metric(nbr, r->advert_metric);
611
      babel_select_route(p, r->e, r);
612
    }
613
  }
614
}
615

    
616
/**
617
 * babel_announce_rte - announce selected route to the core
618
 * @p: Babel protocol instance
619
 * @e: Babel route entry to announce
620
 *
621
 * This function announces a Babel entry to the core if it has a selected
622
 * incoming path, and retracts it otherwise. If there is no selected route but
623
 * the entry is valid and ours, the unreachable route is announced instead.
624
 */
625
static void
626
babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
627
{
628
  struct babel_route *r = e->selected;
629
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
630

    
631
  if (r)
632
  {
633
    rta a0 = {
634
      .src = p->p.main_source,
635
      .source = RTS_BABEL,
636
      .scope = SCOPE_UNIVERSE,
637
      .dest = RTD_UNICAST,
638
      .from = r->neigh->addr,
639
      .nh.gw = r->next_hop,
640
      .nh.iface = r->neigh->ifa->iface,
641
    };
642

    
643
    rta *a = rta_lookup(&a0);
644
    rte *rte = rte_get_temp(a);
645
    rte->u.babel.seqno = r->seqno;
646
    rte->u.babel.metric = r->metric;
647
    rte->u.babel.router_id = r->router_id;
648
    rte->pflags = 0;
649

    
650
    e->unreachable = 0;
651
    rte_update2(c, e->n.addr, rte, p->p.main_source);
652
  }
653
  else if (e->valid && (e->router_id != p->router_id))
654
  {
655
    /* Unreachable */
656
    rta a0 = {
657
      .src = p->p.main_source,
658
      .source = RTS_BABEL,
659
      .scope = SCOPE_UNIVERSE,
660
      .dest = RTD_UNREACHABLE,
661
    };
662

    
663
    rta *a = rta_lookup(&a0);
664
    rte *rte = rte_get_temp(a);
665
    memset(&rte->u.babel, 0, sizeof(rte->u.babel));
666
    rte->pflags = 0;
667
    rte->pref = 1;
668

    
669
    e->unreachable = 1;
670
    rte_update2(c, e->n.addr, rte, p->p.main_source);
671
  }
672
  else
673
  {
674
    /* Retraction */
675
    e->unreachable = 0;
676
    rte_update2(c, e->n.addr, NULL, p->p.main_source);
677
  }
678
}
679

    
680
/* Special case of babel_announce_rte() just for retraction */
681
static inline void
682
babel_announce_retraction(struct babel_proto *p, struct babel_entry *e)
683
{
684
  struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
685
  e->unreachable = 0;
686
  rte_update2(c, e->n.addr, NULL, p->p.main_source);
687
}
688

    
689

    
690
/**
691
 * babel_select_route - select best route for given route entry
692
 * @p: Babel protocol instance
693
 * @e: Babel entry to select the best route for
694
 * @mod: Babel route that was modified or NULL if unspecified
695
 *
696
 * Select the best reachable and feasible route for a given prefix among the
697
 * routes received from peers, and propagate it to the nest. This just selects
698
 * the reachable and feasible route with the lowest metric, but keeps selected
699
 * the old one in case of tie.
700
 *
701
 * If no feasible route is available for a prefix that previously had a route
702
 * selected, a seqno request is sent to try to get a valid route. If the entry
703
 * is valid and not owned by us, the unreachable route is announced to the nest
704
 * (to blackhole packets going to it, as per section 2.8). It is later removed
705
 * by babel_expire_routes(). Otherwise, the route is just removed from the nest.
706
 *
707
 * Argument @mod is used to optimize best route calculation. When specified, the
708
 * function can assume that only the @mod route was modified to avoid full best
709
 * route selection and announcement when non-best route was modified in minor
710
 * way. The caller is advised to not call babel_select_route() when no change is
711
 * done (e.g. periodic route updates) to avoid unnecessary announcements of the
712
 * same best route. The caller is not required to call the function in case of a
713
 * retraction of a non-best route.
714
 *
715
 * Note that the function does not active triggered updates. That is done by
716
 * babel_rt_notify() when the change is propagated back to Babel.
717
 */
718
static void
719
babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod)
720
{
721
  struct babel_route *r, *best = e->selected;
722

    
723
  /* Shortcut if only non-best was modified */
724
  if (mod && (mod != best))
725
  {
726
    /* Either select modified route, or keep old best route */
727
    if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible)
728
      best = mod;
729
    else
730
      return;
731
  }
732
  else
733
  {
734
    /* Selected route may be modified and no longer admissible */
735
    if (!best || (best->metric == BABEL_INFINITY) || !best->feasible)
736
      best = NULL;
737

    
738
    /* Find the best feasible route from all routes */
739
    WALK_LIST(r, e->routes)
740
      if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible)
741
        best = r;
742
  }
743

    
744
  if (best)
745
  {
746
    if (best != e->selected)
747
      TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d",
748
            e->n.addr, best->router_id, best->metric);
749
  }
750
  else if (e->selected)
751
  {
752
    /*
753
     * We have lost all feasible routes. We have to broadcast seqno request
754
     * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8).
755
     * The later is done automatically by babel_announce_rte().
756
     */
757

    
758
    TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr);
759
    if (e->valid && (e->selected->router_id == e->router_id))
760
      babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL);
761
  }
762
  else
763
    return;
764

    
765
  e->selected = best;
766
  babel_announce_rte(p, e);
767
}
768

    
769
/*
770
 *        Functions to send replies
771
 */
772

    
773
static void
774
babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
775
{
776
  struct babel_proto *p = ifa->proto;
777
  union babel_msg msg = {};
778

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

    
781
  msg.type = BABEL_TLV_ACK;
782
  msg.ack.nonce = nonce;
783

    
784
  babel_send_unicast(&msg, ifa, dest);
785
}
786

    
787
static void
788
babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
789
{
790
  struct babel_proto *p = ifa->proto;
791

    
792
  msg->type = BABEL_TLV_IHU;
793
  msg->ihu.addr = n->addr;
794
  msg->ihu.rxcost = n->rxcost;
795
  msg->ihu.interval = ifa->cf->ihu_interval;
796

    
797
  TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %t",
798
        msg->ihu.addr, msg->ihu.rxcost, (btime) msg->ihu.interval);
799
}
800

    
801
static void
802
babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
803
{
804
  union babel_msg msg = {};
805
  babel_build_ihu(&msg, ifa, n);
806
  babel_send_unicast(&msg, ifa, n->addr);
807
  n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
808
}
809

    
810
static void
811
babel_send_ihus(struct babel_iface *ifa)
812
{
813
  struct babel_neighbor *n;
814
  WALK_LIST(n, ifa->neigh_list)
815
  {
816
    if (n->hello_cnt && (--n->ihu_cnt <= 0))
817
    {
818
      union babel_msg msg = {};
819
      babel_build_ihu(&msg, ifa, n);
820
      babel_enqueue(&msg, ifa);
821
      n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
822
    }
823
  }
824
}
825

    
826
static void
827
babel_send_hello(struct babel_iface *ifa)
828
{
829
  struct babel_proto *p = ifa->proto;
830
  union babel_msg msg = {};
831

    
832
  msg.type = BABEL_TLV_HELLO;
833
  msg.hello.seqno = ifa->hello_seqno++;
834
  msg.hello.interval = ifa->cf->hello_interval;
835

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

    
839
  babel_enqueue(&msg, ifa);
840

    
841
  babel_send_ihus(ifa);
842
}
843

    
844
static void
845
babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n)
846
{
847
  union babel_msg msg = {};
848

    
849
  TRACE(D_PACKETS, "Sending route request for %N to %I",
850
        e->n.addr, n->addr);
851

    
852
  msg.type = BABEL_TLV_ROUTE_REQUEST;
853
  net_copy(&msg.route_request.net, e->n.addr);
854

    
855
  babel_send_unicast(&msg, n->ifa, n->addr);
856
}
857

    
858
static void
859
babel_send_wildcard_request(struct babel_iface *ifa)
860
{
861
  struct babel_proto *p = ifa->proto;
862
  union babel_msg msg = {};
863

    
864
  TRACE(D_PACKETS, "Sending wildcard route request on %s",
865
        ifa->ifname);
866

    
867
  msg.type = BABEL_TLV_ROUTE_REQUEST;
868
  msg.route_request.full = 1;
869

    
870
  babel_enqueue(&msg, ifa);
871
}
872

    
873
static void
874
babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr)
875
{
876
  union babel_msg msg = {};
877

    
878
  msg.type = BABEL_TLV_SEQNO_REQUEST;
879
  msg.seqno_request.hop_count = sr->hop_count ?: BABEL_INITIAL_HOP_COUNT;
880
  msg.seqno_request.seqno = sr->seqno;
881
  msg.seqno_request.router_id = sr->router_id;
882
  net_copy(&msg.seqno_request.net, e->n.addr);
883

    
884
  if (sr->nbr)
885
  {
886
    TRACE(D_PACKETS, "Sending seqno request for %N router-id %lR seqno %d to %I on %s",
887
          e->n.addr, sr->router_id, sr->seqno, sr->nbr->addr, sr->nbr->ifa->ifname);
888

    
889
    babel_send_unicast(&msg, sr->nbr->ifa, sr->nbr->addr);
890
  }
891
  else
892
  {
893
    TRACE(D_PACKETS, "Sending broadcast seqno request for %N router-id %lR seqno %d",
894
          e->n.addr, sr->router_id, sr->seqno);
895

    
896
    struct babel_iface *ifa;
897
    WALK_LIST(ifa, p->interfaces)
898
      babel_enqueue(&msg, ifa);
899
  }
900
}
901

    
902
/**
903
 * babel_send_update - send route table updates
904
 * @ifa: Interface to transmit on
905
 * @changed: Only send entries changed since this time
906
 *
907
 * This function produces update TLVs for all entries changed since the time
908
 * indicated by the &changed parameter and queues them for transmission on the
909
 * selected interface. During the process, the feasibility distance for each
910
 * transmitted entry is updated.
911
 */
912
static void
913
babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable)
914
{
915
  struct babel_proto *p = ifa->proto;
916

    
917
  /* Update increase was requested */
918
  if (p->update_seqno_inc)
919
  {
920
    p->update_seqno++;
921
    p->update_seqno_inc = 0;
922
  }
923

    
924
  FIB_WALK(rtable, struct babel_entry, e)
925
  {
926
    if (!e->valid)
927
      continue;
928

    
929
    /* Our own seqno might have changed, in which case we update the routes we
930
       originate. */
931
    if ((e->router_id == p->router_id) && (e->seqno < p->update_seqno))
932
    {
933
      e->seqno = p->update_seqno;
934
      e->updated = current_time();
935
    }
936

    
937
    /* Skip routes that weren't updated since 'changed' time */
938
    if (e->updated < changed)
939
      continue;
940

    
941
    TRACE(D_PACKETS, "Sending update for %N router-id %lR seqno %d metric %d",
942
          e->n.addr, e->router_id, e->seqno, e->metric);
943

    
944
    union babel_msg msg = {};
945
    msg.type = BABEL_TLV_UPDATE;
946
    msg.update.interval = ifa->cf->update_interval;
947
    msg.update.seqno = e->seqno;
948
    msg.update.metric = e->metric;
949
    msg.update.router_id = e->router_id;
950
    net_copy(&msg.update.net, e->n.addr);
951

    
952
    msg.update.next_hop = ((e->n.addr->type == NET_IP4) ?
953
                           ifa->next_hop_ip4 : ifa->next_hop_ip6);
954

    
955
    babel_enqueue(&msg, ifa);
956

    
957
    /* Update feasibility distance for redistributed routes */
958
    if (e->router_id != p->router_id)
959
    {
960
      struct babel_source *s = babel_get_source(p, e, e->router_id);
961
      s->expires = current_time() + BABEL_GARBAGE_INTERVAL;
962

    
963
      if ((msg.update.seqno > s->seqno) ||
964
          ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
965
      {
966
        s->seqno = msg.update.seqno;
967
        s->metric = msg.update.metric;
968
      }
969
    }
970
  }
971
  FIB_WALK_END;
972
}
973

    
974
static void
975
babel_send_update(struct babel_iface *ifa, btime changed)
976
{
977
  struct babel_proto *p = ifa->proto;
978

    
979
  babel_send_update_(ifa, changed, &p->ip4_rtable);
980
  babel_send_update_(ifa, changed, &p->ip6_rtable);
981
}
982

    
983
static void
984
babel_trigger_iface_update(struct babel_iface *ifa)
985
{
986
  struct babel_proto *p = ifa->proto;
987

    
988
  /* Interface not active or already scheduled */
989
  if (!ifa->up || ifa->want_triggered)
990
    return;
991

    
992
  TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
993
        ifa->iface->name, p->update_seqno);
994

    
995
  ifa->want_triggered = current_time();
996
  babel_iface_kick_timer(ifa);
997
}
998

    
999
/* Sends and update on all interfaces. */
1000
static void
1001
babel_trigger_update(struct babel_proto *p)
1002
{
1003
  if (p->triggered)
1004
    return;
1005

    
1006
  struct babel_iface *ifa;
1007
  WALK_LIST(ifa, p->interfaces)
1008
    babel_trigger_iface_update(ifa);
1009

    
1010
  p->triggered = 1;
1011
}
1012

    
1013
/* A retraction is an update with an infinite metric */
1014
static void
1015
babel_send_retraction(struct babel_iface *ifa, net_addr *n)
1016
{
1017
  struct babel_proto *p = ifa->proto;
1018
  union babel_msg msg = {};
1019

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

    
1022
  msg.type = BABEL_TLV_UPDATE;
1023
  msg.update.interval = ifa->cf->update_interval;
1024
  msg.update.seqno = p->update_seqno;
1025
  msg.update.metric = BABEL_INFINITY;
1026
  msg.update.net = *n;
1027

    
1028
  babel_enqueue(&msg, ifa);
1029
}
1030

    
1031
static void
1032
babel_send_wildcard_retraction(struct babel_iface *ifa)
1033
{
1034
  struct babel_proto *p = ifa->proto;
1035
  union babel_msg msg = {};
1036

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

    
1039
  msg.type = BABEL_TLV_UPDATE;
1040
  msg.update.wildcard = 1;
1041
  msg.update.interval = ifa->cf->update_interval;
1042
  msg.update.seqno = p->update_seqno;
1043
  msg.update.metric = BABEL_INFINITY;
1044

    
1045
  babel_enqueue(&msg, ifa);
1046
}
1047

    
1048

    
1049
/*
1050
 *        TLV handler helpers
1051
 */
1052

    
1053
/* Update hello history according to Appendix A1 of the RFC */
1054
static void
1055
babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
1056
{
1057
  /*
1058
   * Compute the difference between expected and received seqno (modulo 2^16).
1059
   * If the expected and received seqnos are within 16 of each other, the modular
1060
   * difference is going to be less than 16 for one of the directions. Otherwise,
1061
   * the values differ too much, so just reset the state.
1062
   */
1063

    
1064
  u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
1065

    
1066
  if ((delta == 0) || (n->hello_cnt == 0))
1067
  {
1068
    /* Do nothing */
1069
  }
1070
  else if (delta <= 16)
1071
  {
1072
    /* Sending node decreased interval; fast-forward */
1073
    n->hello_map <<= delta;
1074
    n->hello_cnt = MIN(n->hello_cnt + delta, 16);
1075
  }
1076
  else if (delta >= 0xfff0)
1077
  {
1078
    u8 diff = (0xffff - delta);
1079
    /* Sending node increased interval; undo history */
1080
    n->hello_map >>= diff;
1081
    n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
1082
  }
1083
  else
1084
  {
1085
    /* Note state reset - flush entries */
1086
    n->hello_map = n->hello_cnt = 0;
1087
  }
1088

    
1089
  /* Current entry */
1090
  n->hello_map = (n->hello_map << 1) | 1;
1091
  n->next_hello_seqno = seqno+1;
1092
  if (n->hello_cnt < 16) n->hello_cnt++;
1093

    
1094
  /* Update expiration */
1095
  n->hello_expiry = current_time() + BABEL_HELLO_EXPIRY_FACTOR(interval);
1096
  n->last_hello_int = interval;
1097
}
1098

    
1099

    
1100
/*
1101
 *        TLV handlers
1102
 */
1103

    
1104
void
1105
babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
1106
{
1107
  struct babel_proto *p = ifa->proto;
1108
  struct babel_msg_ack_req *msg = &m->ack_req;
1109

    
1110
  TRACE(D_PACKETS, "Handling ACK request nonce %d interval %t",
1111
        msg->nonce, (btime) msg->interval);
1112

    
1113
  babel_send_ack(ifa, msg->sender, msg->nonce);
1114
}
1115

    
1116
void
1117
babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
1118
{
1119
  struct babel_proto *p = ifa->proto;
1120
  struct babel_msg_hello *msg = &m->hello;
1121

    
1122
  TRACE(D_PACKETS, "Handling hello seqno %d interval %t",
1123
        msg->seqno, (btime) msg->interval);
1124

    
1125
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1126
  int first_hello = !n->hello_cnt;
1127

    
1128
  babel_update_hello_history(n, msg->seqno, msg->interval);
1129
  babel_update_cost(n);
1130

    
1131
  /* Speed up session establishment by sending IHU immediately */
1132
  if (first_hello)
1133
    babel_send_ihu(ifa, n);
1134
}
1135

    
1136
void
1137
babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
1138
{
1139
  struct babel_proto *p = ifa->proto;
1140
  struct babel_msg_ihu *msg = &m->ihu;
1141

    
1142
  /* Ignore IHUs that are not about us */
1143
  if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
1144
    return;
1145

    
1146
  TRACE(D_PACKETS, "Handling IHU rxcost %d interval %t",
1147
        msg->rxcost, (btime) msg->interval);
1148

    
1149
  struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
1150
  n->txcost = msg->rxcost;
1151
  n->ihu_expiry = current_time() + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
1152
  babel_update_cost(n);
1153
}
1154

    
1155
/**
1156
 * babel_handle_update - handle incoming route updates
1157
 * @m: Incoming update TLV
1158
 * @ifa: Interface the update was received on
1159
 *
1160
 * This function is called as a handler for update TLVs and handles the updating
1161
 * and maintenance of route entries in Babel's internal routing cache. The
1162
 * handling follows the actions described in the Babel RFC, and at the end of
1163
 * each update handling, babel_select_route() is called on the affected entry to
1164
 * optionally update the selected routes and propagate them to the core.
1165
 */
1166
void
1167
babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
1168
{
1169
  struct babel_proto *p = ifa->proto;
1170
  struct babel_msg_update *msg = &m->update;
1171

    
1172
  struct babel_neighbor *nbr;
1173
  struct babel_entry *e;
1174
  struct babel_source *s;
1175
  struct babel_route *r, *best;
1176
  node *n;
1177
  int feasible, metric;
1178

    
1179
  if (msg->wildcard)
1180
    TRACE(D_PACKETS, "Handling wildcard retraction", msg->seqno);
1181
  else
1182
    TRACE(D_PACKETS, "Handling update for %N with seqno %d metric %d",
1183
          &msg->net, msg->seqno, msg->metric);
1184

    
1185
  nbr = babel_find_neighbor(ifa, msg->sender);
1186
  if (!nbr)
1187
  {
1188
    DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
1189
    return;
1190
  }
1191

    
1192
  if (msg->router_id == p->router_id)
1193
  {
1194
    DBG("Babel: Ignoring update for our own router ID.\n");
1195
    return;
1196
  }
1197

    
1198
  struct channel *c = (msg->net.type == NET_IP4) ? p->ip4_channel : p->ip6_channel;
1199
  if (!c || (c->channel_state != CS_UP))
1200
  {
1201
    DBG("Babel: Ignoring update for inactive address family.\n");
1202
    return;
1203
  }
1204

    
1205
  /* Retraction */
1206
  if (msg->metric == BABEL_INFINITY)
1207
  {
1208
    if (msg->wildcard)
1209
    {
1210
      /*
1211
       * Special case: This is a retraction of all prefixes announced by this
1212
       * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
1213
       */
1214
      WALK_LIST(n, nbr->routes)
1215
      {
1216
        r = SKIP_BACK(struct babel_route, neigh_route, n);
1217
        babel_retract_route(p, r);
1218
      }
1219
    }
1220
    else
1221
    {
1222
      e = babel_find_entry(p, &msg->net);
1223

    
1224
      if (!e)
1225
        return;
1226

    
1227
      /* The route entry indexed by neighbour */
1228
      r = babel_find_route(e, nbr);
1229

    
1230
      if (!r)
1231
        return;
1232

    
1233
      /* Router-id, next-hop and seqno are ignored for retractions */
1234
      babel_retract_route(p, r);
1235
    }
1236

    
1237
    /* Done with retractions */
1238
    return;
1239
  }
1240

    
1241
  /* Regular update */
1242
  e = babel_get_entry(p, &msg->net);
1243
  r = babel_get_route(p, e, nbr); /* the route entry indexed by neighbour */
1244
  s = babel_find_source(e, msg->router_id); /* for feasibility */
1245
  feasible = babel_is_feasible(s, msg->seqno, msg->metric);
1246
  metric = babel_compute_metric(nbr, msg->metric);
1247
  best = e->selected;
1248

    
1249
  /* RFC section 3.8.2.2 - Dealing with unfeasible updates */
1250
  if (!feasible && (metric != BABEL_INFINITY) &&
1251
      (!best || (r == best) || (metric < best->metric)))
1252
    babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr);
1253

    
1254
  /* Special case - ignore unfeasible update to best route */
1255
  if (r == best && !feasible && (msg->router_id == r->router_id))
1256
    return;
1257

    
1258
  r->expires = current_time() + BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
1259
  r->refresh_time = current_time() + BABEL_ROUTE_REFRESH_FACTOR(msg->interval);
1260

    
1261
  /* No further processing if there is no change */
1262
  if ((r->feasible == feasible) && (r->seqno == msg->seqno) &&
1263
      (r->metric == metric) && (r->advert_metric == msg->metric) &&
1264
      (r->router_id == msg->router_id) && ipa_equal(r->next_hop, msg->next_hop))
1265
    return;
1266

    
1267
  /* Last paragraph above - update the entry */
1268
  r->feasible = feasible;
1269
  r->seqno = msg->seqno;
1270
  r->metric = metric;
1271
  r->advert_metric = msg->metric;
1272
  r->router_id = msg->router_id;
1273
  r->next_hop = msg->next_hop;
1274

    
1275
  /* If received update satisfies seqno request, we send triggered updates */
1276
  if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno))
1277
  {
1278
    babel_trigger_update(p);
1279
    e->updated = current_time();
1280
  }
1281

    
1282
  babel_select_route(p, e, r);
1283
}
1284

    
1285
void
1286
babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
1287
{
1288
  struct babel_proto *p = ifa->proto;
1289
  struct babel_msg_route_request *msg = &m->route_request;
1290

    
1291
  /* RFC 6126 3.8.1.1 */
1292

    
1293
  /* Wildcard request - full update on the interface */
1294
  if (msg->full)
1295
  {
1296
    TRACE(D_PACKETS, "Handling wildcard route request");
1297
    ifa->want_triggered = 1;
1298
    return;
1299
  }
1300

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

    
1303
  /* Non-wildcard request - see if we have an entry for the route.
1304
     If not, send a retraction, otherwise send an update. */
1305
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1306
  if (!e)
1307
  {
1308
    babel_send_retraction(ifa, &msg->net);
1309
  }
1310
  else
1311
  {
1312
    babel_trigger_iface_update(ifa);
1313
    e->updated = current_time();
1314
  }
1315
}
1316

    
1317
void
1318
babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
1319
{
1320
  struct babel_proto *p = ifa->proto;
1321
  struct babel_msg_seqno_request *msg = &m->seqno_request;
1322

    
1323
  /* RFC 6126 3.8.1.2 */
1324

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

    
1328
  /* Ignore if we have no such entry or entry has infinite metric */
1329
  struct babel_entry *e = babel_find_entry(p, &msg->net);
1330
  if (!e || !e->valid || (e->metric == BABEL_INFINITY))
1331
    return;
1332

    
1333
  /* Trigger update on incoming interface if we have a selected route with
1334
     different router id or seqno no smaller than requested */
1335
  if ((e->router_id != msg->router_id) || ge_mod64k(e->seqno, msg->seqno))
1336
  {
1337
    babel_trigger_iface_update(ifa);
1338
    e->updated = current_time();
1339
    return;
1340
  }
1341

    
1342
  /* Seqno is larger; check if we own the router id */
1343
  if (msg->router_id == p->router_id)
1344
  {
1345
    /* Ours; seqno increase and trigger global update */
1346
    p->update_seqno_inc = 1;
1347
    babel_trigger_update(p);
1348
  }
1349
  else if (msg->hop_count > 1)
1350
  {
1351
    /* Not ours; forward if TTL allows it */
1352

    
1353
    /* Find best admissible route */
1354
    struct babel_route *r, *best1 = NULL, *best2 = NULL;
1355
    WALK_LIST(r, e->routes)
1356
      if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender))
1357
      {
1358
        /* Find best feasible route */
1359
        if ((!best1 || r->metric < best1->metric) && r->feasible)
1360
          best1 = r;
1361

    
1362
        /* Find best not necessary feasible route */
1363
        if (!best2 || r->metric < best2->metric)
1364
          best2 = r;
1365
      }
1366

    
1367
    /* If no route is found, do nothing */
1368
    r = best1 ?: best2;
1369
    if (!r)
1370
      return;
1371

    
1372
    babel_add_seqno_request(p, e, msg->router_id, msg->seqno, msg->hop_count-1, r->neigh);
1373
  }
1374
}
1375

    
1376

    
1377
/*
1378
 *        Babel interfaces
1379
 */
1380

    
1381
/**
1382
 * babel_iface_timer - Babel interface timer handler
1383
 * @t: Timer
1384
 *
1385
 * This function is called by the per-interface timer and triggers sending of
1386
 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1387
 * and updates are simply handled by setting the next_{hello,regular} variables
1388
 * on the interface, and triggering an update (and resetting the variable)
1389
 * whenever 'now' exceeds that value.
1390
 *
1391
 * For triggered updates, babel_trigger_iface_update() will set the
1392
 * want_triggered field on the interface to a timestamp value. If this is set
1393
 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1394
 * babel_send_update() will be called with this timestamp as the second
1395
 * parameter. This causes updates to be send consisting of only the routes that
1396
 * have changed since the time saved in want_triggered.
1397
 *
1398
 * Mostly when an update is triggered, the route being modified will be set to
1399
 * the value of 'now' at the time of the trigger; the >= comparison for
1400
 * selecting which routes to send in the update will make sure this is included.
1401
 */
1402
static void
1403
babel_iface_timer(timer *t)
1404
{
1405
  struct babel_iface *ifa = t->data;
1406
  struct babel_proto *p = ifa->proto;
1407
  btime hello_period = ifa->cf->hello_interval;
1408
  btime update_period = ifa->cf->update_interval;
1409
  btime now_ = current_time();
1410

    
1411
  if (now_ >= ifa->next_hello)
1412
  {
1413
    babel_send_hello(ifa);
1414
    ifa->next_hello += hello_period * (1 + (now_ - ifa->next_hello) / hello_period);
1415
  }
1416

    
1417
  if (now_ >= ifa->next_regular)
1418
  {
1419
    TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
1420
    babel_send_update(ifa, 0);
1421
    ifa->next_regular += update_period * (1 + (now_ - ifa->next_regular) / update_period);
1422
    ifa->want_triggered = 0;
1423
    p->triggered = 0;
1424
  }
1425
  else if (ifa->want_triggered && (now_ >= ifa->next_triggered))
1426
  {
1427
    TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
1428
    babel_send_update(ifa, ifa->want_triggered);
1429
    ifa->next_triggered = now_ + MIN(1 S, update_period / 2);
1430
    ifa->want_triggered = 0;
1431
    p->triggered = 0;
1432
  }
1433

    
1434
  btime next_event = MIN(ifa->next_hello, ifa->next_regular);
1435
  if (ifa->want_triggered) next_event = MIN(next_event, ifa->next_triggered);
1436
  tm_set(ifa->timer, next_event);
1437
}
1438

    
1439
static inline void
1440
babel_iface_kick_timer(struct babel_iface *ifa)
1441
{
1442
  if (ifa->timer->expires > (current_time() + 100 MS))
1443
    tm_start(ifa->timer, 100 MS);
1444
}
1445

    
1446
static void
1447
babel_iface_start(struct babel_iface *ifa)
1448
{
1449
  struct babel_proto *p = ifa->proto;
1450

    
1451
  TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
1452

    
1453
  ifa->next_hello = current_time() + (random() % ifa->cf->hello_interval);
1454
  ifa->next_regular = current_time() + (random() % ifa->cf->update_interval);
1455
  ifa->next_triggered = current_time() + MIN(1 S, ifa->cf->update_interval / 2);
1456
  ifa->want_triggered = 0;        /* We send an immediate update (below) */
1457
  tm_start(ifa->timer, 100 MS);
1458
  ifa->up = 1;
1459

    
1460
  babel_send_hello(ifa);
1461
  babel_send_wildcard_retraction(ifa);
1462
  babel_send_wildcard_request(ifa);
1463
  babel_send_update(ifa, 0);        /* Full update */
1464
}
1465

    
1466
static void
1467
babel_iface_stop(struct babel_iface *ifa)
1468
{
1469
  struct babel_proto *p = ifa->proto;
1470
  struct babel_neighbor *nbr;
1471
  struct babel_route *r;
1472
  node *n;
1473

    
1474
  TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
1475

    
1476
  /*
1477
   * Rather than just flushing the neighbours, we set the metric of their routes
1478
   * to infinity. This allows us to keep the neighbour hello state for when the
1479
   * interface comes back up. The routes will also be kept until they expire.
1480
   */
1481
  WALK_LIST(nbr, ifa->neigh_list)
1482
  {
1483
    WALK_LIST(n, nbr->routes)
1484
    {
1485
      r = SKIP_BACK(struct babel_route, neigh_route, n);
1486
      babel_retract_route(p, r);
1487
    }
1488
  }
1489

    
1490
  tm_stop(ifa->timer);
1491
  ifa->up = 0;
1492
}
1493

    
1494
static inline int
1495
babel_iface_link_up(struct babel_iface *ifa)
1496
{
1497
  return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
1498
}
1499

    
1500
static void
1501
babel_iface_update_state(struct babel_iface *ifa)
1502
{
1503
  int up = ifa->sk && babel_iface_link_up(ifa);
1504

    
1505
  if (up == ifa->up)
1506
    return;
1507

    
1508
  if (up)
1509
    babel_iface_start(ifa);
1510
  else
1511
    babel_iface_stop(ifa);
1512
}
1513

    
1514
static void
1515
babel_iface_update_buffers(struct babel_iface *ifa)
1516
{
1517
  if (!ifa->sk)
1518
    return;
1519

    
1520
  uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
1521
  uint rbsize = ifa->cf->rx_buffer ?: mtu;
1522
  uint tbsize = ifa->cf->tx_length ?: mtu;
1523
  rbsize = MAX(rbsize, tbsize);
1524

    
1525
  sk_set_rbsize(ifa->sk, rbsize);
1526
  sk_set_tbsize(ifa->sk, tbsize);
1527

    
1528
  ifa->tx_length = tbsize - BABEL_OVERHEAD;
1529
}
1530

    
1531
static struct babel_iface*
1532
babel_find_iface(struct babel_proto *p, struct iface *what)
1533
{
1534
  struct babel_iface *ifa;
1535

    
1536
  WALK_LIST (ifa, p->interfaces)
1537
    if (ifa->iface == what)
1538
      return ifa;
1539

    
1540
  return NULL;
1541
}
1542

    
1543
static void
1544
babel_iface_locked(struct object_lock *lock)
1545
{
1546
  struct babel_iface *ifa = lock->data;
1547
  struct babel_proto *p = ifa->proto;
1548

    
1549
  if (!babel_open_socket(ifa))
1550
  {
1551
    log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
1552
    return;
1553
  }
1554

    
1555
  babel_iface_update_buffers(ifa);
1556
  babel_iface_update_state(ifa);
1557
}
1558

    
1559
static void
1560
babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
1561
{
1562
  struct babel_iface *ifa;
1563

    
1564
  TRACE(D_EVENTS, "Adding interface %s", new->name);
1565

    
1566
  pool *pool = rp_new(p->p.pool, new->name);
1567

    
1568
  ifa = mb_allocz(pool, sizeof(struct babel_iface));
1569
  ifa->proto = p;
1570
  ifa->iface = new;
1571
  ifa->cf = ic;
1572
  ifa->pool = pool;
1573
  ifa->ifname = new->name;
1574
  ifa->addr = new->llv6->ip;
1575

    
1576
  add_tail(&p->interfaces, NODE ifa);
1577

    
1578
  ip_addr addr4 = new->addr4 ? new->addr4->ip : IPA_NONE;
1579
  ifa->next_hop_ip4 = ipa_nonzero(ic->next_hop_ip4) ? ic->next_hop_ip4 : addr4;
1580
  ifa->next_hop_ip6 = ipa_nonzero(ic->next_hop_ip6) ? ic->next_hop_ip6 : ifa->addr;
1581

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

    
1585
  init_list(&ifa->neigh_list);
1586
  ifa->hello_seqno = 1;
1587

    
1588
  ifa->timer = tm_new_init(ifa->pool, babel_iface_timer, ifa, 0, 0);
1589

    
1590
  init_list(&ifa->msg_queue);
1591
  ifa->send_event = ev_new(ifa->pool);
1592
  ifa->send_event->hook = babel_send_queue;
1593
  ifa->send_event->data = ifa;
1594

    
1595
  struct object_lock *lock = olock_new(ifa->pool);
1596
  lock->type = OBJLOCK_UDP;
1597
  lock->addr = IP6_BABEL_ROUTERS;
1598
  lock->port = ifa->cf->port;
1599
  lock->iface = ifa->iface;
1600
  lock->hook = babel_iface_locked;
1601
  lock->data = ifa;
1602

    
1603
  olock_acquire(lock);
1604
}
1605

    
1606
static void
1607
babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
1608
{
1609
  TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
1610

    
1611
  struct babel_neighbor *n;
1612
  WALK_LIST_FIRST(n, ifa->neigh_list)
1613
    babel_flush_neighbor(p, n);
1614

    
1615
  rem_node(NODE ifa);
1616

    
1617
  rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
1618
}
1619

    
1620
static void
1621
babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
1622
{
1623
  struct babel_proto *p = (void *) P;
1624
  struct babel_config *cf = (void *) P->cf;
1625

    
1626
  if (iface->flags & IF_IGNORE)
1627
    return;
1628

    
1629
  if (flags & IF_CHANGE_UP)
1630
  {
1631
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1632

    
1633
    /* we only speak multicast */
1634
    if (!(iface->flags & IF_MULTICAST))
1635
      return;
1636

    
1637
    /* Ignore ifaces without link-local address */
1638
    if (!iface->llv6)
1639
      return;
1640

    
1641
    if (ic)
1642
      babel_add_iface(p, iface, ic);
1643

    
1644
    return;
1645
  }
1646

    
1647
  struct babel_iface *ifa = babel_find_iface(p, iface);
1648

    
1649
  if (!ifa)
1650
    return;
1651

    
1652
  if (flags & IF_CHANGE_DOWN)
1653
  {
1654
    babel_remove_iface(p, ifa);
1655
    return;
1656
  }
1657

    
1658
  if (flags & IF_CHANGE_MTU)
1659
    babel_iface_update_buffers(ifa);
1660

    
1661
  if (flags & IF_CHANGE_LINK)
1662
    babel_iface_update_state(ifa);
1663
}
1664

    
1665
static int
1666
babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new)
1667
{
1668
  struct babel_iface_config *old = ifa->cf;
1669

    
1670
  /* Change of these options would require to reset the iface socket */
1671
  if ((new->port != old->port) ||
1672
      (new->tx_tos != old->tx_tos) ||
1673
      (new->tx_priority != old->tx_priority))
1674
    return 0;
1675

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

    
1678
  ifa->cf = new;
1679

    
1680
  ip_addr addr4 = ifa->iface->addr4 ? ifa->iface->addr4->ip : IPA_NONE;
1681
  ifa->next_hop_ip4 = ipa_nonzero(new->next_hop_ip4) ? new->next_hop_ip4 : addr4;
1682
  ifa->next_hop_ip6 = ipa_nonzero(new->next_hop_ip6) ? new->next_hop_ip6 : ifa->addr;
1683

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

    
1687
  if (ifa->next_hello > (current_time() + new->hello_interval))
1688
    ifa->next_hello = current_time() + (random() % new->hello_interval);
1689

    
1690
  if (ifa->next_regular > (current_time() + new->update_interval))
1691
    ifa->next_regular = current_time() + (random() % new->update_interval);
1692

    
1693
  if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
1694
    babel_iface_update_buffers(ifa);
1695

    
1696
  if (new->check_link != old->check_link)
1697
    babel_iface_update_state(ifa);
1698

    
1699
  if (ifa->up)
1700
    babel_iface_kick_timer(ifa);
1701

    
1702
  return 1;
1703
}
1704

    
1705
static void
1706
babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
1707
{
1708
  struct iface *iface;
1709

    
1710
  WALK_LIST(iface, iface_list)
1711
  {
1712
    if (!(iface->flags & IF_UP))
1713
      continue;
1714

    
1715
    /* Ignore non-multicast ifaces */
1716
    if (!(iface->flags & IF_MULTICAST))
1717
      continue;
1718

    
1719
    /* Ignore ifaces without link-local address */
1720
    if (!iface->llv6)
1721
      continue;
1722

    
1723
    struct babel_iface *ifa = babel_find_iface(p, iface);
1724
    struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
1725

    
1726
    if (ifa && ic)
1727
    {
1728
      if (babel_reconfigure_iface(p, ifa, ic))
1729
        continue;
1730

    
1731
      /* Hard restart */
1732
      log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
1733
      babel_remove_iface(p, ifa);
1734
      babel_add_iface(p, iface, ic);
1735
    }
1736

    
1737
    if (ifa && !ic)
1738
      babel_remove_iface(p, ifa);
1739

    
1740
    if (!ifa && ic)
1741
      babel_add_iface(p, iface, ic);
1742
  }
1743
}
1744

    
1745

    
1746
/*
1747
 *        Debugging and info output functions
1748
 */
1749

    
1750
static void
1751
babel_dump_source(struct babel_source *s)
1752
{
1753
  debug("Source router_id %lR seqno %d metric %d expires %t\n",
1754
        s->router_id, s->seqno, s->metric,
1755
        s->expires ? s->expires - current_time() : 0);
1756
}
1757

    
1758
static void
1759
babel_dump_route(struct babel_route *r)
1760
{
1761
  debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %t\n",
1762
        r->neigh->addr, r->neigh->ifa->ifname, r->seqno, r->advert_metric, r->metric,
1763
        r->router_id, r->expires ? r->expires - current_time() : 0);
1764
}
1765

    
1766
static void
1767
babel_dump_entry(struct babel_entry *e)
1768
{
1769
  struct babel_source *s;
1770
  struct babel_route *r;
1771

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

    
1774
  WALK_LIST(s,e->sources)
1775
  { debug(" "); babel_dump_source(s); }
1776

    
1777
  WALK_LIST(r,e->routes)
1778
  {
1779
    debug(" ");
1780
    if (r == e->selected) debug("*");
1781
    babel_dump_route(r);
1782
  }
1783
}
1784

    
1785
static void
1786
babel_dump_neighbor(struct babel_neighbor *n)
1787
{
1788
  debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %t/%t\n",
1789
        n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
1790
        n->hello_expiry ? n->hello_expiry - current_time() : 0,
1791
        n->ihu_expiry ? n->ihu_expiry - current_time() : 0);
1792
}
1793

    
1794
static void
1795
babel_dump_iface(struct babel_iface *ifa)
1796
{
1797
  struct babel_neighbor *n;
1798

    
1799
  debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %t %t",
1800
        ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
1801
        ifa->cf->hello_interval, ifa->cf->update_interval);
1802
  debug(" next hop v4 %I next hop v6 %I\n", ifa->next_hop_ip4, ifa->next_hop_ip6);
1803

    
1804
  WALK_LIST(n, ifa->neigh_list)
1805
  { debug(" "); babel_dump_neighbor(n); }
1806
}
1807

    
1808
static void
1809
babel_dump(struct proto *P)
1810
{
1811
  struct babel_proto *p = (struct babel_proto *) P;
1812
  struct babel_iface *ifa;
1813

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

    
1816
  WALK_LIST(ifa, p->interfaces)
1817
    babel_dump_iface(ifa);
1818

    
1819
  FIB_WALK(&p->ip4_rtable, struct babel_entry, e)
1820
  {
1821
    babel_dump_entry(e);
1822
  }
1823
  FIB_WALK_END;
1824
  FIB_WALK(&p->ip6_rtable, struct babel_entry, e)
1825
  {
1826
    babel_dump_entry(e);
1827
  }
1828
  FIB_WALK_END;
1829
}
1830

    
1831
static void
1832
babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
1833
{
1834
  buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id);
1835
}
1836

    
1837
static int
1838
babel_get_attr(eattr *a, byte *buf, int buflen UNUSED)
1839
{
1840
  switch (a->id)
1841
  {
1842
  case EA_BABEL_METRIC:
1843
    bsprintf(buf, "metric: %d", a->u.data);
1844
    return GA_FULL;
1845

    
1846
  case EA_BABEL_ROUTER_ID:
1847
  {
1848
    u64 rid = 0;
1849
    memcpy(&rid, a->u.ptr->data, sizeof(u64));
1850
    bsprintf(buf, "router_id: %lR", rid);
1851
    return GA_FULL;
1852
  }
1853

    
1854
  default:
1855
    return GA_UNKNOWN;
1856
  }
1857
}
1858

    
1859
void
1860
babel_show_interfaces(struct proto *P, char *iff)
1861
{
1862
  struct babel_proto *p = (void *) P;
1863
  struct babel_iface *ifa = NULL;
1864
  struct babel_neighbor *nbr = NULL;
1865

    
1866
  if (p->p.proto_state != PS_UP)
1867
  {
1868
    cli_msg(-1023, "%s: is not up", p->p.name);
1869
    cli_msg(0, "");
1870
    return;
1871
  }
1872

    
1873
  cli_msg(-1023, "%s:", p->p.name);
1874
  cli_msg(-1023, "%-10s %-6s %7s %6s %7s %-15s %s",
1875
          "Interface", "State", "RX cost", "Nbrs", "Timer",
1876
          "Next hop (v4)", "Next hop (v6)");
1877

    
1878
  WALK_LIST(ifa, p->interfaces)
1879
  {
1880
    if (iff && !patmatch(iff, ifa->iface->name))
1881
      continue;
1882

    
1883
    int nbrs = 0;
1884
    WALK_LIST(nbr, ifa->neigh_list)
1885
        nbrs++;
1886

    
1887
    btime timer = MIN(ifa->next_regular, ifa->next_hello) - current_time();
1888
    cli_msg(-1023, "%-10s %-6s %7u %6u %7t %-15I %I",
1889
            ifa->iface->name, (ifa->up ? "Up" : "Down"),
1890
            ifa->cf->rxcost, nbrs, MAX(timer, 0),
1891
            ifa->next_hop_ip4, ifa->next_hop_ip6);
1892
  }
1893

    
1894
  cli_msg(0, "");
1895
}
1896

    
1897
void
1898
babel_show_neighbors(struct proto *P, char *iff)
1899
{
1900
  struct babel_proto *p = (void *) P;
1901
  struct babel_iface *ifa = NULL;
1902
  struct babel_neighbor *n = NULL;
1903
  struct babel_route *r = NULL;
1904

    
1905
  if (p->p.proto_state != PS_UP)
1906
  {
1907
    cli_msg(-1024, "%s: is not up", p->p.name);
1908
    cli_msg(0, "");
1909
    return;
1910
  }
1911

    
1912
  cli_msg(-1024, "%s:", p->p.name);
1913
  cli_msg(-1024, "%-25s %-10s %6s %6s %6s %7s",
1914
          "IP address", "Interface", "Metric", "Routes", "Hellos", "Expires");
1915

    
1916
  WALK_LIST(ifa, p->interfaces)
1917
  {
1918
    if (iff && !patmatch(iff, ifa->iface->name))
1919
      continue;
1920

    
1921
    WALK_LIST(n, ifa->neigh_list)
1922
    {
1923
      int rts = 0;
1924
      WALK_LIST(r, n->routes)
1925
        rts++;
1926

    
1927
      uint hellos = u32_popcount(n->hello_map);
1928
      btime timer = n->hello_expiry - current_time();
1929
      cli_msg(-1024, "%-25I %-10s %6u %6u %6u %7t",
1930
              n->addr, ifa->iface->name, n->cost, rts, hellos, MAX(timer, 0));
1931
    }
1932
  }
1933

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

    
1937
static void
1938
babel_show_entries_(struct babel_proto *p UNUSED, struct fib *rtable)
1939
{
1940
  FIB_WALK(rtable, struct babel_entry, e)
1941
  {
1942
    struct babel_route *r = NULL;
1943
    uint rts = 0, srcs = 0;
1944
    node *n;
1945

    
1946
    WALK_LIST(n, e->routes)
1947
      rts++;
1948

    
1949
    WALK_LIST(n, e->sources)
1950
      srcs++;
1951

    
1952
    if (e->valid)
1953
      cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u",
1954
              e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs);
1955
    else if (r = e->selected)
1956
      cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u",
1957
              e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs);
1958
    else
1959
      cli_msg(-1025, "%-24N %-23s %6s %5s %7u %7u",
1960
              e->n.addr, "<none>", "-", "-", rts, srcs);
1961
  }
1962
  FIB_WALK_END;
1963
}
1964

    
1965
void
1966
babel_show_entries(struct proto *P)
1967
{
1968
  struct babel_proto *p = (void *) P;
1969

    
1970
  if (p->p.proto_state != PS_UP)
1971
  {
1972
    cli_msg(-1025, "%s: is not up", p->p.name);
1973
    cli_msg(0, "");
1974
    return;
1975
  }
1976

    
1977
  cli_msg(-1025, "%s:", p->p.name);
1978
  cli_msg(-1025, "%-24s %-23s %6s %5s %7s %7s",
1979
          "Prefix", "Router ID", "Metric", "Seqno", "Routes", "Sources");
1980

    
1981
  babel_show_entries_(p, &p->ip4_rtable);
1982
  babel_show_entries_(p, &p->ip6_rtable);
1983

    
1984
  cli_msg(0, "");
1985
}
1986

    
1987
static void
1988
babel_show_routes_(struct babel_proto *p UNUSED, struct fib *rtable)
1989
{
1990
  FIB_WALK(rtable, struct babel_entry, e)
1991
  {
1992
    struct babel_route *r;
1993
    WALK_LIST(r, e->routes)
1994
    {
1995
      char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' ');
1996
      btime time = r->expires ? r->expires - current_time() : 0;
1997
      cli_msg(-1025, "%-24N %-25I %-10s %5u %c %5u %7t",
1998
              e->n.addr, r->next_hop, r->neigh->ifa->ifname,
1999
              r->metric, c, r->seqno, MAX(time, 0));
2000
    }
2001
  }
2002
  FIB_WALK_END;
2003
}
2004

    
2005
void
2006
babel_show_routes(struct proto *P)
2007
{
2008
  struct babel_proto *p = (void *) P;
2009

    
2010
  if (p->p.proto_state != PS_UP)
2011
  {
2012
    cli_msg(-1025, "%s: is not up", p->p.name);
2013
    cli_msg(0, "");
2014
    return;
2015
  }
2016

    
2017
  cli_msg(-1025, "%s:", p->p.name);
2018
  cli_msg(-1025, "%-24s %-25s %-9s %6s F %5s %7s",
2019
          "Prefix", "Nexthop", "Interface", "Metric", "Seqno", "Expires");
2020

    
2021
  babel_show_routes_(p, &p->ip4_rtable);
2022
  babel_show_routes_(p, &p->ip6_rtable);
2023

    
2024
  cli_msg(0, "");
2025
}
2026

    
2027

    
2028
/*
2029
 *        Babel protocol glue
2030
 */
2031

    
2032
/**
2033
 * babel_timer - global timer hook
2034
 * @t: Timer
2035
 *
2036
 * This function is called by the global protocol instance timer and handles
2037
 * expiration of routes and neighbours as well as pruning of the seqno request
2038
 * cache.
2039
 */
2040
static void
2041
babel_timer(timer *t)
2042
{
2043
  struct babel_proto *p = t->data;
2044

    
2045
  babel_expire_routes(p);
2046
  babel_expire_neighbors(p);
2047
}
2048

    
2049
static inline void
2050
babel_kick_timer(struct babel_proto *p)
2051
{
2052
  if (p->timer->expires > (current_time() + 100 MS))
2053
    tm_start(p->timer, 100 MS);
2054
}
2055

    
2056

    
2057
static struct ea_list *
2058
babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id)
2059
{
2060
  struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr));
2061
  struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64));
2062
  rid->length = sizeof(u64);
2063
  memcpy(&rid->data, &router_id, sizeof(u64));
2064

    
2065
  l->next = next;
2066
  l->flags = EALF_SORTED;
2067
  l->count = 2;
2068

    
2069
  l->attrs[0].id = EA_BABEL_METRIC;
2070
  l->attrs[0].flags = 0;
2071
  l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
2072
  l->attrs[0].u.data = metric;
2073

    
2074
  l->attrs[1].id = EA_BABEL_ROUTER_ID;
2075
  l->attrs[1].flags = 0;
2076
  l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
2077
  l->attrs[1].u.ptr = rid;
2078

    
2079
  return l;
2080
}
2081

    
2082

    
2083
static int
2084
babel_import_control(struct proto *P, struct rte **new, struct ea_list **attrs, struct linpool *pool)
2085
{
2086
  struct babel_proto *p = (void *) P;
2087
  rte *rt = *new;
2088

    
2089
  /* Reject our own unreachable routes */
2090
  if ((rt->attrs->dest == RTD_UNREACHABLE) && (rt->attrs->src->proto == P))
2091
    return -1;
2092

    
2093

    
2094
  /* Prepare attributes with initial values */
2095
  if (rt->attrs->source != RTS_BABEL)
2096
    *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
2097

    
2098
  return 0;
2099
}
2100

    
2101
static struct ea_list *
2102
babel_make_tmp_attrs(struct rte *rt, struct linpool *pool)
2103
{
2104
  return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id);
2105
}
2106

    
2107
static void
2108
babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs)
2109
{
2110
  rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
2111
}
2112

    
2113
/*
2114
 * babel_rt_notify - core tells us about new route (possibly our own),
2115
 * so store it into our data structures.
2116
 */
2117
static void
2118
babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net,
2119
                struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
2120
{
2121
  struct babel_proto *p = (void *) P;
2122
  struct babel_entry *e;
2123

    
2124
  if (new)
2125
  {
2126
    /* Update */
2127
    uint internal = (new->attrs->src->proto == P);
2128
    uint rt_seqno = internal ? new->u.babel.seqno : p->update_seqno;
2129
    uint rt_metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
2130
    uint rt_router_id = internal ? new->u.babel.router_id : p->router_id;
2131

    
2132
    if (rt_metric > BABEL_INFINITY)
2133
    {
2134
      log(L_WARN "%s: Invalid babel_metric value %u for route %N",
2135
          p->p.name, rt_metric, net->n.addr);
2136
      rt_metric = BABEL_INFINITY;
2137
    }
2138

    
2139
    e = babel_get_entry(p, net->n.addr);
2140

    
2141
    /* Activate triggered updates */
2142
    if ((e->valid |= BABEL_ENTRY_VALID) ||
2143
        (e->router_id != rt_router_id))
2144
    {
2145
      babel_trigger_update(p);
2146
      e->updated = current_time();
2147
    }
2148

    
2149
    e->valid = BABEL_ENTRY_VALID;
2150
    e->seqno = rt_seqno;
2151
    e->metric = rt_metric;
2152
    e->router_id = rt_router_id;
2153
  }
2154
  else
2155
  {
2156
    /* Withdraw */
2157
    e = babel_find_entry(p, net->n.addr);
2158

    
2159
    if (!e || e->valid != BABEL_ENTRY_VALID)
2160
      return;
2161

    
2162
    e->valid = BABEL_ENTRY_STALE;
2163
    e->metric = BABEL_INFINITY;
2164

    
2165
    babel_trigger_update(p);
2166
    e->updated = current_time();
2167
  }
2168
}
2169

    
2170
static int
2171
babel_rte_better(struct rte *new, struct rte *old)
2172
{
2173
  return new->u.babel.metric < old->u.babel.metric;
2174
}
2175

    
2176
static int
2177
babel_rte_same(struct rte *new, struct rte *old)
2178
{
2179
  return ((new->u.babel.seqno == old->u.babel.seqno) &&
2180
          (new->u.babel.metric == old->u.babel.metric) &&
2181
          (new->u.babel.router_id == old->u.babel.router_id));
2182
}
2183

    
2184

    
2185
static struct proto *
2186
babel_init(struct proto_config *CF)
2187
{
2188
  struct proto *P = proto_new(CF);
2189
  struct babel_proto *p = (void *) P;
2190

    
2191
  proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4));
2192
  proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6));
2193

    
2194
  P->if_notify = babel_if_notify;
2195
  P->rt_notify = babel_rt_notify;
2196
  P->import_control = babel_import_control;
2197
  P->make_tmp_attrs = babel_make_tmp_attrs;
2198
  P->store_tmp_attrs = babel_store_tmp_attrs;
2199
  P->rte_better = babel_rte_better;
2200
  P->rte_same = babel_rte_same;
2201

    
2202
  return P;
2203
}
2204

    
2205
static int
2206
babel_start(struct proto *P)
2207
{
2208
  struct babel_proto *p = (void *) P;
2209
  struct babel_config *cf = (void *) P->cf;
2210

    
2211
  fib_init(&p->ip4_rtable, P->pool, NET_IP4, sizeof(struct babel_entry),
2212
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2213
  fib_init(&p->ip6_rtable, P->pool, NET_IP6, sizeof(struct babel_entry),
2214
           OFFSETOF(struct babel_entry, n), 0, babel_init_entry);
2215

    
2216
  init_list(&p->interfaces);
2217
  p->timer = tm_new_init(P->pool, babel_timer, p, 1 S, 0);
2218
  tm_start(p->timer, 1 S);
2219
  p->update_seqno = 1;
2220
  p->router_id = proto_get_router_id(&cf->c);
2221

    
2222
  p->route_slab = sl_new(P->pool, sizeof(struct babel_route));
2223
  p->source_slab = sl_new(P->pool, sizeof(struct babel_source));
2224
  p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node));
2225
  p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request));
2226

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

    
2229
  return PS_UP;
2230
}
2231

    
2232
static inline void
2233
babel_iface_shutdown(struct babel_iface *ifa)
2234
{
2235
  if (ifa->sk)
2236
  {
2237
    babel_send_wildcard_retraction(ifa);
2238
    babel_send_queue(ifa);
2239
  }
2240
}
2241

    
2242
static int
2243
babel_shutdown(struct proto *P)
2244
{
2245
  struct babel_proto *p = (void *) P;
2246
  struct babel_iface *ifa;
2247

    
2248
  TRACE(D_EVENTS, "Shutdown requested");
2249

    
2250
  WALK_LIST(ifa, p->interfaces)
2251
    babel_iface_shutdown(ifa);
2252

    
2253
  return PS_DOWN;
2254
}
2255

    
2256
static int
2257
babel_reconfigure(struct proto *P, struct proto_config *CF)
2258
{
2259
  struct babel_proto *p = (void *) P;
2260
  struct babel_config *new = (void *) CF;
2261

    
2262
  TRACE(D_EVENTS, "Reconfiguring");
2263

    
2264
  if (!proto_configure_channel(P, &p->ip4_channel, proto_cf_find_channel(CF, NET_IP4)) ||
2265
      !proto_configure_channel(P, &p->ip6_channel, proto_cf_find_channel(CF, NET_IP6)))
2266
    return 0;
2267

    
2268
  p->p.cf = CF;
2269
  babel_reconfigure_ifaces(p, new);
2270

    
2271
  babel_trigger_update(p);
2272
  babel_kick_timer(p);
2273

    
2274
  return 1;
2275
}
2276

    
2277

    
2278
struct protocol proto_babel = {
2279
  .name =                "Babel",
2280
  .template =                "babel%d",
2281
  .attr_class =                EAP_BABEL,
2282
  .preference =                DEF_PREF_BABEL,
2283
  .channel_mask =        NB_IP,
2284
  .proto_size =                sizeof(struct babel_proto),
2285
  .config_size =        sizeof(struct babel_config),
2286
  .init =                babel_init,
2287
  .dump =                babel_dump,
2288
  .start =                babel_start,
2289
  .shutdown =                babel_shutdown,
2290
  .reconfigure =        babel_reconfigure,
2291
  .get_route_info =        babel_get_route_info,
2292
  .get_attr =                babel_get_attr
2293
};