Microchip® Advanced Software Framework

 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Trickle timers

This library implements timers which behave in accordance with RFC 6206 "The Trickle Algorithm" (http://tools.ietf.org/html/rfc6206)

Protocols wishing to use trickle timers, may use this library instead of implementing the trickle algorithm internally.

The protocol implementation will declare one (or more) variable(s) of type struct trickle_timer and will then populate its fields by calling trickle_timer_config(). trickle_timer_set() will start the timer.

When the timer reaches time t within the current trickle interval, the library will call a protocol-provided callback, which will signal to the protocol that it is time to TX (see algorithm step 4 in the RFC).

The proto does not need to check the suppression conditions. This is done by the library and if TX must be suppressed, the callback won't be called at all.

The library also provides functions to be called when the protocol hears a 'consistent' or 'inconsistent' message and when an 'external event' occurs (in this context, those terms have the exact same meaning as in the RFC).

Data Structures

struct  trickle_timer
 A trickle timer. More...
 

Files

file  trickle-timer.c
 Trickle timer library implementation.
 
file  trickle-timer.h
 Trickle timer library header file.
 

Macros

#define _DEBUG_   0
 
#define PRINTF(...)
 
#define TRICKLE_TIMER_COMPENSATE_DRIFT   1
 Controls whether the library will try to compensate for time drifts caused by getting called later than scheduled. More...
 
#define TRICKLE_TIMER_ERROR_CHECKING   1
 Enables/Disables error checking. More...
 
#define TRICKLE_TIMER_MAX_IMAX_WIDTH   TRICKLE_TIMER_MAX_IMAX_GENERIC
 Selects a flavor for the 'Find maximum Imax' (max_imax) function. More...
 
#define TRICKLE_TIMER_WIDE_RAND   1
 Turns on support for 4-byte wide, unsigned random numbers. More...
 
#define tt_rand()   random_rand()
 Wide randoms for platforms using a 4-byte wide clock (see TRICKLE_TIMER_WIDE_RAND) More...
 

Functions

static void double_interval (void *ptr)
 
static void fire (void *ptr)
 
static clock_time_t get_t (clock_time_t i_cur)
 
static void new_interval (struct trickle_timer *tt)
 
static void schedule_for_end (struct trickle_timer *tt)
 

Variables

static clock_time_t loc_clock
 
static struct trickle_timerloctt
 

Trickle Timer Library: Constants

#define TRICKLE_TIMER_INFINITE_REDUNDANCY   0x00
 Set as value of k to disable suppression. More...
 
#define TRICKLE_TIMER_ERROR   0
 
#define TRICKLE_TIMER_SUCCESS   1
 
#define TRICKLE_TIMER_MAX_IMAX_GENERIC   0
 Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the generic 'Find max Imax' routine. More...
 
#define TRICKLE_TIMER_MAX_IMAX_16_BIT   1
 Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 16-bit 'Find max Imax' routine. More...
 
#define TRICKLE_TIMER_MAX_IMAX_32_BIT   2
 Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 32-bit 'Find max Imax' routine. More...
 
#define TRICKLE_TIMER_TX_SUPPRESS   0
 Constants used as values for the suppress param of trickle_timer_cb_t. More...
 
#define TRICKLE_TIMER_TX_OK   1
 
#define TRICKLE_TIMER_IS_STOPPED   0
 A trickle timer is considered 'stopped' when i_cur == TRICKLE_TIMER_IS_STOPPED. More...
 

Trickle Timer Library: Macros

#define TRICKLE_TIMER_CLOCK_MAX   ((clock_time_t)~0)
 cross-platform method to get the maximum clock_time_t value More...
 
#define TRICKLE_TIMER_SUPPRESSION_ENABLED(tt)   ((tt)->k != TRICKLE_TIMER_INFINITE_REDUNDANCY)
 Checks if the trickle timer's suppression feature is enabled. More...
 
#define TRICKLE_TIMER_SUPPRESSION_DISABLED(tt)   ((tt)->k == TRICKLE_TIMER_INFINITE_REDUNDANCY)
 Checks if the trickle timer's suppression feature is disabled. More...
 
#define TRICKLE_TIMER_PROTO_TX_ALLOW(tt)   (TRICKLE_TIMER_SUPPRESSION_DISABLED(tt) || ((tt)->c < (tt)->k))
 Determines whether the protocol must go ahead with a transmission. More...
 
#define TRICKLE_TIMER_PROTO_TX_SUPPRESS(tt)   (TRICKLE_TIMER_SUPPRESSION_ENABLED(tt) && ((tt)->c >= (tt)->k))
 Determines whether the protocol must suppress a transmission. More...
 
#define TRICKLE_TIMER_INTERVAL_MAX(tt)   ((tt)->i_max_abs)
 Returns a timer's maximum interval size (Imin << Imax) as a number of clock ticks. More...
 
#define TRICKLE_TIMER_INTERVAL_END(tt)   ((tt)->i_start + (tt)->i_cur)
 Returns the current trickle interval's end (absolute time in ticks) More...
 
#define TRICKLE_TIMER_IMIN_IS_OK(imin)   ((imin > 1) && (i_min <= (TRICKLE_TIMER_CLOCK_MAX >> 1)))
 Checks whether an Imin value is suitable considering the various restrictions imposed by our platform's clock as well as by the library itself. More...
 
#define TRICKLE_TIMER_IMIN_IS_BAD(imin)   ((imin < 2) || (i_min > (TRICKLE_TIMER_CLOCK_MAX >> 1)))
 Checks whether an Imin value is invalid considering the various restrictions imposed by our platform's clock as well as by the library itself. More...
 
#define TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max)   ((TRICKLE_TIMER_CLOCK_MAX >> (i_max + 1)) < i_min - 1)
 Checks whether Imin << Imax is unsuitable considering the boundaries of our platform's clock_time_t. More...
 

Trickle Timer Library: Data Representation

typedef void(* trickle_timer_cb_t )(void *ptr, uint8_t suppress)
 typedef for a callback function to be defined in the protocol's implementation. More...
 

Trickle Timer Library: Functions called by protocol implementations

void trickle_timer_consistency (struct trickle_timer *tt)
 To be called by the protocol when it hears a consistent transmission. More...
 
void trickle_timer_inconsistency (struct trickle_timer *tt)
 To be called by the protocol when it hears an inconsistent transmission. More...
 
uint8_t trickle_timer_config (struct trickle_timer *tt, clock_time_t i_min, uint8_t i_max, uint8_t k)
 Configure a trickle timer. More...
 
uint8_t trickle_timer_set (struct trickle_timer *tt, trickle_timer_cb_t proto_cb, void *ptr)
 Start a previously configured trickle timer. More...
 
#define trickle_timer_stop(tt)
 Stop a running trickle timer. More...
 
#define trickle_timer_reset_event(tt)   trickle_timer_inconsistency(tt)
 To be called by the protocol when an external event occurs that should trigger a timer reset. More...
 
#define trickle_timer_is_running(tt)   ((tt)->i_cur != TRICKLE_TIMER_IS_STOPPED)
 To be called in order to determine whether a trickle timer is running. More...
 

#define _DEBUG_   0
#define TRICKLE_TIMER_CLOCK_MAX   ((clock_time_t)~0)

cross-platform method to get the maximum clock_time_t value

Referenced by double_interval(), and schedule_for_end().

#define TRICKLE_TIMER_COMPENSATE_DRIFT   1

Controls whether the library will try to compensate for time drifts caused by getting called later than scheduled.

1: Enabled (default). 0: Disabled

To override the default, define TRICKLE_TIMER_CONF_COMPENSATE_DRIFT in contiki-conf.h

Bear in mind that this controls the behaviour of the entire library (i.e. all trickle timers) and not of an individual timer

#define TRICKLE_TIMER_ERROR   0
#define TRICKLE_TIMER_ERROR_CHECKING   1

Enables/Disables error checking.

1: Enabled (default). The library checks the validity of Imin and Imax 0: Disabled. All error checking is turned off. This reduces code size.

#define TRICKLE_TIMER_IMIN_IS_BAD (   imin)    ((imin < 2) || (i_min > (TRICKLE_TIMER_CLOCK_MAX >> 1)))

Checks whether an Imin value is invalid considering the various restrictions imposed by our platform's clock as well as by the library itself.

Parameters
iminAn Imin value in clock ticks
Return values
1The Imin value is invalid
0The Imin value is valid

Referenced by trickle_timer_config().

#define TRICKLE_TIMER_IMIN_IS_OK (   imin)    ((imin > 1) && (i_min <= (TRICKLE_TIMER_CLOCK_MAX >> 1)))

Checks whether an Imin value is suitable considering the various restrictions imposed by our platform's clock as well as by the library itself.

Parameters
iminAn Imin value in clock ticks
Return values
1The Imin value is valid
0The Imin value is invalid
#define TRICKLE_TIMER_INFINITE_REDUNDANCY   0x00

Set as value of k to disable suppression.

#define TRICKLE_TIMER_INTERVAL_END (   tt)    ((tt)->i_start + (tt)->i_cur)

Returns the current trickle interval's end (absolute time in ticks)

Parameters
ttA pointer to a trickle_timer structure
Returns
The absolute number of clock ticks when the current trickle interval will expire

Referenced by double_interval(), new_interval(), schedule_for_end(), and trickle_timer_set().

#define TRICKLE_TIMER_INTERVAL_MAX (   tt)    ((tt)->i_max_abs)

Returns a timer's maximum interval size (Imin << Imax) as a number of clock ticks.

Parameters
ttA pointer to a trickle_timer structure
Returns
Maximum trickle interval length in clock ticks

Referenced by double_interval(), and trickle_timer_set().

#define TRICKLE_TIMER_IPAIR_IS_BAD (   i_min,
  i_max 
)    ((TRICKLE_TIMER_CLOCK_MAX >> (i_max + 1)) < i_min - 1)

