bfd.c 28.1 KB
Newer Older
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1 2 3 4 5
/*
 *	BIRD -- Bidirectional Forwarding Detection (BFD)
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */
6

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
/**
 * DOC: Bidirectional Forwarding Detection
 *
 * The BFD protocol is implemented in three files: |bfd.c| containing the
 * protocol logic and the protocol glue with BIRD core, |packets.c| handling BFD
 * packet processing, RX, TX and protocol sockets. |io.c| then contains generic
 * code for the event loop, threads and event sources (sockets, microsecond
 * timers). This generic code will be merged to the main BIRD I/O code in the
 * future.
 *
 * The BFD implementation uses a separate thread with an internal event loop for
 * handling the protocol logic, which requires high-res and low-latency timing,
 * so it is not affected by the rest of BIRD, which has several low-granularity
 * hooks in the main loop, uses second-based timers and cannot offer good
 * latency. The core of BFD protocol (the code related to BFD sessions,
 * interfaces and packets) runs in the BFD thread, while the rest (the code
 * related to BFD requests, BFD neighbors and the protocol glue) runs in the
 * main thread.
 *
 * BFD sessions are represented by structure &bfd_session that contains a state
 * related to the session and two timers (TX timer for periodic packets and hold
 * timer for session timeout). These sessions are allocated from @session_slab
 * and are accessible by two hash tables, @session_hash_id (by session ID) and
 * @session_hash_ip (by IP addresses of neighbors). Slab and both hashes are in
 * the main protocol structure &bfd_proto. The protocol logic related to BFD
 * sessions is implemented in internal functions bfd_session_*(), which are
 * expected to be called from the context of BFD thread, and external functions
 * bfd_add_session(), bfd_remove_session() and bfd_reconfigure_session(), which
 * form an interface to the BFD core for the rest and are expected to be called
 * from the context of main thread.
 *
 * Each BFD session has an associated BFD interface, represented by structure
 * &bfd_iface. A BFD interface contains a socket used for TX (the one for RX is
 * shared in &bfd_proto), an interface configuration and reference counter.
 * Compared to interface structures of other protocols, these structures are not
 * created and removed based on interface notification events, but according to
 * the needs of BFD sessions. When a new session is created, it requests a
 * proper BFD interface by function bfd_get_iface(), which either finds an
 * existing one in &iface_list (from &bfd_proto) or allocates a new one. When a
46
 * session is removed, an associated iface is discharged by bfd_free_iface().
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
 *
 * BFD requests are the external API for the other protocols. When a protocol
 * wants a BFD session, it calls bfd_request_session(), which creates a
 * structure &bfd_request containing approprite information and an notify hook.
 * This structure is a resource associated with the caller's resource pool. When
 * a BFD protocol is available, a BFD request is submitted to the protocol, an
 * appropriate BFD session is found or created and the request is attached to
 * the session. When a session changes state, all attached requests (and related
 * protocols) are notified. Note that BFD requests do not depend on BFD protocol
 * running. When the BFD protocol is stopped or removed (or not available from
 * beginning), related BFD requests are stored in @bfd_wait_list, where waits
 * for a new protocol.
 *
 * BFD neighbors are just a way to statically configure BFD sessions without
 * requests from other protocol. Structures &bfd_neighbor are part of BFD
 * configuration (like static routes in the static protocol). BFD neighbors are
 * handled by BFD protocol like it is a BFD client -- when a BFD neighbor is
 * ready, the protocol just creates a BFD request like any other protocol.
65
 *
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
 * The protocol uses a new generic event loop (structure &birdloop) from |io.c|,
 * which supports sockets, timers and events like the main loop. Timers
 * (structure &timer2) are new microsecond based timers, while sockets and
 * events are the same. A birdloop is associated with a thread (field @thread)
 * in which event hooks are executed. Most functions for setting event sources
 * (like sk_start() or tm2_start()) must be called from the context of that
 * thread. Birdloop allows to temporarily acquire the context of that thread for
 * the main thread by calling birdloop_enter() and then birdloop_leave(), which
 * also ensures mutual exclusion with all event hooks. Note that resources
 * associated with a birdloop (like timers) should be attached to the
 * independent resource pool, detached from the main resource tree.
 *
 * There are two kinds of interaction between the BFD core (running in the BFD
 * thread) and the rest of BFD (running in the main thread). The first kind are
 * configuration calls from main thread to the BFD thread (like bfd_add_session()).
 * These calls are synchronous and use birdloop_enter() mechanism for mutual
 * exclusion. The second kind is a notification about session changes from the
 * BFD thread to the main thread. This is done in an asynchronous way, sesions
 * with pending notifications are linked (in the BFD thread) to @notify_list in
 * &bfd_proto, and then bfd_notify_hook() in the main thread is activated using
 * bfd_notify_kick() and a pipe. The hook then processes scheduled sessions and
 * calls hooks from associated BFD requests. This @notify_list (and state fields
 * in structure &bfd_session) is protected by a spinlock in &bfd_proto and
 * functions bfd_lock_sessions() / bfd_unlock_sessions().
 *
 * There are few data races (accessing @p->p.debug from TRACE() from the BFD
 * thread and accessing some some private fields of %bfd_session from
 * bfd_show_sessions() from the main thread, but these are harmless (i hope).
 *
 * TODO: document functions and access restrictions for fields in BFD structures.
 *
 * Supported standards:
 * - RFC 5880 - main BFD standard
 * - RFC 5881 - BFD for IP links
 * - RFC 5882 - generic application of BFD
 * - RFC 5883 - BFD for multihop paths
 */

