/**
|
* \addtogroup trickle-timer
|
* @{
|
*/
|
|
/**
|
* \file
|
* Trickle timer library implementation.
|
* \author
|
* George Oikonomou - <oikonomou@users.sourceforge.net>
|
*/
|
|
/*
|
* Copyright (c) 2012, George Oikonomou - <oikonomou@users.sourceforge.net>
|
* All rights reserved.
|
*
|
* Redistribution and use in source and binary forms, with or without
|
* modification, are permitted provided that the following conditions
|
* are met:
|
*
|
* 1. Redistributions of source code must retain the above copyright
|
* notice, this list of conditions and the following disclaimer.
|
* 2. Redistributions in binary form must reproduce the above copyright
|
* notice, this list of conditions and the following disclaimer in the
|
* documentation and/or other materials provided with the distribution.
|
* 3. Neither the name of the copyright holder nor the names of its
|
* contributors may be used to endorse or promote products derived
|
* from this software without specific prior written permission.
|
*
|
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
|
* COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
|
* OF THE POSSIBILITY OF SUCH DAMAGE.
|
*/
|
#include "contiki-conf.h"
|
#include "lib/trickle-timer.h"
|
#include "sys/ctimer.h"
|
#include "sys/cc.h"
|
#include "lib/random.h"
|
/*---------------------------------------------------------------------------*/
|
#define DEBUG 0
|
|
#if DEBUG
|
#include <stdio.h>
|
#define PRINTF(...) printf(__VA_ARGS__)
|
#else
|
#define PRINTF(...)
|
#endif
|
/*---------------------------------------------------------------------------*/
|
/**
|
* \brief Wide randoms for platforms using a 4-byte wide clock
|
* (see ::TRICKLE_TIMER_WIDE_RAND)
|
*/
|
#if TRICKLE_TIMER_WIDE_RAND
|
#define tt_rand() wide_rand()
|
#else
|
#define tt_rand() random_rand()
|
#endif
|
/*---------------------------------------------------------------------------*/
|
/* Declarations of variables of local interest */
|
/*---------------------------------------------------------------------------*/
|
static struct trickle_timer *loctt; /* Pointer to a struct for local use */
|
static clock_time_t loc_clock; /* A local, general-purpose placeholder */
|
|
static void fire(void *ptr);
|
static void double_interval(void *ptr);
|
/*---------------------------------------------------------------------------*/
|
/* Local utilities and functions to be used as ctimer callbacks */
|
/*---------------------------------------------------------------------------*/
|
#if TRICKLE_TIMER_WIDE_RAND
|
/* Returns a 4-byte wide, unsigned random number */
|
static uint32_t
|
wide_rand()
|
{
|
return ((uint32_t)random_rand() << 16 | random_rand());
|
}
|
#endif
|
/*---------------------------------------------------------------------------*/
|
/*
|
* Returns the maximum sane Imax value for a given Imin
|
*
|
* This function is a variant of a fairly standard 'Count Leading Zeros'. It
|
* has three flavours. The most suitable one for a specific platform can be
|
* configured by changing the value of TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH
|
* in the platform's contiki-conf.h
|
*/
|
#if TRICKLE_TIMER_ERROR_CHECKING
|
static uint8_t
|
max_imax(clock_time_t value)
|
{
|
uint8_t zeros = 0;
|
#if (TRICKLE_TIMER_MAX_IMAX_WIDTH==TRICKLE_TIMER_MAX_IMAX_GENERIC)
|
uint8_t i;
|
clock_time_t mask = 0xFFFF;
|
|
value--;
|
|
for(i = sizeof(clock_time_t) << 2; i > 0; i >>= 1) {
|
if((value & (mask <<= i)) == 0) {
|
zeros += i;
|
value <<= i;
|
}
|
}
|
|
#elif (TRICKLE_TIMER_MAX_IMAX_WIDTH==TRICKLE_TIMER_MAX_IMAX_16_BIT)
|
if((value & 0xFF00) == 0) {
|
zeros += 8;
|
value <<= 8;
|
}
|
if((value & 0xF000) == 0) {
|
zeros += 4;
|
value <<= 4;
|
}
|
if((value & 0xC000) == 0) {
|
zeros += 2;
|
value <<= 2;
|
}
|
if((value & 0x8000) == 0) {
|
zeros++;
|
}
|
#elif (TRICKLE_TIMER_MAX_IMAX_WIDTH==TRICKLE_TIMER_MAX_IMAX_32_BIT)
|
if((value & 0xFFFF0000) == 0) {
|
zeros += 16;
|
value <<= 16;
|
}
|
if((value & 0xFF000000) == 0) {
|
zeros += 8;
|
value <<= 8;
|
}
|
if((value & 0xF0000000) == 0) {
|
zeros += 4;
|
value <<= 4;
|
}
|
if((value & 0xC0000000) == 0) {
|
zeros += 2;
|
value <<= 2;
|
}
|
if((value & 0x80000000) == 0) {
|
zeros += 1;
|
}
|
#endif
|
|
return zeros - 1; /* Always non-negative due to the range of 'value' */
|
}
|
#endif /* TRICKLE_TIMER_ERROR_CHECKING */
|
/*---------------------------------------------------------------------------*/
|
/* Returns a random time point t in [I/2 , I) */
|
static clock_time_t
|
get_t(clock_time_t i_cur)
|
{
|
i_cur >>= 1;
|
|
PRINTF("trickle_timer get t: [%lu, %lu)\n", (unsigned long)i_cur,
|
(unsigned long)(i_cur << 1));
|
|
return i_cur + (tt_rand() % i_cur);
|
}
|
/*---------------------------------------------------------------------------*/
|
static void
|
schedule_for_end(struct trickle_timer *tt)
|
{
|
/* Reset our ctimer, schedule interval_end to run at time I */
|
clock_time_t now = clock_time();
|
|
loc_clock = TRICKLE_TIMER_INTERVAL_END(tt) - now;
|
|
PRINTF("trickle_timer sched for end: at %lu, end in %ld\n",
|
(unsigned long)clock_time(), (signed long)loc_clock);
|
|
/* Interval's end will happen in loc_clock ticks. Make sure this isn't in
|
* the past... */
|
if(loc_clock > (TRICKLE_TIMER_CLOCK_MAX >> 1)) {
|
loc_clock = 0; /* Interval ended in the past, schedule for in 0 */
|
PRINTF("trickle_timer doubling: Was in the past. Compensating\n");
|
}
|
|
ctimer_set(&tt->ct, loc_clock, double_interval, tt);
|
}
|
/*---------------------------------------------------------------------------*/
|
/* This is used as a ctimer callback, thus its argument must be void *. ptr is
|
* a pointer to the struct trickle_timer that fired */
|
static void
|
double_interval(void *ptr)
|
{
|
clock_time_t last_end;
|
|
/* 'cast' ptr to a struct trickle_timer */
|
loctt = (struct trickle_timer *)ptr;
|
|
loctt->c = 0;
|
|
PRINTF("trickle_timer doubling: at %lu, (was for %lu), ",
|
(unsigned long)clock_time(),
|
(unsigned long)TRICKLE_TIMER_INTERVAL_END(loctt));
|
|
/* Remember the previous interval's end (absolute time), before we double */
|
last_end = TRICKLE_TIMER_INTERVAL_END(loctt);
|
|
/* Double the interval if we have to */
|
if(loctt->i_cur <= TRICKLE_TIMER_INTERVAL_MAX(loctt) >> 1) {
|
/* If I <= Imax/2, we double */
|
loctt->i_cur <<= 1;
|
PRINTF("I << 1 = %lu\n", (unsigned long)loctt->i_cur);
|
} else {
|
/* We may have I > Imax/2 but I <> Imax, in which case we set to Imax
|
* This will happen when I didn't start as Imin (before the first reset) */
|
loctt->i_cur = TRICKLE_TIMER_INTERVAL_MAX(loctt);
|
PRINTF("I = Imax = %lu\n", (unsigned long)loctt->i_cur);
|
}
|
|
/* Random t in [I/2, I) */
|
loc_clock = get_t(loctt->i_cur);
|
|
PRINTF("trickle_timer doubling: t=%lu\n", (unsigned long)loc_clock);
|
|
#if TRICKLE_TIMER_COMPENSATE_DRIFT
|
/* Schedule for t ticks after the previous interval's end, not after now. If
|
* that is in the past, schedule in 0 */
|
loc_clock = (last_end + loc_clock) - clock_time();
|
PRINTF("trickle_timer doubling: at %lu, in %ld ticks\n",
|
(unsigned long)clock_time(), (signed long)loc_clock);
|
if(loc_clock > (TRICKLE_TIMER_CLOCK_MAX >> 1)) {
|
/* Oops, that's in the past */
|
loc_clock = 0;
|
PRINTF("trickle_timer doubling: Was in the past. Compensating\n");
|
}
|
ctimer_set(&loctt->ct, loc_clock, fire, loctt);
|
|
/* Store the actual interval start (absolute time), we need it later.
|
* We pretend that it started at the same time when the last one ended */
|
loctt->i_start = last_end;
|
#else
|
/* Assumed that the previous interval's end is 'now' and schedule in t ticks
|
* after 'now', ignoring potential offsets */
|
ctimer_set(&loctt->ct, loc_clock, fire, loctt);
|
/* Store the actual interval start (absolute time), we need it later */
|
loctt->i_start = loctt->ct.etimer.timer.start;
|
#endif
|
|
PRINTF("trickle_timer doubling: Last end %lu, new end %lu, for %lu, I=%lu\n",
|
(unsigned long)last_end,
|
(unsigned long)TRICKLE_TIMER_INTERVAL_END(loctt),
|
(unsigned long)(loctt->ct.etimer.timer.start +
|
loctt->ct.etimer.timer.interval),
|
(unsigned long)(loctt->i_cur));
|
}
|
/*---------------------------------------------------------------------------*/
|
/* Called by the ctimer module at time t within the current interval. ptr is
|
* a pointer to the struct trickle_timer of interest */
|
static void
|
fire(void *ptr)
|
{
|
/* 'cast' c to a struct trickle_timer */
|
loctt = (struct trickle_timer *)ptr;
|
|
PRINTF("trickle_timer fire: at %lu (was for %lu)\n",
|
(unsigned long)clock_time(),
|
(unsigned long)(loctt->ct.etimer.timer.start +
|
loctt->ct.etimer.timer.interval));
|
|
if(loctt->cb) {
|
/*
|
* Call the protocol's TX callback, with the suppression status as an
|
* argument.
|
*/
|
PRINTF("trickle_timer fire: Suppression Status %u (%u < %u)\n",
|
TRICKLE_TIMER_PROTO_TX_ALLOW(loctt), loctt->c, loctt->k);
|
loctt->cb(loctt->cb_arg, TRICKLE_TIMER_PROTO_TX_ALLOW(loctt));
|
}
|
|
if(trickle_timer_is_running(loctt)) {
|
schedule_for_end(loctt);
|
}
|
}
|
/*---------------------------------------------------------------------------*/
|
/* New trickle interval, either due to a newly set trickle timer or due to an
|
* inconsistency. Schedule 'fire' to be called in t ticks. */
|
static void
|
new_interval(struct trickle_timer *tt)
|
{
|
tt->c = 0;
|
|
/* Random t in [I/2, I) */
|
loc_clock = get_t(tt->i_cur);
|
|
ctimer_set(&tt->ct, loc_clock, fire, tt);
|
|
/* Store the actual interval start (absolute time), we need it later */
|
tt->i_start = tt->ct.etimer.timer.start;
|
PRINTF("trickle_timer new interval: at %lu, ends %lu, ",
|
(unsigned long)clock_time(),
|
(unsigned long)TRICKLE_TIMER_INTERVAL_END(tt));
|
PRINTF("t=%lu, I=%lu\n", (unsigned long)loc_clock, (unsigned long)tt->i_cur);
|
}
|
/*---------------------------------------------------------------------------*/
|
/* Functions to be called by the protocol implementation */
|
/*---------------------------------------------------------------------------*/
|
void
|
trickle_timer_consistency(struct trickle_timer *tt)
|
{
|
if(tt->c < 0xFF) {
|
tt->c++;
|
}
|
PRINTF("trickle_timer consistency: c=%u\n", tt->c);
|
}
|
/*---------------------------------------------------------------------------*/
|
void
|
trickle_timer_inconsistency(struct trickle_timer *tt)
|
{
|
/* "If I is equal to Imin when Trickle hears an "inconsistent" transmission,
|
* Trickle does nothing." */
|
if(tt->i_cur != tt->i_min) {
|
PRINTF("trickle_timer inconsistency\n");
|
tt->i_cur = tt->i_min;
|
|
new_interval(tt);
|
}
|
}
|
/*---------------------------------------------------------------------------*/
|
uint8_t
|
trickle_timer_config(struct trickle_timer *tt, clock_time_t i_min,
|
uint8_t i_max, uint8_t k)
|
{
|
#if TRICKLE_TIMER_ERROR_CHECKING
|
/*
|
* Although in theory Imin=1 is a valid value, it would break get_t() and
|
* doesn't make sense anyway. Thus Valid Imin values are in the range:
|
* 1 < Imin <= (TRICKLE_TIMER_CLOCK_MAX >> 1) + 1
|
*/
|
if(TRICKLE_TIMER_IMIN_IS_BAD(i_min)) {
|
PRINTF("trickle_timer config: Bad Imin value\n");
|
return TRICKLE_TIMER_ERROR;
|
}
|
|
if(tt == NULL || i_max == 0 || k == 0) {
|
PRINTF("trickle_timer config: Bad arguments\n");
|
return TRICKLE_TIMER_ERROR;
|
}
|
|
/*
|
* If clock_time_t is not wide enough to store Imin << Imax, we adjust Imax
|
*
|
* This means that 'we' are likely to have a different Imax than 'them'
|
* See RFC 6206, sec 6.3 for the consequences of this situation
|
*/
|
if(TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max)) {
|
PRINTF("trickle_timer config: %lu << %u would exceed clock boundaries. ",
|
(unsigned long)i_min, i_max);
|
|
/* For this Imin, get the maximum sane Imax */
|
i_max = max_imax(i_min);
|
PRINTF("trickle_timer config: Using Imax=%u\n", i_max);
|
}
|
#endif
|
|
tt->i_min = i_min;
|
tt->i_max = i_max;
|
tt->i_max_abs = i_min << i_max;
|
tt->k = k;
|
|
PRINTF("trickle_timer config: Imin=%lu, Imax=%u, k=%u\n",
|
(unsigned long)tt->i_min, tt->i_max, tt->k);
|
|
return TRICKLE_TIMER_SUCCESS;
|
}
|
/*---------------------------------------------------------------------------*/
|
uint8_t
|
trickle_timer_set(struct trickle_timer *tt, trickle_timer_cb_t proto_cb,
|
void *ptr)
|
{
|
#if TRICKLE_TIMER_ERROR_CHECKING
|
/* Sanity checks */
|
if(tt == NULL || proto_cb == NULL) {
|
PRINTF("trickle_timer set: Bad arguments\n");
|
return TRICKLE_TIMER_ERROR;
|
}
|
#endif
|
|
tt->cb = proto_cb;
|
tt->cb_arg = ptr;
|
|
/* Random I in [Imin , Imax] */
|
tt->i_cur = tt->i_min +
|
(tt_rand() % (TRICKLE_TIMER_INTERVAL_MAX(tt) - tt->i_min + 1));
|
|
PRINTF("trickle_timer set: I=%lu in [%lu , %lu]\n", (unsigned long)tt->i_cur,
|
(unsigned long)tt->i_min,
|
(unsigned long)TRICKLE_TIMER_INTERVAL_MAX(tt));
|
|
new_interval(tt);
|
|
PRINTF("trickle_timer set: at %lu, ends %lu, t=%lu in [%lu , %lu)\n",
|
(unsigned long)tt->i_start,
|
(unsigned long)TRICKLE_TIMER_INTERVAL_END(tt),
|
(unsigned long)tt->ct.etimer.timer.interval,
|
(unsigned long)tt->i_cur >> 1, (unsigned long)tt->i_cur);
|
|
return TRICKLE_TIMER_SUCCESS;
|
}
|
/*---------------------------------------------------------------------------*/
|
/** @} */
|