Checks whether Imin << Imax is unsuitable considering the boundaries of our platform's clock_time_t.

Parameters
i_minImin value
i_maxMaximum number of doublings
Return values
non-zeroThe pair would exceed clock boundaries
0The pair is suitable for the platform

Timers scheduled far in the future can be perceived as being scheduled in the past. Thus, we limit Imin << Imax to be LEQ(TRICKLE_TIMER_CLOCK_MAX >> 1) + 1

Referenced by trickle_timer_config().

#define trickle_timer_is_running (   tt)    ((tt)->i_cur != TRICKLE_TIMER_IS_STOPPED)

To be called in order to determine whether a trickle timer is running.

Parameters
ttA pointer to a trickle_timer structure
Return values
0The timer is stopped
non-zeroThe timer is running

Referenced by fire().

#define TRICKLE_TIMER_IS_STOPPED   0

A trickle timer is considered 'stopped' when i_cur == TRICKLE_TIMER_IS_STOPPED.

trickle_timer_stop() must be used to correctly disable a trickle timer. Do NOT set the value of i_cur to 0 directly, as this will fail to stop the timer.

#define TRICKLE_TIMER_MAX_IMAX_16_BIT   1

Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 16-bit 'Find max Imax' routine.

#define TRICKLE_TIMER_MAX_IMAX_32_BIT   2

Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 32-bit 'Find max Imax' routine.