104 105 106
#include "bfd.h"


Ondřej Zajíček's avatar
Ondřej Zajíček committed
107 108
#define HASH_ID_KEY(n)		n->loc_id
#define HASH_ID_NEXT(n)		n->next_id
Ondřej Zajíček's avatar
Ondřej Zajíček committed
109 110
#define HASH_ID_EQ(a,b)		a == b
#define HASH_ID_FN(k)		k
111

Ondřej Zajíček's avatar
Ondřej Zajíček committed
112 113 114
#define HASH_IP_KEY(n)		n->addr
#define HASH_IP_NEXT(n)		n->next_ip
#define HASH_IP_EQ(a,b)		ipa_equal(a,b)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
115
#define HASH_IP_FN(k)		ipa_hash32(k)
116

117 118
static list bfd_proto_list;
static list bfd_wait_list;
119 120 121

const char *bfd_state_names[] = { "AdminDown", "Down", "Init", "Up" };

122 123 124
static void bfd_session_set_min_tx(struct bfd_session *s, u32 val);
static struct bfd_iface *bfd_get_iface(struct bfd_proto *p, ip_addr local, struct iface *iface);
static void bfd_free_iface(struct bfd_iface *ifa);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
125
static inline void bfd_notify_kick(struct bfd_proto *p);
126

127 128 129 130 131

/*
 *	BFD sessions
 */

132
static void
Ondřej Zajíček's avatar
Ondřej Zajíček committed
133
bfd_session_update_state(struct bfd_session *s, uint state, uint diag)
134
{
135
  struct bfd_proto *p = s->ifa->bfd;
136
  uint old_state = s->loc_state;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
137
  int notify;
138

139
  if (state == old_state)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
140
    return;
141

142 143 144
  TRACE(D_EVENTS, "Session to %I changed state from %s to %s",
	s->addr, bfd_state_names[old_state], bfd_state_names[state]);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
145 146 147
  bfd_lock_sessions(p);
  s->loc_state = state;
  s->loc_diag = diag;
148

Ondřej Zajíček's avatar
Ondřej Zajíček committed
149 150 151 152
  notify = !NODE_VALID(&s->n);
  if (notify)
    add_tail(&p->notify_list, &s->n);
  bfd_unlock_sessions(p);
153

154 155
  if (state == BFD_STATE_UP)
    bfd_session_set_min_tx(s, s->ifa->cf->min_tx_int);
156

157 158
  if (old_state == BFD_STATE_UP)
    bfd_session_set_min_tx(s, s->ifa->cf->idle_tx_int);
159

160 161
  if (notify)
    bfd_notify_kick(p);
162 163 164
}

static void
Ondřej Zajíček's avatar
Ondřej Zajíček committed
165
bfd_session_update_tx_interval(struct bfd_session *s)
166
{
Ondřej Zajíček's avatar
Ondřej Zajíček committed
167 168 169
  u32 tx_int = MAX(s->des_min_tx_int, s->rem_min_rx_int);
  u32 tx_int_l = tx_int - (tx_int / 4);	 // 75 %
  u32 tx_int_h = tx_int - (tx_int / 10); // 90 %
170

Ondřej Zajíček's avatar
Ondřej Zajíček committed
171 172
  s->tx_timer->recurrent = tx_int_l;
  s->tx_timer->randomize = tx_int_h - tx_int_l;
173

Ondřej Zajíček's avatar
Ondřej Zajíček committed
174 175 176
  /* Do not set timer if no previous event */
  if (!s->last_tx)
    return;
177

Ondřej Zajíček's avatar
Ondřej Zajíček committed
178 179
  /* Set timer relative to last tx_timer event */
  tm2_set(s->tx_timer, s->last_tx + tx_int_l);
180 181 182
}

static void
Ondřej Zajíček's avatar
Ondřej Zajíček committed
183
bfd_session_update_detection_time(struct bfd_session *s, int kick)
184
{
Ondřej Zajíček's avatar
Ondřej Zajíček committed
185
  btime timeout = (btime) MAX(s->req_min_rx_int, s->rem_min_tx_int) * s->rem_detect_mult;
186

Ondřej Zajíček's avatar
Ondřej Zajíček committed
187 188
  if (kick)
    s->last_rx = current_time();
189

Ondřej Zajíček's avatar
Ondřej Zajíček committed
190 191
  if (!s->last_rx)
    return;
192

Ondřej Zajíček's avatar
Ondřej Zajíček committed
193
  tm2_set(s->hold_timer, s->last_rx + timeout);
194 195 196
}

