[mirror_frr.git] / lib / spf_backoff.c

/*
 * This is an implementation of the IETF SPF delay algorithm
 * as explained in draft-ietf-rtgwg-backoff-algo-04
 *
 * Created: 25-01-2017 by S. Litkowski
 *
 * Copyright (C) 2017 Orange Labs http://www.orange.com/
 * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
 *
 * This file is part of FreeRangeRouting (FRR)
 *
 * FRR is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * FRR is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <zebra.h>

#include "spf_backoff.h"

#include "command.h"
#include "memory.h"
#include "thread.h"
#include "vty.h"

DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff")
DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name")

static bool debug_spf_backoff = false;
#define backoff_debug(...) \
  do \
    { \
      if (debug_spf_backoff) \
        zlog_debug(__VA_ARGS__); \
    } \
  while (0)

enum spf_backoff_state {
  SPF_BACKOFF_QUIET,
  SPF_BACKOFF_SHORT_WAIT,
  SPF_BACKOFF_LONG_WAIT
};

struct spf_backoff {
  struct thread_master *m;

  /* Timers as per draft */
  long init_delay;
  long short_delay;
  long long_delay;
  long holddown;
  long timetolearn;

  /* State machine */
  enum spf_backoff_state state;
  struct thread *t_holddown;
  struct thread *t_timetolearn;

  /* For debugging */
  char *name;
  struct timeval first_event_time;
  struct timeval last_event_time;
};

static const char *
spf_backoff_state2str(enum spf_backoff_state state)
{
  switch (state)
    {
    case SPF_BACKOFF_QUIET:
      return "QUIET";
    case SPF_BACKOFF_SHORT_WAIT:
      return "SHORT_WAIT";
    case SPF_BACKOFF_LONG_WAIT:
      return "LONG_WAIT";
    }
  return "???";
}

struct spf_backoff *
spf_backoff_new(struct thread_master *m,
                const char *name,
                long init_delay,
                long short_delay,
                long long_delay,
                long holddown,
                long timetolearn)
{
  struct spf_backoff *rv;

  rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
  rv->m = m;

  rv->init_delay = init_delay;
  rv->short_delay = short_delay;
  rv->long_delay = long_delay;
  rv->holddown = holddown;
  rv->timetolearn = timetolearn;

  rv->state = SPF_BACKOFF_QUIET;

  rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
  return rv;
}

void
spf_backoff_free(struct spf_backoff *backoff)
{
  if (!backoff)
    return;

  THREAD_TIMER_OFF(backoff->t_holddown);
  THREAD_TIMER_OFF(backoff->t_timetolearn);
  XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);

  XFREE(MTYPE_SPF_BACKOFF, backoff);
}

static int
spf_backoff_timetolearn_elapsed(struct thread *thread)
{
  struct spf_backoff *backoff = THREAD_ARG(thread);

  backoff->t_timetolearn = NULL;
  backoff->state = SPF_BACKOFF_LONG_WAIT;
  backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
                backoff->name, spf_backoff_state2str(backoff->state));
  return 0;
}

static int
spf_backoff_holddown_elapsed(struct thread *thread)
{
  struct spf_backoff *backoff = THREAD_ARG(thread);

  backoff->t_holddown = NULL;
  THREAD_TIMER_OFF(backoff->t_timetolearn);
  timerclear(&backoff->first_event_time);
  backoff->state = SPF_BACKOFF_QUIET;
  backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
                backoff->name, spf_backoff_state2str(backoff->state));
  return 0;
}

long spf_backoff_schedule(struct spf_backoff *backoff)
{
  long rv;
  struct timeval now;

  gettimeofday(&now, NULL);

  backoff_debug("SPF Back-off(%s) schedule called in state %s",
                backoff->name, spf_backoff_state2str(backoff->state));

  backoff->last_event_time = now;

  switch (backoff->state)
    {
    case SPF_BACKOFF_QUIET:
      backoff->state = SPF_BACKOFF_SHORT_WAIT;
      thread_add_timer_msec(backoff->m, spf_backoff_timetolearn_elapsed,
                            backoff, backoff->timetolearn,
                            &backoff->t_timetolearn);
      thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
                            backoff->holddown, &backoff->t_holddown);
      backoff->first_event_time = now;
      rv = backoff->init_delay;
      break;
    case SPF_BACKOFF_SHORT_WAIT:
    case SPF_BACKOFF_LONG_WAIT:
      THREAD_TIMER_OFF(backoff->t_holddown);
      thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
                            backoff->holddown, &backoff->t_holddown);
      if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
        rv = backoff->short_delay;
      else
        rv = backoff->long_delay;
      break;
    default:
      zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
      rv = backoff->init_delay;
    }

  backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay",
                backoff->name, spf_backoff_state2str(backoff->state), rv);
  return rv;
}