#define TRICKLE_TIMER_MAX_IMAX_GENERIC   0

Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the generic 'Find max Imax' routine.

#define TRICKLE_TIMER_MAX_IMAX_WIDTH   TRICKLE_TIMER_MAX_IMAX_GENERIC

Selects a flavor for the 'Find maximum Imax' (max_imax) function.

When configuring a new trickle timer, the library verifies that the (Imin , Imax) pair will fit in the platform's clock_time_t boundaries. If this is not the case, Imax will be adjusted down. In order to achieve this, we use an internal function which is a slight variant of a standard 'Count Leading Zeros'.

This functionality is disabled when TRICKLE_TIMER_ERROR_CHECKING is 0

This define helps us generate, at the pre-processing stage, the desired version of this function. We start with a generic version by default. The platform's contiki-conf.h can change this to use the 16- or 32-bit specific flavor by defining TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH.

Depending on the toolchain, the generic variant may actually result in a smaller code size. Do your own experiments.

TRICKLE_TIMER_MAX_IMAX_GENERIC (0): Generic function which will work regardless whether the platform uses a 16 or 32 bit wide clock type

TRICKLE_TIMER_MAX_IMAX_16_BIT (1): You can select this in your contiki-conf.h if your platform's clock_time_t is 16 bits wide

TRICKLE_TIMER_MAX_IMAX_32_BIT (2): You can select this in your contiki-conf.h if your platform's clock_time_t is 32 bits wide