static void
197
bfd_session_control_tx_timer(struct bfd_session *s, int reset)
198
{
199
  // if (!s->opened) goto stop;
200 201 202 203

  if (s->passive && (s->rem_id == 0))
    goto stop;

204 205
  if (s->rem_demand_mode &&
      !s->poll_active &&
206 207 208 209 210 211 212 213
      (s->loc_state == BFD_STATE_UP) &&
      (s->rem_state == BFD_STATE_UP))
    goto stop;

  if (s->rem_min_rx_int == 0)
    goto stop;

  /* So TX timer should run */
214 215 216 217 218
  if (reset || !tm2_active(s->tx_timer))
  {
    s->last_tx = 0;
    tm2_start(s->tx_timer, 0);
  }
219 220 221 222 223 224 225 226 227 228 229

  return;

 stop:
  tm2_stop(s->tx_timer);
  s->last_tx = 0;
}

static void
bfd_session_request_poll(struct bfd_session *s, u8 request)
{
230 231 232 233
  /* Not sure about this, but doing poll in this case does not make sense */
  if (s->rem_id == 0)
    return;

234 235 236 237 238 239 240
  s->poll_scheduled |= request;

  if (s->poll_active)
    return;

  s->poll_active = s->poll_scheduled;
  s->poll_scheduled = 0;
241 242

  bfd_session_control_tx_timer(s, 1);
243 244
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
245
static void
246 247 248 249 250 251 252 253 254 255
bfd_session_terminate_poll(struct bfd_session *s)
{
  u8 poll_done = s->poll_active & ~s->poll_scheduled;

  if (poll_done & BFD_POLL_TX)
    s->des_min_tx_int = s->des_min_tx_new;

  if (poll_done & BFD_POLL_RX)
    s->req_min_rx_int = s->req_min_rx_new;

256 257
  s->poll_active = s->poll_scheduled;
  s->poll_scheduled = 0;
258 259 260 261 262

  /* Timers are updated by caller - bfd_session_process_ctl() */
}

void
Ondřej Zajíček's avatar
Ondřej Zajíček committed
263
bfd_session_process_ctl(struct bfd_session *s, u8 flags, u32 old_tx_int, u32 old_rx_int)
264 265 266 267
{
  if (s->poll_active && (flags & BFD_FLAG_FINAL))
    bfd_session_terminate_poll(s);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
268
  if ((s->des_min_tx_int != old_tx_int) || (s->rem_min_rx_int != old_rx_int))
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
    bfd_session_update_tx_interval(s);

  bfd_session_update_detection_time(s, 1);

  /* Update session state */
  int next_state = 0;
  int diag = BFD_DIAG_NOTHING;

  switch (s->loc_state)
  {
  case BFD_STATE_ADMIN_DOWN:
    return;

  case BFD_STATE_DOWN:
    if (s->rem_state == BFD_STATE_DOWN)		next_state = BFD_STATE_INIT;
    else if (s->rem_state == BFD_STATE_INIT)	next_state = BFD_STATE_UP;
    break;

  case BFD_STATE_INIT:
    if (s->rem_state == BFD_STATE_ADMIN_DOWN)	next_state = BFD_STATE_DOWN, diag = BFD_DIAG_NEIGHBOR_DOWN;
    else if (s->rem_state >= BFD_STATE_INIT)	next_state = BFD_STATE_UP;
    break;

  case BFD_STATE_UP:
    if (s->rem_state <= BFD_STATE_DOWN)		next_state = BFD_STATE_DOWN, diag = BFD_DIAG_NEIGHBOR_DOWN;
    break;
  }

  if (next_state)
    bfd_session_update_state(s, next_state, diag);

300
  bfd_session_control_tx_timer(s, 0);
301 302

  if (flags & BFD_FLAG_POLL)
303 304 305
    bfd_send_ctl(s->ifa->bfd, s, 1);
}

306
static void
307 308 309 310 311 312 313 314 315 316 317 318
bfd_session_timeout(struct bfd_session *s)
{
  struct bfd_proto *p = s->ifa->bfd;

  TRACE(D_EVENTS, "Session to %I expired", s->addr);

  s->rem_state = BFD_STATE_DOWN;
  s->rem_id = 0;
  s->rem_min_tx_int = 0;
  s->rem_min_rx_int = 1;
  s->rem_demand_mode = 0;
  s->rem_detect_mult = 0;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
319
  s->rx_csn_known = 0;
320 321 322 323 324 325 326

  s->poll_active = 0;
  s->poll_scheduled = 0;

  bfd_session_update_state(s, BFD_STATE_DOWN, BFD_DIAG_TIMEOUT);

  bfd_session_control_tx_timer(s, 1);
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
}

static void
bfd_session_set_min_tx(struct bfd_session *s, u32 val)
{
  /* Note that des_min_tx_int <= des_min_tx_new */

  if (val == s->des_min_tx_new)
    return;

  s->des_min_tx_new = val;

  /* Postpone timer update if des_min_tx_int increases and the session is up */
  if ((s->loc_state != BFD_STATE_UP) || (val < s->des_min_tx_int))
  {
    s->des_min_tx_int = val;
    bfd_session_update_tx_interval(s);
  }

  bfd_session_request_poll(s, BFD_POLL_TX);
}

static void
bfd_session_set_min_rx(struct bfd_session *s, u32 val)
{
  /* Note that req_min_rx_int >= req_min_rx_new */

  if (val == s->req_min_rx_new)
    return;

357
  s->req_min_rx_new = val;
358 359 360 361 362 363 364 365 366 367 368

  /* Postpone timer update if req_min_rx_int decreases and the session is up */
  if ((s->loc_state != BFD_STATE_UP) || (val > s->req_min_rx_int))
  {
    s->req_min_rx_int = val;
    bfd_session_update_detection_time(s, 0);
  }

  bfd_session_request_poll(s, BFD_POLL_RX);
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
struct bfd_session *
bfd_find_session_by_id(struct bfd_proto *p, u32 id)
{
  return HASH_FIND(p->session_hash_id, HASH_ID, id);
}

struct bfd_session *
bfd_find_session_by_addr(struct bfd_proto *p, ip_addr addr)
{
  return HASH_FIND(p->session_hash_ip, HASH_IP, addr);
}

static void
bfd_tx_timer_hook(timer2 *t)
{
  struct bfd_session *s = t->data;

  s->last_tx = current_time();
387
  bfd_send_ctl(s->ifa->bfd, s, 0);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
}

static void
bfd_hold_timer_hook(timer2 *t)
{
  bfd_session_timeout(t->data);
}

static u32
bfd_get_free_id(struct bfd_proto *p)
{
  u32 id;
  for (id = random_u32(); 1; id++)
    if (id && !bfd_find_session_by_id(p, id))
      break;

  return id;
}

static struct bfd_session *
408
bfd_add_session(struct bfd_proto *p, ip_addr addr, ip_addr local, struct iface *iface)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
409 410 411
{
  birdloop_enter(p->loop);

412 413
  struct bfd_iface *ifa = bfd_get_iface(p, local, iface);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
414 415 416 417
  struct bfd_session *s = sl_alloc(p->session_slab);
  bzero(s, sizeof(struct bfd_session));

  s->addr = addr;
418
  s->ifa = ifa;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
419
  s->loc_id = bfd_get_free_id(p);
420

Ondřej Zajíček's avatar
Ondřej Zajíček committed
421 422
  HASH_INSERT(p->session_hash_id, HASH_ID, s);
  HASH_INSERT(p->session_hash_ip, HASH_IP, s);
423

Ondřej Zajíček's avatar
Ondřej Zajíček committed
424 425 426 427

  /* Initialization of state variables - see RFC 5880 6.8.1 */
  s->loc_state = BFD_STATE_DOWN;
  s->rem_state = BFD_STATE_DOWN;
428 429
  s->des_min_tx_int = s->des_min_tx_new = ifa->cf->idle_tx_int;
  s->req_min_rx_int = s->req_min_rx_new = ifa->cf->min_rx_int;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
430
  s->rem_min_rx_int = 1;
431 432
  s->detect_mult = ifa->cf->multiplier;
  s->passive = ifa->cf->passive;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
433
  s->tx_csn = random_u32();
Ondřej Zajíček's avatar
Ondřej Zajíček committed
434 435 436 437

  s->tx_timer = tm2_new_init(p->tpool, bfd_tx_timer_hook, s, 0, 0);
  s->hold_timer = tm2_new_init(p->tpool, bfd_hold_timer_hook, s, 0, 0);
  bfd_session_update_tx_interval(s);
438 439 440 441 442 443
  bfd_session_control_tx_timer(s, 1);

  init_list(&s->request_list);
  s->last_state_change = now;

  TRACE(D_EVENTS, "Session to %I added", s->addr);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
444 445 446 447 448 449

  birdloop_leave(p->loop);

  return s;
}

450
/*
Ondřej Zajíček's avatar
Ondřej Zajíček committed
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474
static void
bfd_open_session(struct bfd_proto *p, struct bfd_session *s, ip_addr local, struct iface *ifa)
{
  birdloop_enter(p->loop);

  s->opened = 1;

  bfd_session_control_tx_timer(s);

  birdloop_leave(p->loop);
}

static void
bfd_close_session(struct bfd_proto *p, struct bfd_session *s)
{
  birdloop_enter(p->loop);

  s->opened = 0;

  bfd_session_update_state(s, BFD_STATE_DOWN, BFD_DIAG_PATH_DOWN);
  bfd_session_control_tx_timer(s);

  birdloop_leave(p->loop);
}
475
*/
Ondřej Zajíček's avatar
Ondřej Zajíček committed
476 477 478 479

static void
bfd_remove_session(struct bfd_proto *p, struct bfd_session *s)
{
480 481
  ip_addr ip = s->addr;

Ondřej Zajíček's avatar
Ondřej Zajíček committed
482 483
  /* Caller should ensure that request list is empty */

Ondřej Zajíček's avatar
Ondřej Zajíček committed
484 485
  birdloop_enter(p->loop);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
486 487 488 489 490
  /* Remove session from notify list if scheduled for notification */
  /* No need for bfd_lock_sessions(), we are already protected by birdloop_enter() */
  if (NODE_VALID(&s->n))
    rem_node(&s->n);

491
  bfd_free_iface(s->ifa);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
492 493 494 495 496 497 498 499 500

  rfree(s->tx_timer);
  rfree(s->hold_timer);

  HASH_REMOVE(p->session_hash_id, HASH_ID, s);
  HASH_REMOVE(p->session_hash_ip, HASH_IP, s);

  sl_free(p->session_slab, s);

501 502
  TRACE(D_EVENTS, "Session to %I removed", ip);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
503 504 505 506
  birdloop_leave(p->loop);
}

static void
507
bfd_reconfigure_session(struct bfd_proto *p, struct bfd_session *s)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
508 509 510
{
  birdloop_enter(p->loop);

511
  struct bfd_iface_config *cf = s->ifa->cf;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
512

513 514 515 516 517
  u32 tx = (s->loc_state == BFD_STATE_UP) ? cf->min_tx_int : cf->idle_tx_int;
  bfd_session_set_min_tx(s, tx);
  bfd_session_set_min_rx(s, cf->min_rx_int);
  s->detect_mult = cf->multiplier;
  s->passive = cf->passive;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
518

519
  bfd_session_control_tx_timer(s, 0);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
520 521

  birdloop_leave(p->loop);
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579

  TRACE(D_EVENTS, "Session to %I reconfigured", s->addr);
}


/*
 *	BFD interfaces
 */

static struct bfd_iface_config bfd_default_iface = {
  .min_rx_int = BFD_DEFAULT_MIN_RX_INT,
  .min_tx_int = BFD_DEFAULT_MIN_TX_INT,
  .idle_tx_int = BFD_DEFAULT_IDLE_TX_INT,
  .multiplier = BFD_DEFAULT_MULTIPLIER
};

static inline struct bfd_iface_config *
bfd_find_iface_config(struct bfd_config *cf, struct iface *iface)
{
  struct bfd_iface_config *ic;

  ic = iface ? (void *) iface_patt_find(&cf->patt_list, iface, NULL) : cf->multihop;

  return ic ? ic : &bfd_default_iface;
}

static struct bfd_iface *
bfd_get_iface(struct bfd_proto *p, ip_addr local, struct iface *iface)
{
  struct bfd_iface *ifa;

  WALK_LIST(ifa, p->iface_list)
    if (ipa_equal(ifa->local, local) && (ifa->iface == iface))
      return ifa->uc++, ifa;

  struct bfd_config *cf = (struct bfd_config *) (p->p.cf);
  struct bfd_iface_config *ic = bfd_find_iface_config(cf, iface);

  ifa = mb_allocz(p->tpool, sizeof(struct bfd_iface));
  ifa->local = local;
  ifa->iface = iface;
  ifa->cf = ic;
  ifa->bfd = p;

  ifa->sk = bfd_open_tx_sk(p, local, iface);
  ifa->uc = 1;

  add_tail(&p->iface_list, &ifa->n);

  return ifa;
}

static void
bfd_free_iface(struct bfd_iface *ifa)
{
  if (!ifa || --ifa->uc)
    return;

580 581 582 583 584 585
  if (ifa->sk)
  {
    sk_stop(ifa->sk);
    rfree(ifa->sk);
  }

586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
  rem_node(&ifa->n);
  mb_free(ifa);
}

static void
bfd_reconfigure_iface(struct bfd_proto *p, struct bfd_iface *ifa, struct bfd_config *nc)
{
  struct bfd_iface_config *nic = bfd_find_iface_config(nc, ifa->iface);
  ifa->changed = !!memcmp(nic, ifa->cf, sizeof(struct bfd_iface_config));

  /* This should be probably changed to not access ifa->cf from the BFD thread */
  birdloop_enter(p->loop);
  ifa->cf = nic;
  birdloop_leave(p->loop);
}


/*
 *	BFD requests
 */

static void
bfd_request_notify(struct bfd_request *req, u8 state, u8 diag)
{
  u8 old_state = req->state;

  if (state == old_state)
    return;

  req->state = state;
  req->diag = diag;
  req->old_state = old_state;
  req->down = (old_state == BFD_STATE_UP) && (state == BFD_STATE_DOWN);

  if (req->hook)
    req->hook(req);
}

static int
bfd_add_request(struct bfd_proto *p, struct bfd_request *req)
{
  struct bfd_session *s = bfd_find_session_by_addr(p, req->addr);
  u8 state, diag;

  if (!s)
    s = bfd_add_session(p, req->addr, req->local, req->iface);

  rem_node(&req->n);
  add_tail(&s->request_list, &req->n);
  req->session = s;

  bfd_lock_sessions(p);
  state = s->loc_state;
  diag = s->loc_diag;
  bfd_unlock_sessions(p);

  bfd_request_notify(req, state, diag);

  return 1;
}

static void
bfd_submit_request(struct bfd_request *req)
{
  node *n;

  WALK_LIST(n, bfd_proto_list)
    if (bfd_add_request(SKIP_BACK(struct bfd_proto, bfd_node, n), req))
      return;

  rem_node(&req->n);
  add_tail(&bfd_wait_list, &req->n);
  req->session = NULL;
  bfd_request_notify(req, BFD_STATE_ADMIN_DOWN, 0);
}

static void
bfd_take_requests(struct bfd_proto *p)
{
  node *n, *nn;

  WALK_LIST_DELSAFE(n, nn, bfd_wait_list)
    bfd_add_request(p, SKIP_BACK(struct bfd_request, n, n));
}

static void
bfd_drop_requests(struct bfd_proto *p)
{
  node *n;

  HASH_WALK(p->session_hash_id, next_id, s)
  {
    /* We assume that p is not in bfd_proto_list */
    WALK_LIST_FIRST(n, s->request_list)
      bfd_submit_request(SKIP_BACK(struct bfd_request, n, n));
  }
  HASH_WALK_END;
}

static struct resclass bfd_request_class;

struct bfd_request *
bfd_request_session(pool *p, ip_addr addr, ip_addr local, struct iface *iface,
		    void (*hook)(struct bfd_request *), void *data)
{
  struct bfd_request *req = ralloc(p, &bfd_request_class);

  /* Hack: self-link req->n, we will call rem_node() on it */
  req->n.prev = req->n.next = &req->n;

  req->addr = addr;
  req->local = local;
  req->iface = iface;

  bfd_submit_request(req);

  req->hook = hook;
  req->data = data;

  return req;
}

static void
bfd_request_free(resource *r)
{
  struct bfd_request *req = (struct bfd_request *) r;
  struct bfd_session *s = req->session;

  rem_node(&req->n);

  /* Remove the session if there is no request for it. Skip that if
     inside notify hooks, will be handled by bfd_notify_hook() itself */

  if (s && EMPTY_LIST(s->request_list) && !s->notify_running)
    bfd_remove_session(s->ifa->bfd, s);
}

static void
bfd_request_dump(resource *r)
{
  struct bfd_request *req = (struct bfd_request *) r;

  debug("(code %p, data %p)\n", req->hook, req->data);
}

static struct resclass bfd_request_class = {
  "BFD request",
  sizeof(struct bfd_request),
  bfd_request_free,
  bfd_request_dump,
  NULL,
  NULL
};


/*
 *	BFD neighbors
 */

static void
bfd_neigh_notify(struct neighbor *nb)
{
  struct bfd_proto *p = (struct bfd_proto *) nb->proto;
  struct bfd_neighbor *n = nb->data;

  if (!n)
    return;

  if ((nb->scope > 0) && !n->req)
  {
756
    ip_addr local = ipa_nonzero(n->local) ? n->local : nb->ifa->ip;
757 758 759 760 761 762 763 764
    n->req = bfd_request_session(p->p.pool, n->addr, local, nb->iface, NULL, NULL);
  }

  if ((nb->scope <= 0) && n->req)
  {
    rfree(n->req);
    n->req = NULL;
  }
Ondřej Zajíček's avatar
Ondřej Zajíček committed
765 766
}

767 768 769
static void
bfd_start_neighbor(struct bfd_proto *p, struct bfd_neighbor *n)
{
770
  n->active = 1;
771

772
  if (n->multihop)
773
  {
774
    n->req = bfd_request_session(p->p.pool, n->addr, n->local, NULL, NULL, NULL);
775 776 777 778 779 780 781 782 783 784 785 786
    return;
  }

  struct neighbor *nb = neigh_find2(&p->p, &n->addr, n->iface, NEF_STICKY);
  if (!nb)
  {
    log(L_ERR "%s: Invalid remote address %I%J", p->p.name, n->addr, n->iface);
    return;
  }

  if (nb->data)
  {
787
    log(L_ERR "%s: Duplicate neighbor %I", p->p.name, n->addr);
788 789 790
    return;
  }

791 792
  n->neigh = nb;
  nb->data = n;
793 794

  if (nb->scope > 0)
795
    bfd_neigh_notify(nb);
796
  else
Ondřej Zajíček's avatar
Ondřej Zajíček committed
797
    TRACE(D_EVENTS, "Waiting for %I%J to become my neighbor", n->addr, n->iface);
798 799 800
}

static void
801
bfd_stop_neighbor(struct bfd_proto *p UNUSED, struct bfd_neighbor *n)
802
{
803 804 805
  if (n->neigh)
    n->neigh->data = NULL;
  n->neigh = NULL;
806

807 808
  rfree(n->req);
  n->req = NULL;
809 810
}

811 812
static inline int
bfd_same_neighbor(struct bfd_neighbor *x, struct bfd_neighbor *y)
813
{
814 815 816
  return ipa_equal(x->addr, y->addr) && ipa_equal(x->local, y->local) &&
    (x->iface == y->iface) && (x->multihop == y->multihop);
}
817

818 819 820 821 822
static void
bfd_reconfigure_neighbors(struct bfd_proto *p, struct bfd_config *new)
{
  struct bfd_config *old = (struct bfd_config *) (p->p.cf);
  struct bfd_neighbor *on, *nn;
823

824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839
  WALK_LIST(on, old->neigh_list)
  {
    WALK_LIST(nn, new->neigh_list)
      if (bfd_same_neighbor(nn, on))
      {
	nn->neigh = on->neigh;
	if (nn->neigh)
	  nn->neigh->data = nn;

	nn->req = on->req;
	nn->active = 1;
	return;
      }

    bfd_stop_neighbor(p, on);
  }
840

841 842 843
  WALK_LIST(nn, new->neigh_list)
    if (!nn->active)
      bfd_start_neighbor(p, nn);
844 845 846
}


847 848 849 850
/*
 *	BFD notify socket
 */

Ondřej Zajíček's avatar
Ondřej Zajíček committed
851 852 853 854 855 856 857
/* This core notify code should be replaced after main loop transition to birdloop */

int pipe(int pipefd[2]);
void pipe_drain(int fd);
void pipe_kick(int fd);

static int
858
bfd_notify_hook(sock *sk, uint len UNUSED)
Ondřej Zajíček's avatar
Ondřej Zajíček committed
859 860 861 862
{
  struct bfd_proto *p = sk->data;
  struct bfd_session *s;
  list tmp_list;
863 864
  u8 state, diag;
  node *n, *nn;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
865 866 867 868 869 870 871 872 873 874 875 876

  pipe_drain(sk->fd);

  bfd_lock_sessions(p);
  init_list(&tmp_list);
  add_tail_list(&tmp_list, &p->notify_list);
  init_list(&p->notify_list);
  bfd_unlock_sessions(p);

  WALK_LIST_FIRST(s, tmp_list)
  {
    bfd_lock_sessions(p);
877
    rem_node(&s->n);
878 879
    state = s->loc_state;
    diag = s->loc_diag;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
880 881
    bfd_unlock_sessions(p);

882
    /* FIXME: convert to btime and move to bfd_session_update_state() */
883 884 885 886 887 888 889 890 891 892
    s->last_state_change = now;

    s->notify_running = 1;
    WALK_LIST_DELSAFE(n, nn, s->request_list)
      bfd_request_notify(SKIP_BACK(struct bfd_request, n, n), state, diag);
    s->notify_running = 0;

    /* Remove the session if all requests were removed in notify hooks */
    if (EMPTY_LIST(s->request_list))
      bfd_remove_session(p, s);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941
  }

  return 0;
}

static inline void
bfd_notify_kick(struct bfd_proto *p)
{
  pipe_kick(p->notify_ws->fd);
}

static void
bfd_noterr_hook(sock *sk, int err)
{
  struct bfd_proto *p = sk->data;
  log(L_ERR "%s: Notify socket error: %m", p->p.name, err);
}

static void
bfd_notify_init(struct bfd_proto *p)
{
  int pfds[2];
  sock *sk;

  int rv = pipe(pfds);
  if (rv < 0)
    die("pipe: %m");

  sk = sk_new(p->p.pool);
  sk->type = SK_MAGIC;
  sk->rx_hook = bfd_notify_hook;
  sk->err_hook = bfd_noterr_hook;
  sk->fd = pfds[0];
  sk->data = p;
  if (sk_open(sk) < 0)
    die("bfd: sk_open failed");
  p->notify_rs = sk;

  /* The write sock is not added to any event loop */
  sk = sk_new(p->p.pool);
  sk->type = SK_MAGIC;
  sk->fd = pfds[1];
  sk->data = p;
  sk->flags = SKF_THREAD;
  if (sk_open(sk) < 0)
    die("bfd: sk_open failed");
  p->notify_ws = sk;
}

942

943 944 945 946 947 948 949 950 951 952 953
/*
 *	BFD protocol glue
 */

void
bfd_init_all(void)
{
  init_list(&bfd_proto_list);
  init_list(&bfd_wait_list);
}

954 955 956 957 958
static struct proto *
bfd_init(struct proto_config *c)
{
  struct proto *p = proto_new(c, sizeof(struct bfd_proto));

Ondřej Zajíček's avatar
Ondřej Zajíček committed
959
  p->neigh_notify = bfd_neigh_notify;
960 961 962 963 964 965 966 967 968 969

  return p;
}

static int
bfd_start(struct proto *P)
{
  struct bfd_proto *p = (struct bfd_proto *) P;
  struct bfd_config *cf = (struct bfd_config *) (P->cf);

970
  p->loop = birdloop_new();
Ondřej Zajíček's avatar
Ondřej Zajíček committed
971 972 973
  p->tpool = rp_new(NULL, "BFD thread root");
  pthread_spin_init(&p->lock, PTHREAD_PROCESS_PRIVATE);

974
  p->session_slab = sl_new(P->pool, sizeof(struct bfd_session));
975 976
  HASH_INIT(p->session_hash_id, P->pool, 8);
  HASH_INIT(p->session_hash_ip, P->pool, 8);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
977

978
  init_list(&p->iface_list);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
979 980 981 982

  init_list(&p->notify_list);
  bfd_notify_init(p);

983 984
  add_tail(&bfd_proto_list, &p->bfd_node);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
985 986 987 988
  birdloop_enter(p->loop);
  p->rx_1 = bfd_open_rx_sk(p, 0);
  p->rx_m = bfd_open_rx_sk(p, 1);
  birdloop_leave(p->loop);
989

990 991
  bfd_take_requests(p);

992
  struct bfd_neighbor *n;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
993
  WALK_LIST(n, cf->neigh_list)
994 995
    bfd_start_neighbor(p, n);

996
  birdloop_start(p->loop);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
997

998 999 1000 1001 1002 1003 1004 1005
  return PS_UP;
}


static int
bfd_shutdown(struct proto *P)
{
  struct bfd_proto *p = (struct bfd_proto *) P;
1006 1007 1008
  struct bfd_config *cf = (struct bfd_config *) (P->cf);

  rem_node(&p->bfd_node);
1009

1010 1011
  birdloop_stop(p->loop);

1012 1013 1014 1015 1016 1017
  struct bfd_neighbor *n;
  WALK_LIST(n, cf->neigh_list)
    bfd_stop_neighbor(p, n);

  bfd_drop_requests(p);

1018 1019 1020 1021 1022
  /* FIXME: This is hack */
  birdloop_enter(p->loop);
  rfree(p->tpool);
  birdloop_leave(p->loop);

1023
  birdloop_free(p->loop);
1024

1025
  return PS_DOWN;
1026 1027 1028 1029 1030 1031
}

static int
bfd_reconfigure(struct proto *P, struct proto_config *c)
{
  struct bfd_proto *p = (struct bfd_proto *) P;
1032
  // struct bfd_config *old = (struct bfd_config *) (P->cf);
1033
  struct bfd_config *new = (struct bfd_config *) c;
1034
  struct bfd_iface *ifa;
1035

Ondřej Zajíček's avatar
Ondřej Zajíček committed
1036 1037
  birdloop_mask_wakeups(p->loop);

1038 1039 1040 1041 1042 1043 1044 1045 1046
  WALK_LIST(ifa, p->iface_list)
    bfd_reconfigure_iface(p, ifa, new);

  HASH_WALK(p->session_hash_id, next_id, s)
  {
    if (s->ifa->changed)
      bfd_reconfigure_session(p, s);
  }
  HASH_WALK_END;
1047

1048
  bfd_reconfigure_neighbors(p, new);
1049

Ondřej Zajíček's avatar
Ondřej Zajíček committed
1050 1051
  birdloop_unmask_wakeups(p->loop);

1052 1053 1054
  return 1;
}

1055 1056 1057 1058 1059 1060 1061 1062 1063
/* Ensure one instance */
struct bfd_config *bfd_cf;

static void
bfd_preconfig(struct protocol *P UNUSED, struct config *c UNUSED)
{
  bfd_cf = NULL;
}

1064
static void
1065
bfd_copy_config(struct proto_config *dest, struct proto_config *src UNUSED)
1066 1067
{
  struct bfd_config *d = (struct bfd_config *) dest;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1068
  // struct bfd_config *s = (struct bfd_config *) src;
1069

1070
  /* We clean up patt_list and neigh_list, neighbors and ifaces are non-sharable */
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1071
  init_list(&d->patt_list);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1072
  init_list(&d->neigh_list);
1073 1074
}

Ondřej Zajíček's avatar
Ondřej Zajíček committed
1075 1076 1077
void
bfd_show_sessions(struct proto *P)
{
1078
  byte tbuf[TM_DATETIME_BUFFER_SIZE];
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1079
  struct bfd_proto *p = (struct bfd_proto *) P;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1080
  uint state, diag UNUSED;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1081 1082 1083 1084 1085
  u32 tx_int, timeout;
  const char *ifname;

  if (p->p.proto_state != PS_UP)
  {
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1086
    cli_msg(-1020, "%s: is not up", p->p.name);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1087 1088 1089 1090
    cli_msg(0, "");
    return;
  }

Ondřej Zajíček's avatar
Ondřej Zajíček committed
1091 1092
  cli_msg(-1020, "%s:", p->p.name);
  cli_msg(-1020, "%-25s %-10s %-10s %-10s  %8s %8s",
1093
	  "IP address", "Interface", "State", "Since", "Interval", "Timeout");
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1094 1095 1096 1097


  HASH_WALK(p->session_hash_id, next_id, s)
  {
1098
    /* FIXME: this is thread-unsafe, but perhaps harmless */
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1099 1100
    state = s->loc_state;
    diag = s->loc_diag;
1101
    ifname = (s->ifa && s->ifa->iface) ? s->ifa->iface->name : "---";
1102
    tx_int = s->last_tx ? (MAX(s->des_min_tx_int, s->rem_min_rx_int) TO_MS) : 0;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1103 1104
    timeout = (MAX(s->req_min_rx_int, s->rem_min_tx_int) TO_MS) * s->rem_detect_mult;

1105 1106 1107
    state = (state < 4) ? state : 0;
    tm_format_datetime(tbuf, &config->tf_proto, s->last_state_change);

Ondřej Zajíček's avatar
Ondřej Zajíček committed
1108
    cli_msg(-1020, "%-25I %-10s %-10s %-10s  %3u.%03u  %3u.%03u",
1109 1110
	    s->addr, ifname, bfd_state_names[state], tbuf,
	    tx_int / 1000, tx_int % 1000, timeout / 1000, timeout % 1000);
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1111 1112 1113 1114 1115 1116 1117
  }
  HASH_WALK_END;

  cli_msg(0, "");
}


1118 1119 1120
struct protocol proto_bfd = {
  .name =		"BFD",
  .template =		"bfd%d",
1121
  .config_size =	sizeof(struct bfd_config),
1122 1123 1124 1125
  .init =		bfd_init,
  .start =		bfd_start,
  .shutdown =		bfd_shutdown,
  .reconfigure =	bfd_reconfigure,
1126
  .preconfig = 		bfd_preconfig,
1127 1128
  .copy_config =	bfd_copy_config,
};