Merge pull request #11722 from donaldsharp/qdb

[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 FRRouting (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_cancel(&backoff->t_holddown);
	thread_cancel(&backoff->t_timetolearn);
	XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name);

	XFREE(MTYPE_SPF_BACKOFF, backoff);
}

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

	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));
}

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

	THREAD_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));
}

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_cancel(&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;
}