#define TRICKLE_TIMER_PROTO_TX_ALLOW (   tt)    (TRICKLE_TIMER_SUPPRESSION_DISABLED(tt) || ((tt)->c < (tt)->k))

Determines whether the protocol must go ahead with a transmission.

Parameters
ttA pointer to a trickle_timer structure
Return values
non-zeroGo ahead with TX
0Suppress

Referenced by fire().

#define TRICKLE_TIMER_PROTO_TX_SUPPRESS (   tt)    (TRICKLE_TIMER_SUPPRESSION_ENABLED(tt) && ((tt)->c >= (tt)->k))

Determines whether the protocol must suppress a transmission.

Parameters
ttA pointer to a trickle_timer structure
Return values
non-zeroSuppress
0Go ahead with TX
#define trickle_timer_reset_event (   tt)    trickle_timer_inconsistency(tt)

To be called by the protocol when an external event occurs that should trigger a timer reset.

Parameters
ttA pointer to a trickle_timer structure

When an external event occurs that should result in a timer reset, the protocol implementation must call this function to notify the library.

Before resetting the timer, the library will perform a set of checks. Therefore, it is important that the protocol calls this function instead of trying to reset the timer by itself.

#define trickle_timer_stop (   tt)
Value:
do { \
ctimer_stop(&((tt)->ct)); \
(tt)->i_cur = TRICKLE_TIMER_IS_STOPPED; \
} while(0)
void ctimer_stop(struct ctimer *c)
Stop a pending callback timer.
Definition: ctimer.c:145
#define TRICKLE_TIMER_IS_STOPPED
A trickle timer is considered &#39;stopped&#39; when i_cur == TRICKLE_TIMER_IS_STOPPED.
Definition: trickle-timer.h:123

Stop a running trickle timer.

Parameters
ttA pointer to a trickle_timer structure

This function stops a running trickle timer that was previously started with trickle_timer_start(). After this function has been called, the trickle timer will no longer call the protocol's callback and its interval will not double any more. In order to resume the trickle timer, the user application must call trickle_timer_set().

The protocol implementation must NOT use trickle_timer_stop(), _set() cycles to reset a timer manually. Instead, in response to events or inconsistencies, the corresponding functions must be used

#define TRICKLE_TIMER_SUCCESS   1
#define TRICKLE_TIMER_SUPPRESSION_DISABLED (   tt)    ((tt)->k == TRICKLE_TIMER_INFINITE_REDUNDANCY)

Checks if the trickle timer's suppression feature is disabled.

Parameters
ttA pointer to a trickle_timer structure
Return values
non-zeroSuppression is disabled
0Suppression is enabled
#define TRICKLE_TIMER_SUPPRESSION_ENABLED (   tt)    ((tt)->k != TRICKLE_TIMER_INFINITE_REDUNDANCY)

Checks if the trickle timer's suppression feature is enabled.

Parameters
ttA pointer to a trickle_timer structure
Return values
non-zeroSuppression is enabled
0Suppression is disabled
#define TRICKLE_TIMER_TX_OK   1
#define TRICKLE_TIMER_TX_SUPPRESS   0

Constants used as values for the suppress param of trickle_timer_cb_t.

#define TRICKLE_TIMER_WIDE_RAND   1

Turns on support for 4-byte wide, unsigned random numbers.

We need this for platforms which have a 4-byte wide clock_time_t. For those platforms and if Imin << Imax is GT 0xFFFF, random_rand alone is not always enough to generate a correct t in [I/2, I). Specifically, we need wide randoms when I > 0x1FFFF.

For platforms with a 2-byte wide clock_time_t, this can be defined as 0 to reduce code footprint and increase speed.

#define tt_rand ( )    random_rand()

Wide randoms for platforms using a 4-byte wide clock (see TRICKLE_TIMER_WIDE_RAND)

Referenced by get_t(), and trickle_timer_set().

typedef void(* trickle_timer_cb_t)(void *ptr, uint8_t suppress)

typedef for a callback function to be defined in the protocol's implementation.

Those callbaks are stored as a function pointer inside a trickle_timer structure and are called by the library at time t within the current trickle interval.

