[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",
		 (long int)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\n", prefix,
		spf_backoff_state2str(backoff->state));
	vty_out(vty, "%sInit timer:        %ld msec\n", prefix,
		backoff->init_delay);
	vty_out(vty, "%sShort timer:       %ld msec\n", prefix,
		backoff->short_delay);
	vty_out(vty, "%sLong timer:        %ld msec\n", prefix,
		backoff->long_delay);
	vty_out(vty, "%sHolddown timer:    %ld msec\n", prefix,
		backoff->holddown);
	if (backoff->t_holddown) {
		struct timeval remain =
			thread_timer_remain(backoff->t_holddown);
		vty_out(vty, "%s                   Still runs for %lld msec\n",
			prefix,
			(long long)remain.tv_sec * 1000
				+ remain.tv_usec / 1000);
	} else {
		vty_out(vty, "%s                   Inactive\n", prefix);
	}

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

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

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\n");
		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;
d62a17ae	40	#define backoff_debug(...) \
	41	do { \
	42	if (debug_spf_backoff) \
	43	zlog_debug(__VA_ARGS__); \
	44	} while (0)
c1d0d21f CF	45
c1d0d21f CF	46	enum spf_backoff_state {
d62a17ae	47	SPF_BACKOFF_QUIET,
	48	SPF_BACKOFF_SHORT_WAIT,
	49	SPF_BACKOFF_LONG_WAIT
c1d0d21f CF	50	};
	51
	52	struct spf_backoff {
d62a17ae	53	struct thread_master *m;
	54
	55	/* Timers as per draft */
	56	long init_delay;
	57	long short_delay;
	58	long long_delay;
	59	long holddown;
	60	long timetolearn;
	61
	62	/* State machine */
	63	enum spf_backoff_state state;
	64	struct thread *t_holddown;
	65	struct thread *t_timetolearn;
	66
	67	/* For debugging */
	68	char *name;
	69	struct timeval first_event_time;
	70	struct timeval last_event_time;
c1d0d21f CF	71	};
c1d0d21f CF	72
d62a17ae	73	static const char *spf_backoff_state2str(enum spf_backoff_state state)
c1d0d21f	74	{
d62a17ae	75	switch (state) {
	76	case SPF_BACKOFF_QUIET:
	77	return "QUIET";
	78	case SPF_BACKOFF_SHORT_WAIT:
	79	return "SHORT_WAIT";
	80	case SPF_BACKOFF_LONG_WAIT:
	81	return "LONG_WAIT";
	82	}
	83	return "???";
c1d0d21f CF	84	}
c1d0d21f CF	85
d62a17ae	86	struct spf_backoff spf_backoff_new(struct thread_master m, const char *name,
	87	long init_delay, long short_delay,
	88	long long_delay, long holddown,
	89	long timetolearn)
c1d0d21f	90	{
d62a17ae	91	struct spf_backoff *rv;
c1d0d21f	92
d62a17ae	93	rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv));
d62a17ae	94	rv->m = m;
c1d0d21f	95
d62a17ae	96	rv->init_delay = init_delay;
	97	rv->short_delay = short_delay;
	98	rv->long_delay = long_delay;
	99	rv->holddown = holddown;
	100	rv->timetolearn = timetolearn;
c1d0d21f	101
d62a17ae	102	rv->state = SPF_BACKOFF_QUIET;
c1d0d21f	103
d62a17ae	104	rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name);
d62a17ae	105	return rv;
c1d0d21f CF	106	}
c1d0d21f CF	107
d62a17ae	108	void spf_backoff_free(struct spf_backoff *backoff)
c1d0d21f	109	{
d62a17ae	110	if (!backoff)
d62a17ae	111	return;
c1d0d21f	112
d62a17ae	113	THREAD_TIMER_OFF(backoff->t_holddown);
	114	THREAD_TIMER_OFF(backoff->t_timetolearn);
	115	XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);
c1d0d21f	116
d62a17ae	117	XFREE(MTYPE_SPF_BACKOFF, backoff);
c1d0d21f CF	118	}
c1d0d21f CF	119
d62a17ae	120	static int spf_backoff_timetolearn_elapsed(struct thread *thread)
c1d0d21f	121	{
d62a17ae	122	struct spf_backoff *backoff = THREAD_ARG(thread);
c1d0d21f	123
d62a17ae	124	backoff->t_timetolearn = NULL;
	125	backoff->state = SPF_BACKOFF_LONG_WAIT;
	126	backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s",
	127	backoff->name, spf_backoff_state2str(backoff->state));
	128	return 0;
