Contiki-NG
trickle-timer.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012, George Oikonomou - <oikonomou@users.sourceforge.net>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution.
14  * 3. Neither the name of the copyright holder nor the names of its
15  * contributors may be used to endorse or promote products derived
16  * from this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
21  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
22  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
29  * OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 /**
33  * \file
34  * Trickle timer library header file.
35  *
36  * \author
37  * George Oikonomou - <oikonomou@users.sourceforge.net>
38  */
39 
40 /** \addtogroup lib
41  * @{ */
42 
43 /**
44  * \defgroup trickle-timer Trickle timers
45  *
46  * This library implements timers which behave in accordance with RFC 6206
47  * "The Trickle Algorithm" (http://tools.ietf.org/html/rfc6206)
48  *
49  * Protocols wishing to use trickle timers, may use this library instead of
50  * implementing the trickle algorithm internally.
51  *
52  * The protocol implementation will declare one (or more) variable(s) of type
53  * struct ::trickle_timer and will then populate its fields by calling
54  * trickle_timer_config(). trickle_timer_set() will start the timer.
55  *
56  * When the timer reaches time t within the current trickle interval, the
57  * library will call a protocol-provided callback, which will signal to the
58  * protocol that it is time to TX (see algorithm step 4 in the RFC).
59  *
60  * The proto does not need to check the suppression conditions. This is done by
61  * the library and if TX must be suppressed, the callback won't be called at
62  * all.
63  *
64  * The library also provides functions to be called when the protocol hears a
65  * 'consistent' or 'inconsistent' message and when an 'external event' occurs
66  * (in this context, those terms have the exact same meaning as in the RFC).
67  *
68  * It is \e not safe to manipulate trickle timers within an interrupt context.
69  * @{
70  */
71 
72 #ifndef TRICKLE_TIMER_H_
73 #define TRICKLE_TIMER_H_
74 
75 #include "contiki.h"
76 #include "sys/ctimer.h"
77 /*---------------------------------------------------------------------------*/
78 /* Trickle Timer Library Constants */
79 /*---------------------------------------------------------------------------*/
80 /**
81  * \name Trickle Timer Library: Constants
82  * @{
83  */
84 /*---------------------------------------------------------------------------*/
85 /**
86  * \brief Set as value of k to disable suppression
87  */
88 #define TRICKLE_TIMER_INFINITE_REDUNDANCY 0x00
89 
90 #define TRICKLE_TIMER_ERROR 0
91 #define TRICKLE_TIMER_SUCCESS 1
92 
93 /**
94  * \brief Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the
95  * generic 'Find max Imax' routine
96  */
97 #define TRICKLE_TIMER_MAX_IMAX_GENERIC 0
98 /**
99  * \brief Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 16-bit
100  * 'Find max Imax' routine
101  */
102 #define TRICKLE_TIMER_MAX_IMAX_16_BIT 1
103 /**
104  * \brief Use as the value of TRICKLE_TIMER_MAX_IMAX_WIDTH to enable the 32-bit
105  * 'Find max Imax' routine
106  */
107 #define TRICKLE_TIMER_MAX_IMAX_32_BIT 2
108 
109 /**
110  * \brief Constants used as values for the \e suppress param of
111  * trickle_timer_cb_t
112  */
113 #define TRICKLE_TIMER_TX_SUPPRESS 0
114 #define TRICKLE_TIMER_TX_OK 1
115 
116 /**
117  * \brief A trickle timer is considered 'stopped' when
118  * i_cur == TRICKLE_TIMER_IS_STOPPED.
119  *
120  * trickle_timer_stop() must be used to correctly disable a trickle timer.
121  * Do NOT set the value of i_cur to 0 directly, as this will fail to stop the
122  * timer.
123  */
124 #define TRICKLE_TIMER_IS_STOPPED 0
125 /** @} */
126 /*---------------------------------------------------------------------------*/
127 /**
128  * \brief Controls whether the library will try to compensate for time drifts
129  * caused by getting called later than scheduled.
130  *
131  * 1: Enabled (default). 0: Disabled
132  *
133  * To override the default, define TRICKLE_TIMER_CONF_COMPENSATE_DRIFT in
134  * contiki-conf.h
135  *
136  * Bear in mind that this controls the behaviour of the entire library (i.e.
137  * all trickle timers) and not of an individual timer
138  */
139 #ifdef TRICKLE_TIMER_CONF_COMPENSATE_DRIFT
140 #define TRICKLE_TIMER_COMPENSATE_DRIFT TRICKLE_TIMER_CONF_COMPENSATE_DRIFT
141 #else
142 #define TRICKLE_TIMER_COMPENSATE_DRIFT 1
143 #endif
144 /*---------------------------------------------------------------------------*/
145 /**
146  * \brief Turns on support for 4-byte wide, unsigned random numbers
147  *
148  * We need this for platforms which have a 4-byte wide clock_time_t. For those
149  * platforms and if Imin << Imax is GT 0xFFFF, random_rand alone is not always
150  * enough to generate a correct t in [I/2, I). Specifically, we need wide
151  * randoms when I > 0x1FFFF.
152  *
153  * For platforms with a 2-byte wide clock_time_t, this can be defined as 0
154  * to reduce code footprint and increase speed.
155  */
156 #ifdef TRICKLE_TIMER_CONF_WIDE_RAND
157 #define TRICKLE_TIMER_WIDE_RAND TRICKLE_TIMER_CONF_WIDE_RAND
158 #else
159 #define TRICKLE_TIMER_WIDE_RAND 1
160 #endif
161 /*---------------------------------------------------------------------------*/
162 /**
163  * \brief Selects a flavor for the 'Find maximum Imax' (max_imax) function.
164  *
165  * When configuring a new trickle timer, the library verifies that the (Imin ,
166  * Imax) pair will fit in the platform's clock_time_t boundaries. If this is
167  * not the case, Imax will be adjusted down. In order to achieve this, we use
168  * an internal function which is a slight variant of a standard 'Count Leading
169  * Zeros'.
170  *
171  * This functionality is disabled when ::TRICKLE_TIMER_ERROR_CHECKING is 0
172  *
173  * This define helps us generate, at the pre-processing stage, the desired
174  * version of this function. We start with a generic version by default. The
175  * platform's contiki-conf.h can change this to use the 16- or 32-bit specific
176  * flavor by defining TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH.
177  *
178  * Depending on the toolchain, the generic variant may actually result in a
179  * smaller code size. Do your own experiments.
180  *
181  * TRICKLE_TIMER_MAX_IMAX_GENERIC (0): Generic function which will work
182  * regardless whether the platform uses a 16 or 32 bit wide clock type
183  *
184  * TRICKLE_TIMER_MAX_IMAX_16_BIT (1): You can select this in your
185  * contiki-conf.h if your platform's clock_time_t is 16 bits wide
186  *
187  * TRICKLE_TIMER_MAX_IMAX_32_BIT (2): You can select this in your
188  * contiki-conf.h if your platform's clock_time_t is 32 bits wide
189  */
190 #ifdef TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH
191 #define TRICKLE_TIMER_MAX_IMAX_WIDTH TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH
192 #else
193 #define TRICKLE_TIMER_MAX_IMAX_WIDTH TRICKLE_TIMER_MAX_IMAX_GENERIC
194 #endif
195 
196 /**
197  * \brief Enables/Disables error checking
198  *
199  * 1: Enabled (default). The library checks the validity of Imin and Imax
200  * 0: Disabled. All error checking is turned off. This reduces code size.
201  */
202 #ifdef TRICKLE_TIMER_CONF_ERROR_CHECKING
203 #define TRICKLE_TIMER_ERROR_CHECKING TRICKLE_TIMER_CONF_ERROR_CHECKING
204 #else
205 #define TRICKLE_TIMER_ERROR_CHECKING 1
206 #endif
207 /*---------------------------------------------------------------------------*/
208 /* Trickle Timer Library Macros */
209 /*---------------------------------------------------------------------------*/
210 /**
211  * \name Trickle Timer Library: Macros
212  * @{
213  */
214 /**
215  * \brief cross-platform method to get the maximum clock_time_t value
216  */
217 #define TRICKLE_TIMER_CLOCK_MAX ((clock_time_t)~0)
218 
219 
220 /**
221  * \brief Checks if the trickle timer's suppression feature is enabled
222  *
223  * \param tt A pointer to a ::trickle_timer structure
224  *
225  * \retval non-zero Suppression is enabled
226  * \retval 0 Suppression is disabled
227  */
228 #define TRICKLE_TIMER_SUPPRESSION_ENABLED(tt) \
229  ((tt)->k != TRICKLE_TIMER_INFINITE_REDUNDANCY)
230 
231 /**
232  * \brief Checks if the trickle timer's suppression feature is disabled
233  *
234  * \param tt A pointer to a ::trickle_timer structure
235  *
236  * \retval non-zero Suppression is disabled
237  * \retval 0 Suppression is enabled
238  */
239 #define TRICKLE_TIMER_SUPPRESSION_DISABLED(tt) \
240  ((tt)->k == TRICKLE_TIMER_INFINITE_REDUNDANCY)
241 
242 /**
243  * \brief Determines whether the protocol must go ahead with a transmission
244  *
245  * \param tt A pointer to a ::trickle_timer structure
246  *
247  * \retval non-zero Go ahead with TX
248  * \retval 0 Suppress
249  */
250 #define TRICKLE_TIMER_PROTO_TX_ALLOW(tt) \
251  (TRICKLE_TIMER_SUPPRESSION_DISABLED(tt) || ((tt)->c < (tt)->k))
252 
253 /**
254  * \brief Determines whether the protocol must suppress a transmission
255  *
256  * \param tt A pointer to a ::trickle_timer structure
257  *
258  * \retval non-zero Suppress
259  * \retval 0 Go ahead with TX
260  */
261 #define TRICKLE_TIMER_PROTO_TX_SUPPRESS(tt) \
262  (TRICKLE_TIMER_SUPPRESSION_ENABLED(tt) && ((tt)->c >= (tt)->k))
263 
264 /**
265  * \brief Returns a timer's maximum interval size (Imin << Imax) as a number of
266  * clock ticks
267  *
268  * \param tt A pointer to a ::trickle_timer structure
269  *
270  * \return Maximum trickle interval length in clock ticks
271  */
272 #define TRICKLE_TIMER_INTERVAL_MAX(tt) ((tt)->i_max_abs)
273 
274 /**
275  * \brief Returns the current trickle interval's end (absolute time in ticks)
276  *
277  * \param tt A pointer to a ::trickle_timer structure
278  *
279  * \return The absolute number of clock ticks when the current trickle interval
280  * will expire
281  */
282 #define TRICKLE_TIMER_INTERVAL_END(tt) ((tt)->i_start + (tt)->i_cur)
283 
284 /**
285  * \brief Checks whether an Imin value is suitable considering the various
286  * restrictions imposed by our platform's clock as well as by the library itself
287  *
288  * \param imin An Imin value in clock ticks
289  *
290  * \retval 1 The Imin value is valid
291  * \retval 0 The Imin value is invalid
292  */
293 #define TRICKLE_TIMER_IMIN_IS_OK(imin) \
294  ((imin > 1) && (i_min <= (TRICKLE_TIMER_CLOCK_MAX >> 1)))
295 
296 /**
297  * \brief Checks whether an Imin value is invalid considering the various
298  * restrictions imposed by our platform's clock as well as by the library itself
299  *
300  * \param imin An Imin value in clock ticks
301  *
302  * \retval 1 The Imin value is invalid
303  * \retval 0 The Imin value is valid
304  */
305 #define TRICKLE_TIMER_IMIN_IS_BAD(imin) \
306  ((imin < 2) || (i_min > (TRICKLE_TIMER_CLOCK_MAX >> 1)))
307 
308 /**
309  * \brief Checks whether Imin << Imax is unsuitable considering the boundaries
310  * of our platform's clock_time_t
311  *
312  * \param i_min Imin value
313  * \param i_max Maximum number of doublings
314  *
315  * \retval non-zero The pair would exceed clock boundaries
316  * \retval 0 The pair is suitable for the platform
317  *
318  * Timers scheduled far in the future can be perceived as being scheduled in
319  * the past.
320  * Thus, we limit Imin << Imax to be LEQ(TRICKLE_TIMER_CLOCK_MAX >> 1) + 1
321  */
322 #define TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max) \
323  ((TRICKLE_TIMER_CLOCK_MAX >> (i_max + 1)) < i_min - 1)
324 /** @} */
325 /*---------------------------------------------------------------------------*/
326 /* Trickle Timer Library Data Representation */
327 /*---------------------------------------------------------------------------*/
328 /**
329  * \name Trickle Timer Library: Data Representation
330  * @{
331  */
332 
333 /**
334  * \brief typedef for a callback function to be defined in the protocol's
335  * implementation.
336  *
337  * Those callbaks are stored as a function pointer inside a ::trickle_timer
338  * structure and are called by the library at time t within the current trickle
339  * interval.
340  *
341  * Some protocols may rely on multiple trickle timers. For this reason, this
342  * function's argument will be an opaque pointer, aiming to help the protocol
343  * determine which timer triggered the call.
344  *
345  * The \e suppress argument is used so that the library can signal the protocol
346  * whether it should TX or suppress
347  */
348 typedef void (* trickle_timer_cb_t)(void *ptr, uint8_t suppress);
349 
350 /**
351  * \struct trickle_timer
352  *
353  * A trickle timer.
354  *
355  * This structure is used for declaring a trickle timer. In order for the timer
356  * to start running, the protocol must first populate the structure's fields
357  * by calling trickle_timer_set(). Protocol implementations must NOT modify the
358  * contents of this structure directly.
359  *
360  * Protocol developers must also be careful to specify the values of Imin and
361  * Imax in such a way that the maximum interval size does not exceed the
362  * boundaries of clock_time_t
363  */
365  clock_time_t i_min; /**< Imin: Clock ticks */
366  clock_time_t i_cur; /**< I: Current interval in clock_ticks */
367  clock_time_t i_start; /**< Start of this interval (absolute clock_time) */
368  clock_time_t i_max_abs; /**< Maximum interval size in clock ticks (and not in
369  number of doublings). This is a cached value of
370  Imin << Imax used internally, so that we can
371  have direct access to the maximum interval size
372  without having to calculate it all the time */
373  struct ctimer ct; /**< A \ref ctimer used internally */
374  trickle_timer_cb_t cb; /**< Protocol's own callback, invoked at time t
375  within the current interval */
376  void *cb_arg; /**< Opaque pointer to be used as the argument of the
377  protocol's callback */
378  uint8_t i_max; /**< Imax: Max number of doublings */
379  uint8_t k; /**< k: Redundancy Constant */
380  uint8_t c; /**< c: Consistency Counter */
381 };
382 /** @} */
383 /*---------------------------------------------------------------------------*/
384 /* Trickle Timer Library Functions */
385 /*---------------------------------------------------------------------------*/
386 /**
387  * \name Trickle Timer Library: Functions called by protocol implementations
388  * @{
389  */
390 
391 /**
392  * \brief Configure a trickle timer
393  * \param tt A pointer to a ::trickle_timer structure
394  * \param i_min The timer's Imin configuration parameter, in units of
395  * clock_time_t
396  * \param i_max The timer's Imax configuration parameter (maximum number of
397  * doublings), specified as number of doublings
398  * \param k The timer's K (redundancy constant). If the value of K
399  * equals #TRICKLE_TIMER_INFINITE_REDUNDANCY, message
400  * suppression will be disabled
401  * \retval 0 Error (Bad argument)
402  * \retval non-zero Success.
403  *
404  * This function is used to set the initial configuration for a trickle timer.
405  * A trickle timer MUST be configured before the protocol calls
406  * trickle_timer_set().
407  *
408  * If Imin<<Imax would exceed the platform's clock_time_t boundaries, this
409  * function adjusts Imax to the maximum permitted value for the provided Imin.
410  * This means that in a network with heterogenous hardware, 'we' are likely to
411  * have a different Imax than 'some of them'. See RFC 6206, sec 6.3 for the
412  * consequences of this situation
413  */
414 uint8_t trickle_timer_config(struct trickle_timer *tt, clock_time_t i_min,
415  uint8_t i_max, uint8_t k);
416 
417 /**
418  * \brief Start a previously configured trickle timer
419  * \param tt A pointer to a ::trickle_timer structure
420  * \param proto_cb A pointer to a callback function, which will be invoked at
421  * at time t within the current trickle interval
422  * \param ptr An opaque pointer which will be passed as the argument to
423  * proto_cb when the timer fires.
424  * \retval 0 Error (tt was null or the timer was not configured properly)
425  * \retval non-zero Success.
426  *
427  * This function is used to set a trickle timer. The protocol implementation
428  * must use this function ONLY to initialise a new trickle timer and NOT to
429  * reset it as a result of external events or inconsistencies.
430  *
431  * The protocol implementation must configure the trickle timer by calling
432  * trickle_timer_config() before calling this function.
433  */
434 uint8_t trickle_timer_set(struct trickle_timer *tt,
435  trickle_timer_cb_t proto_cb, void *ptr);
436 
437 /**
438  * \brief Stop a running trickle timer.
439  * \param tt A pointer to a ::trickle_timer structure
440  *
441  * This function stops a running trickle timer that was previously started with
442  * trickle_timer_start(). After this function has been called, the trickle
443  * timer will no longer call the protocol's callback and its interval will not
444  * double any more. In order to resume the trickle timer, the user application
445  * must call trickle_timer_set().
446  *
447  * The protocol implementation must NOT use trickle_timer_stop(), _set() cycles
448  * to reset a timer manually. Instead, in response to events or inconsistencies,
449  * the corresponding functions must be used
450  */
451 #define trickle_timer_stop(tt) do { \
452  ctimer_stop(&((tt)->ct)); \
453  (tt)->i_cur = TRICKLE_TIMER_IS_STOPPED; \
454 } while(0)
455 
456 /**
457  * \brief To be called by the protocol when it hears a consistent
458  * transmission
459  * \param tt A pointer to a ::trickle_timer structure
460  *
461  * When the trickle-based protocol hears a consistent transmission it must call
462  * this function to increment trickle's consistency counter, which is later
463  * used to determine whether the protocol must suppress or go ahead with its
464  * own transmissions.
465  *
466  * As the trickle timer library implementation may change in the future to
467  * perform further tasks upon reception of a consistent transmission, the
468  * protocol's implementation MUST use this call to increment the consistency
469  * counter instead of directly writing to the structure's field.
470  */
472 
473 /**
474  * \brief To be called by the protocol when it hears an inconsistent
475  * transmission
476  * \param tt A pointer to a ::trickle_timer structure
477  *
478  * When the protocol hears an inconsistent transmission, it must call this
479  * function to notify the library that the timer must be reset.
480  *
481  * Before resetting the timer, the library will perform a set of checks.
482  * Therefore, it is important that the protocol calls this function instead of
483  * trying to reset the timer by itself.
484  */
486 
487 /**
488  * \brief To be called by the protocol when an external event occurs that
489  * should trigger a timer reset
490  * \param tt A pointer to a ::trickle_timer structure
491  *
492  * When an external event occurs that should result in a timer reset, the
493  * protocol implementation must call this function to notify the library.
494  *
495  * Before resetting the timer, the library will perform a set of checks.
496  * Therefore, it is important that the protocol calls this function instead of
497  * trying to reset the timer by itself.
498  */
499 #define trickle_timer_reset_event(tt) trickle_timer_inconsistency(tt)
500 
501 /**
502  * \brief To be called in order to determine whether a trickle timer is
503  * running
504  * \param tt A pointer to a ::trickle_timer structure
505  * \retval 0 The timer is stopped
506  * \retval non-zero The timer is running
507  *
508  */
509 #define trickle_timer_is_running(tt) ((tt)->i_cur != TRICKLE_TIMER_IS_STOPPED)
510 
511 /** @} */
512 
513 #endif /* TRICKLE_TIMER_H_ */
514 /** @} */
515 /** @} */
A trickle timer.
uint8_t trickle_timer_set(struct trickle_timer *tt, trickle_timer_cb_t proto_cb, void *ptr)
Start a previously configured trickle timer.
void trickle_timer_consistency(struct trickle_timer *tt)
To be called by the protocol when it hears a consistent transmission.
void(* trickle_timer_cb_t)(void *ptr, uint8_t suppress)
typedef for a callback function to be defined in the protocol&#39;s implementation.
void trickle_timer_inconsistency(struct trickle_timer *tt)
To be called by the protocol when it hears an inconsistent transmission.
struct ctimer ct
A Callback timer used internally.
clock_time_t i_max_abs
Maximum interval size in clock ticks (and not in number of doublings).
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.
clock_time_t i_start
Start of this interval (absolute clock_time)
trickle_timer_cb_t cb
Protocol&#39;s own callback, invoked at time t within the current interval.
clock_time_t i_min
Imin: Clock ticks.
Header file for the callback timer
clock_time_t i_cur
I: Current interval in clock_ticks.
uint8_t i_max
Imax: Max number of doublings.
void * cb_arg
Opaque pointer to be used as the argument of the protocol&#39;s callback.
uint8_t c
c: Consistency Counter
uint8_t k
k: Redundancy Constant