Some protocols may rely on multiple trickle timers. For this reason, this function's argument will be an opaque pointer, aiming to help the protocol determine which timer triggered the call.

The suppress argument is used so that the library can signal the protocol whether it should TX or suppress

static clock_time_t get_t ( clock_time_t  i_cur)
static

References trickle_timer::i_cur, PRINTF, and tt_rand.

Referenced by double_interval(), and new_interval().

static void schedule_for_end ( struct trickle_timer tt)
static
uint8_t trickle_timer_config ( struct trickle_timer tt,
clock_time_t  i_min,
uint8_t  i_max,
uint8_t  k 
)

Configure a trickle timer.

Parameters
ttA pointer to a trickle_timer structure
i_minThe timer's Imin configuration parameter, in units of clock_time_t
i_maxThe timer's Imax configuration parameter (maximum number of doublings), specified as number of doublings
kThe timer's K (redundancy constant). If the value of K equals TRICKLE_TIMER_INFINITE_REDUNDANCY, message suppression will be disabled
Return values
0Error (Bad argument)
non-zeroSuccess.

This function is used to set the initial configuration for a trickle timer. A trickle timer MUST be configured before the protocol calls trickle_timer_set().

If Imin<<Imax would exceed the platform's clock_time_t boundaries, this function adjusts Imax to the maximum permitted value for the provided Imin. This means that in a network with heterogenous hardware, 'we' are likely to have a different Imax than 'some of them'. See RFC 6206, sec 6.3 for the consequences of this situation

References trickle_timer::i_max, trickle_timer::i_max_abs, trickle_timer::i_min, trickle_timer::k, NULL, PRINTF, TRICKLE_TIMER_ERROR, TRICKLE_TIMER_IMIN_IS_BAD, TRICKLE_TIMER_IPAIR_IS_BAD, and TRICKLE_TIMER_SUCCESS.

void trickle_timer_consistency ( struct trickle_timer tt)

To be called by the protocol when it hears a consistent transmission.

Parameters
ttA pointer to a trickle_timer structure

When the trickle-based protocol hears a consistent transmission it must call this function to increment trickle's consistency counter, which is later used to determine whether the protocol must suppress or go ahead with its own transmissions.

As the trickle timer library implementation may change in the future to perform further tasks upon reception of a consistent transmission, the protocol's implementation MUST use this call to increment the consistency counter instead of directly writing to the structure's field.

References trickle_timer::c, and PRINTF.

void trickle_timer_inconsistency ( struct trickle_timer tt)

To be called by the protocol when it hears an inconsistent transmission.

Parameters
ttA pointer to a trickle_timer structure

When the protocol hears an inconsistent transmission, it must call this function to notify the library that the timer must be reset.

Before resetting the timer, the library will perform a set of checks. Therefore, it is important that the protocol calls this function instead of trying to reset the timer by itself.

References trickle_timer::i_cur, trickle_timer::i_min, new_interval(), and PRINTF.

uint8_t trickle_timer_set ( struct trickle_timer tt,
trickle_timer_cb_t  proto_cb,
void *  ptr 
)

Start a previously configured trickle timer.

Parameters
ttA pointer to a trickle_timer structure
proto_cbA pointer to a callback function, which will be invoked at at time t within the current trickle interval
ptrAn opaque pointer which will be passed as the argument to proto_cb when the timer fires.
Return values
0Error (tt was null or the timer was not configured properly)
non-zeroSuccess.

This function is used to set a trickle timer. The protocol implementation must use this function ONLY to initialise a new trickle timer and NOT to reset it as a result of external events or inconsistencies.

The protocol implementation must configure the trickle timer by calling trickle_timer_config() before calling this function.

References trickle_timer::cb, trickle_timer::cb_arg, trickle_timer::ct, ctimer::etimer, trickle_timer::i_cur, trickle_timer::i_min, trickle_timer::i_start, timer::interval, new_interval(), NULL, PRINTF, ptr, etimer::timer, TRICKLE_TIMER_ERROR, TRICKLE_TIMER_INTERVAL_END, TRICKLE_TIMER_INTERVAL_MAX, TRICKLE_TIMER_SUCCESS, and tt_rand.

clock_time_t loc_clock
static
struct trickle_timer* loctt
static