c1d0d21f CF	129	}
c1d0d21f CF	130
d62a17ae	131	static int spf_backoff_holddown_elapsed(struct thread *thread)
c1d0d21f	132	{
d62a17ae	133	struct spf_backoff *backoff = THREAD_ARG(thread);
	134
	135	backoff->t_holddown = NULL;
	136	THREAD_TIMER_OFF(backoff->t_timetolearn);
	137	timerclear(&backoff->first_event_time);
	138	backoff->state = SPF_BACKOFF_QUIET;
	139	backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s",
	140	backoff->name, spf_backoff_state2str(backoff->state));
	141	return 0;
c1d0d21f CF	142	}
	143
	144	long spf_backoff_schedule(struct spf_backoff *backoff)
	145	{
d62a17ae	146	long rv;
	147	struct timeval now;
	148
	149	gettimeofday(&now, NULL);
	150
	151	backoff_debug("SPF Back-off(%s) schedule called in state %s",
	152	backoff->name, spf_backoff_state2str(backoff->state));
	153
	154	backoff->last_event_time = now;
	155
	156	switch (backoff->state) {
	157	case SPF_BACKOFF_QUIET:
	158	backoff->state = SPF_BACKOFF_SHORT_WAIT;
	159	thread_add_timer_msec(
	160	backoff->m, spf_backoff_timetolearn_elapsed, backoff,
	161	backoff->timetolearn, &backoff->t_timetolearn);
	162	thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
	163	backoff, backoff->holddown,
	164	&backoff->t_holddown);
	165	backoff->first_event_time = now;
	166	rv = backoff->init_delay;
	167	break;
	168	case SPF_BACKOFF_SHORT_WAIT:
	169	case SPF_BACKOFF_LONG_WAIT:
	170	THREAD_TIMER_OFF(backoff->t_holddown);
	171	thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed,
	172	backoff, backoff->holddown,
	173	&backoff->t_holddown);
	174	if (backoff->state == SPF_BACKOFF_SHORT_WAIT)
	175	rv = backoff->short_delay;
	176	else
	177	rv = backoff->long_delay;
	178	break;
	179	default:
	180	zlog_warn("SPF Back-off(%s) in unknown state", backoff->name);
	181	rv = backoff->init_delay;
	182	}
	183
	184	backoff_debug(
	185	"SPF Back-off(%s) changed state to %s and returned %ld delay",
	186	backoff->name, spf_backoff_state2str(backoff->state), rv);
	187	return rv;