static const char *
timeval_format(struct timeval *tv)
{
  struct tm tm_store;
  struct tm *tm;
  static char timebuf[256];

  if (!tv->tv_sec && !tv->tv_usec)
    return "(never)";

  tm = localtime_r(&tv->tv_sec, &tm_store);
  if (!tm || strftime(timebuf, sizeof(timebuf),
                      "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0)
    {
      return "???";
    }

  size_t offset = strlen(timebuf);
  snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec);

  return timebuf;
}

void
spf_backoff_show(struct spf_backoff *backoff, struct vty *vty,
                 const char *prefix)
{
  vty_out(vty, "%sCurrent state:     %s%s", prefix,
          spf_backoff_state2str(backoff->state), VTY_NEWLINE);
  vty_out(vty, "%sInit timer:        %ld msec%s", prefix,
          backoff->init_delay, VTY_NEWLINE);
  vty_out(vty, "%sShort timer:       %ld msec%s", prefix,
          backoff->short_delay, VTY_NEWLINE);
  vty_out(vty, "%sLong timer:        %ld msec%s", prefix,
          backoff->long_delay, VTY_NEWLINE);
  vty_out(vty, "%sHolddown timer:    %ld msec%s", prefix,
          backoff->holddown, VTY_NEWLINE);
  if (backoff->t_holddown)
    {
      struct timeval remain = thread_timer_remain(backoff->t_holddown);
      vty_out(vty, "%s                   Still runs for %ld msec%s",
              prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
    }
  else
    {
      vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
    }

  vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix,
          backoff->timetolearn, VTY_NEWLINE);
  if (backoff->t_timetolearn)
    {
      struct timeval remain = thread_timer_remain(backoff->t_timetolearn);
      vty_out(vty, "%s                   Still runs for %ld msec%s",
              prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
    }
  else
    {
      vty_out(vty, "%s                   Inactive%s", prefix, VTY_NEWLINE);
    }

  vty_out(vty, "%sFirst event:       %s%s", prefix,
          timeval_format(&backoff->first_event_time), VTY_NEWLINE);
  vty_out(vty, "%sLast event:        %s%s", prefix,
          timeval_format(&backoff->last_event_time), VTY_NEWLINE);
}

DEFUN(spf_backoff_debug,
      spf_backoff_debug_cmd,
      "debug spf-delay-ietf",
      DEBUG_STR
      "SPF Back-off Debugging\n")
{
  debug_spf_backoff = true;
  return CMD_SUCCESS;
}

DEFUN(no_spf_backoff_debug,
      no_spf_backoff_debug_cmd,
      "no debug spf-delay-ietf",
      NO_STR
      DEBUG_STR
      "SPF Back-off Debugging\n")
{
  debug_spf_backoff = false;
  return CMD_SUCCESS;
}

int
spf_backoff_write_config(struct vty *vty)
{
  int written = 0;

  if (debug_spf_backoff)
    {
      vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE);
      written++;
    }

  return written;
}

void
spf_backoff_cmd_init(void)
{
  install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
  install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
  install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
  install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
}

long
spf_backoff_init_delay(struct spf_backoff *backoff)
{
  return backoff->init_delay;
}

long
spf_backoff_short_delay(struct spf_backoff *backoff)
{
  return backoff->short_delay;
}

long
spf_backoff_long_delay(struct spf_backoff *backoff)
{
  return backoff->long_delay;
}

long
spf_backoff_holddown(struct spf_backoff *backoff)
{
  return backoff->holddown;
}

long
spf_backoff_timetolearn(struct spf_backoff *backoff)
{
  return backoff->timetolearn;
}
Commit	Line	Data
c1d0d21f CF	1	/*
	2	* This is an implementation of the IETF SPF delay algorithm
	3	* as explained in draft-ietf-rtgwg-backoff-algo-04
	4	*
	5	* Created: 25-01-2017 by S. Litkowski
	6	*
	7	* Copyright (C) 2017 Orange Labs http://www.orange.com/
	8	* Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc.
	9	*
	10	* This file is part of FreeRangeRouting (FRR)
	11	*
	12	* FRR is free software; you can redistribute it and/or modify it
	13	* under the terms of the GNU General Public License as published by the
	14	* Free Software Foundation; either version 2, or (at your option) any
	15	* later version.
	16	*
	17	* FRR is distributed in the hope that it will be useful, but
	18	* WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	20	* General Public License for more details.
	21	*
896014f4 DL	22	* You should have received a copy of the GNU General Public License along
	23	* with this program; see the file COPYING; if not, write to the Free Software
	24	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
c1d0d21f CF	25	*/
	26
	27	#include <zebra.h>
	28
	29	#include "spf_backoff.h"
	30
	31	#include "command.h"
	32	#include "memory.h"
	33	#include "thread.h"
	34	#include "vty.h"
	35
	36	DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff")
	37	DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name")
	38
	39	static bool debug_spf_backoff = false;
	40	#define backoff_debug(...) \
	41	do \
	42	{ \
	43	if (debug_spf_backoff) \
	44	zlog_debug(__VA_ARGS__); \
	45	} \
	46	while (0)
	47
	48	enum spf_backoff_state {
	49	SPF_BACKOFF_QUIET,
	50	SPF_BACKOFF_SHORT_WAIT,
	51	SPF_BACKOFF_LONG_WAIT
	52	};
	53
	54	struct spf_backoff {
	55	struct thread_master *m;
	56
	57	/* Timers as per draft */
	58	long init_delay;
	59	long short_delay;
	60	long long_delay;
	61	long holddown;
	62	long timetolearn;
	63
	64	/* State machine */
	65	enum spf_backoff_state state;
	66	struct thread *t_holddown;
	67	struct thread *t_timetolearn;
	68
	69	/* For debugging */
	70	char *name;
	71	struct timeval first_event_time;
	72	struct timeval last_event_time;
	73	};
	74
	75	static const char *
	76	spf_backoff_state2str(enum spf_backoff_state state)
	77	{
	78	switch (state)
	79	{
	80	case SPF_BACKOFF_QUIET:
	81	return "QUIET";
	82	case SPF_BACKOFF_SHORT_WAIT:
	83	return "SHORT_WAIT";
	84	case SPF_BACKOFF_LONG_WAIT:
	85	return "LONG_WAIT";
	86	}
	87	return "???";
	88	}
89
90	struct spf_backoff *
91	spf_backoff_new(struct thread_master *m,
92	const char *name,
93	long init_delay,
94	long short_delay,
95	long long_delay,
96	long holddown,
97	long timetolearn)
98	{
99	struct spf_backoff *rv;
100
101	rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
102	rv->m = m;
103
104	rv->init_delay = init_delay;
105	rv->short_delay = short_delay;
106	rv->long_delay = long_delay;
107	rv->holddown = holddown;
108	rv->timetolearn = timetolearn;
109
110	rv->state = SPF_BACKOFF_QUIET;
111
112	rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
113	return rv;
114	}
115
116	void
117	spf_backoff_free(struct spf_backoff *backoff)
118	{
119	if (!backoff)
120	return;
121
122	THREAD_TIMER_OFF(backoff->t_holddown);
123	THREAD_TIMER_OFF(backoff->t_timetolearn);
124	XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
125
126	XFREE(MTYPE_SPF_BACKOFF, backoff);
127	}
128
129	static int
130	spf_backoff_timetolearn_elapsed(struct thread *thread)
131	{
132	struct spf_backoff *backoff = THREAD_ARG(thread);
133
134	backoff->t_timetolearn = NULL;
135	backoff->state = SPF_BACKOFF_LONG_WAIT;
136	backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
137	backoff->name, spf_backoff_state2str(backoff->state));
138	return 0;
139	}
140
141	static int
142	spf_backoff_holddown_elapsed(struct thread *thread)
143	{
144	struct spf_backoff *backoff = THREAD_ARG(thread);
145
146	backoff->t_holddown = NULL;
147	THREAD_TIMER_OFF(backoff->t_timetolearn);
148	timerclear(&backoff->first_event_time);
149	backoff->state = SPF_BACKOFF_QUIET;
150	backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
151	backoff->name, spf_backoff_state2str(backoff->state));
152	return 0;
153	}
154
155	long spf_backoff_schedule(struct spf_backoff *backoff)
156	{
157	long rv;
158	struct timeval now;
159
160	gettimeofday(&now, NULL);
161
162	backoff_debug("SPF Back-off(%s) schedule called in state %s",
163	backoff->name, spf_backoff_state2str(backoff->state));
164
165	backoff->last_event_time = now;
166
167	switch (backoff->state)
168	{
169	case SPF_BACKOFF_QUIET:
170	backoff->state = SPF_BACKOFF_SHORT_WAIT;
ffa2c898 QY	171	thread_add_timer_msec(backoff->m, spf_backoff_timetolearn_elapsed,
	172	backoff, backoff->timetolearn,
	173	&backoff->t_timetolearn);
	174	thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
	175	backoff->holddown, &backoff->t_holddown);
c1d0d21f CF	176	backoff->first_event_time = now;
	177	rv = backoff->init_delay;
	178	break;
	179	case SPF_BACKOFF_SHORT_WAIT:
	180	case SPF_BACKOFF_LONG_WAIT:
	181	THREAD_TIMER_OFF(backoff->t_holddown);
ffa2c898 QY	182	thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff,
ffa2c898 QY	183	backoff->holddown, &backoff->t_holddown);
c1d0d21f CF	184	if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
	185	rv = backoff->short_delay;
	186	else
	187	rv = backoff->long_delay;
	188	break;
	189	default:
	190	zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
	191	rv = backoff->init_delay;
	192	}
	193
	194	backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay",
	195	backoff->name, spf_backoff_state2str(backoff->state), rv);
	196	return rv;
	197	}
	198
	199	static const char *
	200	timeval_format(struct timeval *tv)
	201	{
	202	struct tm tm_store;
	203	struct tm *tm;
	204	static char timebuf[256];
	205
	206	if (!tv->tv_sec && !tv->tv_usec)
	207	return "(never)";
	208
	209	tm = localtime_r(&tv->tv_sec, &tm_store);
	210	if (!tm \|\| strftime(timebuf, sizeof(timebuf),
	211	"%Z %a %Y-%m-%d %H:%M:%S", tm) == 0)
	212	{
	213	return "???";
	214	}
	215
	216	size_t offset = strlen(timebuf);
	217	snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec);
	218
	219	return timebuf;
	220	}
	221
	222	void
	223	spf_backoff_show(struct spf_backoff backoff, struct vty vty,
	224	const char *prefix)
	225	{
	226	vty_out(vty, "%sCurrent state: %s%s", prefix,
	227	spf_backoff_state2str(backoff->state), VTY_NEWLINE);
	228	vty_out(vty, "%sInit timer: %ld msec%s", prefix,
	229	backoff->init_delay, VTY_NEWLINE);
	230	vty_out(vty, "%sShort timer: %ld msec%s", prefix,
	231	backoff->short_delay, VTY_NEWLINE);
	232	vty_out(vty, "%sLong timer: %ld msec%s", prefix,
	233	backoff->long_delay, VTY_NEWLINE);
	234	vty_out(vty, "%sHolddown timer: %ld msec%s", prefix,
	235	backoff->holddown, VTY_NEWLINE);
	236	if (backoff->t_holddown)
	237	{
	238	struct timeval remain = thread_timer_remain(backoff->t_holddown);
	239	vty_out(vty, "%s Still runs for %ld msec%s",
	240	prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
	241	}
	242	else
	243	{
	244	vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE);
	245	}
	246
	247	vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix,
248	backoff->timetolearn, VTY_NEWLINE);
249	if (backoff->t_timetolearn)
250	{
251	struct timeval remain = thread_timer_remain(backoff->t_timetolearn);
252	vty_out(vty, "%s Still runs for %ld msec%s",
253	prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE);
254	}
255	else
256	{
257	vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE);
258	}
259
260	vty_out(vty, "%sFirst event: %s%s", prefix,
261	timeval_format(&backoff->first_event_time), VTY_NEWLINE);
262	vty_out(vty, "%sLast event: %s%s", prefix,
263	timeval_format(&backoff->last_event_time), VTY_NEWLINE);
264	}
265
266	DEFUN(spf_backoff_debug,
267	spf_backoff_debug_cmd,
268	"debug spf-delay-ietf",
269	DEBUG_STR
270	"SPF Back-off Debugging\n")
271	{
272	debug_spf_backoff = true;
273	return CMD_SUCCESS;
274	}
275
276	DEFUN(no_spf_backoff_debug,
277	no_spf_backoff_debug_cmd,
278	"no debug spf-delay-ietf",
279	NO_STR
280	DEBUG_STR
281	"SPF Back-off Debugging\n")
282	{
283	debug_spf_backoff = false;
284	return CMD_SUCCESS;
285	}
286
287	int
288	spf_backoff_write_config(struct vty *vty)
289	{
290	int written = 0;
291
292	if (debug_spf_backoff)
293	{
294	vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE);
295	written++;
296	}
297
298	return written;
299	}
300
301	void
302	spf_backoff_cmd_init(void)
303	{
304	install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
305	install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
306	install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
307	install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
308	}
309
310	long
311	spf_backoff_init_delay(struct spf_backoff *backoff)
312	{
313	return backoff->init_delay;
314	}
315
316	long
317	spf_backoff_short_delay(struct spf_backoff *backoff)
318	{
319	return backoff->short_delay;
320	}
321
322	long
323	spf_backoff_long_delay(struct spf_backoff *backoff)
324	{
325	return backoff->long_delay;
326	}
327
328	long
329	spf_backoff_holddown(struct spf_backoff *backoff)
330	{
331	return backoff->holddown;
332	}
333
334	long
335	spf_backoff_timetolearn(struct spf_backoff *backoff)
336	{
337	return backoff->timetolearn;
338	}