[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 = 0;
	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;
	}

	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	{
496764bb	146	long rv = 0;
d62a17ae	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;
d62a17ae	179	}
	180
	181	backoff_debug(
	182	"SPF Back-off(%s) changed state to %s and returned %ld delay",
	183	backoff->name, spf_backoff_state2str(backoff->state), rv);
	184	return rv;
c1d0d21f CF	185	}
c1d0d21f CF	186
d62a17ae	187	static const char timeval_format(struct timeval tv)
c1d0d21f	188	{
d62a17ae	189	struct tm tm_store;
	190	struct tm *tm;
	191	static char timebuf[256];
c1d0d21f	192
d62a17ae	193	if (!tv->tv_sec && !tv->tv_usec)
d62a17ae	194	return "(never)";
c1d0d21f	195
d62a17ae	196	tm = localtime_r(&tv->tv_sec, &tm_store);
	197	if (!tm
	198	\|\| strftime(timebuf, sizeof(timebuf), "%Z %a %Y-%m-%d %H:%M:%S", tm)
	199	== 0) {
	200	return "???";
	201	}
c1d0d21f	202
d62a17ae	203	size_t offset = strlen(timebuf);
d62a17ae	204	snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld",
a37bd5e0	205	(long int)tv->tv_usec);
c1d0d21f	206
d62a17ae	207	return timebuf;
c1d0d21f CF	208	}
c1d0d21f CF	209
d62a17ae	210	void spf_backoff_show(struct spf_backoff backoff, struct vty vty,
d62a17ae	211	const char *prefix)
c1d0d21f	212	{
d62a17ae	213	vty_out(vty, "%sCurrent state: %s\n", prefix,
	214	spf_backoff_state2str(backoff->state));
	215	vty_out(vty, "%sInit timer: %ld msec\n", prefix,
	216	backoff->init_delay);
	217	vty_out(vty, "%sShort timer: %ld msec\n", prefix,
	218	backoff->short_delay);
	219	vty_out(vty, "%sLong timer: %ld msec\n", prefix,
	220	backoff->long_delay);
	221	vty_out(vty, "%sHolddown timer: %ld msec\n", prefix,
	222	backoff->holddown);
	223	if (backoff->t_holddown) {
	224	struct timeval remain =
	225	thread_timer_remain(backoff->t_holddown);
a97986ff	226	vty_out(vty, "%s Still runs for %lld msec\n",
996c9314 LB	227	prefix,
996c9314 LB	228	(long long)remain.tv_sec * 1000
a97986ff	229	+ remain.tv_usec / 1000);
d62a17ae	230	} else {
	231	vty_out(vty, "%s Inactive\n", prefix);
	232	}
	233
	234	vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix,
	235	backoff->timetolearn);
	236	if (backoff->t_timetolearn) {
	237	struct timeval remain =
	238	thread_timer_remain(backoff->t_timetolearn);
a97986ff	239	vty_out(vty, "%s Still runs for %lld msec\n",
996c9314 LB	240	prefix,
996c9314 LB	241	(long long)remain.tv_sec * 1000
a97986ff	242	+ remain.tv_usec / 1000);
d62a17ae	243	} else {
	244	vty_out(vty, "%s Inactive\n", prefix);
	245	}
	246
	247	vty_out(vty, "%sFirst event: %s\n", prefix,
	248	timeval_format(&backoff->first_event_time));
	249	vty_out(vty, "%sLast event: %s\n", prefix,
	250	timeval_format(&backoff->last_event_time));
c1d0d21f CF	251	}
	252
	253	DEFUN(spf_backoff_debug,
	254	spf_backoff_debug_cmd,
	255	"debug spf-delay-ietf",
	256	DEBUG_STR
	257	"SPF Back-off Debugging\n")
	258	{
d62a17ae	259	debug_spf_backoff = true;
d62a17ae	260	return CMD_SUCCESS;
c1d0d21f CF	261	}
	262
	263	DEFUN(no_spf_backoff_debug,
	264	no_spf_backoff_debug_cmd,
	265	"no debug spf-delay-ietf",
	266	NO_STR
	267	DEBUG_STR
	268	"SPF Back-off Debugging\n")
	269	{
d62a17ae	270	debug_spf_backoff = false;
d62a17ae	271	return CMD_SUCCESS;
c1d0d21f CF	272	}
c1d0d21f CF	273
d62a17ae	274	int spf_backoff_write_config(struct vty *vty)
c1d0d21f	275	{
d62a17ae	276	int written = 0;
c1d0d21f	277
d62a17ae	278	if (debug_spf_backoff) {
	279	vty_out(vty, "debug spf-delay-ietf\n");
	280	written++;
	281	}
c1d0d21f	282
d62a17ae	283	return written;
c1d0d21f CF	284	}
c1d0d21f CF	285
d62a17ae	286	void spf_backoff_cmd_init(void)
c1d0d21f	287	{
d62a17ae	288	install_element(ENABLE_NODE, &spf_backoff_debug_cmd);
	289	install_element(CONFIG_NODE, &spf_backoff_debug_cmd);
	290	install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd);
	291	install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd);
c1d0d21f CF	292	}
c1d0d21f CF	293
d62a17ae	294	long spf_backoff_init_delay(struct spf_backoff *backoff)
c1d0d21f	295	{
d62a17ae	296	return backoff->init_delay;
c1d0d21f CF	297	}
c1d0d21f CF	298
d62a17ae	299	long spf_backoff_short_delay(struct spf_backoff *backoff)
c1d0d21f	300	{
d62a17ae	301	return backoff->short_delay;
c1d0d21f CF	302	}
c1d0d21f CF	303
d62a17ae	304	long spf_backoff_long_delay(struct spf_backoff *backoff)
c1d0d21f	305	{
d62a17ae	306	return backoff->long_delay;
c1d0d21f CF	307	}
c1d0d21f CF	308
d62a17ae	309	long spf_backoff_holddown(struct spf_backoff *backoff)
c1d0d21f	310	{
d62a17ae	311	return backoff->holddown;
c1d0d21f CF	312	}
c1d0d21f CF	313
d62a17ae	314	long spf_backoff_timetolearn(struct spf_backoff *backoff)
c1d0d21f	315	{
d62a17ae	316	return backoff->timetolearn;
c1d0d21f	317	}