c1d0d21f CF	188	}
c1d0d21f CF	189
d62a17ae	190	static const char timeval_format(struct timeval tv)
c1d0d21f	191	{
d62a17ae	192	struct tm tm_store;
	193	struct tm *tm;
	194	static char timebuf[256];
c1d0d21f	195
d62a17ae	196	if (!tv->tv_sec && !tv->tv_usec)
d62a17ae	197	return "(never)";
c1d0d21f	198
d62a17ae	199	tm = localtime_r(&tv->tv_sec, &tm_store);
	200	if (!tm
	201	\|\| strftime(timebuf, sizeof(timebuf), "%Z %a %Y-%m-%d %H:%M:%S", tm)
	202	== 0) {
	203	return "???";
	204	}
c1d0d21f	205
d62a17ae	206	size_t offset = strlen(timebuf);
d62a17ae	207	snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld",
a37bd5e0	208	(long int)tv->tv_usec);
c1d0d21f	209
d62a17ae	210	return timebuf;
c1d0d21f CF	211	}
c1d0d21f CF	212
d62a17ae	213	void spf_backoff_show(struct spf_backoff backoff, struct vty vty,
d62a17ae	214	const char *prefix)
c1d0d21f	215	{
d62a17ae	216	vty_out(vty, "%sCurrent state: %s\n", prefix,
	217	spf_backoff_state2str(backoff->state));
	218	vty_out(vty, "%sInit timer: %ld msec\n", prefix,
	219	backoff->init_delay);
	220	vty_out(vty, "%sShort timer: %ld msec\n", prefix,
	221	backoff->short_delay);
	222	vty_out(vty, "%sLong timer: %ld msec\n", prefix,
	223	backoff->long_delay);
	224	vty_out(vty, "%sHolddown timer: %ld msec\n", prefix,
	225	backoff->holddown);
	226	if (backoff->t_holddown) {
	227	struct timeval remain =
	228	thread_timer_remain(backoff->t_holddown);
a97986ff	229	vty_out(vty, "%s Still runs for %lld msec\n",
996c9314 LB	230	prefix,
996c9314 LB	231	(long long)remain.tv_sec * 1000
a97986ff	232	+ remain.tv_usec / 1000);
d62a17ae	233	} else {
	234	vty_out(vty, "%s Inactive\n", prefix);
	235	}
	236
	237	vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix,
	238	backoff->timetolearn);
	239	if (backoff->t_timetolearn) {
	240	struct timeval remain =
	241	thread_timer_remain(backoff->t_timetolearn);
a97986ff	242	vty_out(vty, "%s Still runs for %lld msec\n",
996c9314 LB	243	prefix,
996c9314 LB	244	(long long)remain.tv_sec * 1000
a97986ff	245	+ remain.tv_usec / 1000);
d62a17ae	246	} else {
	247	vty_out(vty, "%s Inactive\n", prefix);
	248	}
	249
	250	vty_out(vty, "%sFirst event: %s\n", prefix,
	251	timeval_format(&backoff->first_event_time));
	252	vty_out(vty, "%sLast event: %s\n", prefix,
	253	timeval_format(&backoff->last_event_time));
c1d0d21f CF	254	}
	255
	256	DEFUN(spf_backoff_debug,
	257	spf_backoff_debug_cmd,
	258	"debug spf-delay-ietf",
	259	DEBUG_STR
	260	"SPF Back-off Debugging\n")
	261	{
d62a17ae	262	debug_spf_backoff = true;
d62a17ae	263	return CMD_SUCCESS;
c1d0d21f CF	264	}
	265
	266	DEFUN(no_spf_backoff_debug,
	267	no_spf_backoff_debug_cmd,
	268	"no debug spf-delay-ietf",
	269	NO_STR
	270	DEBUG_STR
	271	"SPF Back-off Debugging\n")
	272	{
d62a17ae	273	debug_spf_backoff = false;
d62a17ae	274	return CMD_SUCCESS;
c1d0d21f CF	275	}
c1d0d21f CF	276
d62a17ae	277	int spf_backoff_write_config(struct vty *vty)
c1d0d21f	278	{
d62a17ae	279	int written = 0;
c1d0d21f	280
d62a17ae	281	if (debug_spf_backoff) {
	282	vty_out(vty, "debug spf-delay-ietf\n");
	283	written++;
	284	}
c1d0d21f	285
d62a17ae	286	return written;
c1d0d21f CF	287	}
c1d0d21f CF	288
d62a17ae	289	void spf_backoff_cmd_init(void)
c1d0d21f	290	{
d62a17ae	291	install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
	292	install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
	293	install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
	294	install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
c1d0d21f CF	295	}
c1d0d21f CF	296
d62a17ae	297	long spf_backoff_init_delay(struct spf_backoff *backoff)
c1d0d21f	298	{
d62a17ae	299	return backoff->init_delay;
c1d0d21f CF	300	}
c1d0d21f CF	301
d62a17ae	302	long spf_backoff_short_delay(struct spf_backoff *backoff)
c1d0d21f	303	{
d62a17ae	304	return backoff->short_delay;
c1d0d21f CF	305	}
c1d0d21f CF	306
d62a17ae	307	long spf_backoff_long_delay(struct spf_backoff *backoff)
c1d0d21f	308	{
d62a17ae	309	return backoff->long_delay;
c1d0d21f CF	310	}
c1d0d21f CF	311
d62a17ae	312	long spf_backoff_holddown(struct spf_backoff *backoff)
c1d0d21f	313	{
d62a17ae	314	return backoff->holddown;
c1d0d21f CF	315	}
c1d0d21f CF	316
d62a17ae	317	long spf_backoff_timetolearn(struct spf_backoff *backoff)
c1d0d21f	318	{
d62a17ae	319	return backoff->timetolearn;
c1d0d21f	320	}