Contiki-NG
trickle-timer.c
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 implementation.
35  * \author
36  * George Oikonomou - <oikonomou@users.sourceforge.net>
37  */
38 
39 /**
40  * \addtogroup trickle-timer
41  * @{
42  */
43 
44 #include "contiki.h"
45 #include "lib/trickle-timer.h"
46 #include "sys/ctimer.h"
47 #include "sys/cc.h"
48 #include "lib/random.h"
49 /*---------------------------------------------------------------------------*/
50 #define DEBUG 0
51 
52 #if DEBUG
53 #include <stdio.h>
54 #define PRINTF(...) printf(__VA_ARGS__)
55 #else
56 #define PRINTF(...)
57 #endif
58 /*---------------------------------------------------------------------------*/
59 /**
60  * \brief Wide randoms for platforms using a 4-byte wide clock
61  * (see ::TRICKLE_TIMER_WIDE_RAND)
62  */
63 #if TRICKLE_TIMER_WIDE_RAND
64 #define tt_rand() wide_rand()
65 #else
66 #define tt_rand() random_rand()
67 #endif
68 /*---------------------------------------------------------------------------*/
69 /* Declarations of variables of local interest */
70 /*---------------------------------------------------------------------------*/
71 static struct trickle_timer *loctt; /* Pointer to a struct for local use */
72 static clock_time_t loc_clock; /* A local, general-purpose placeholder */
73 
74 static void fire(void *ptr);
75 static void double_interval(void *ptr);
76 /*---------------------------------------------------------------------------*/
77 /* Local utilities and functions to be used as ctimer callbacks */
78 /*---------------------------------------------------------------------------*/
79 #if TRICKLE_TIMER_WIDE_RAND
80 /* Returns a 4-byte wide, unsigned random number */
81 static uint32_t
82 wide_rand(void)
83 {
84  return (uint32_t)random_rand() << 16 | random_rand();
85 }
86 #endif
87 /*---------------------------------------------------------------------------*/
88 /*
89  * Returns the maximum sane Imax value for a given Imin
90  *
91  * This function is a variant of a fairly standard 'Count Leading Zeros'. It
92  * has three flavours. The most suitable one for a specific platform can be
93  * configured by changing the value of TRICKLE_TIMER_CONF_MAX_IMAX_WIDTH
94  * in the platform's contiki-conf.h
95  */
96 #if TRICKLE_TIMER_ERROR_CHECKING
97 static uint8_t
98 max_imax(clock_time_t value)
99 {
100  uint8_t zeros = 0;
101 #if (TRICKLE_TIMER_MAX_IMAX_WIDTH == TRICKLE_TIMER_MAX_IMAX_GENERIC)
102  uint8_t i;
103  clock_time_t mask = 0xFFFF;
104 
105  value--;
106 
107  for(i = sizeof(clock_time_t) << 2; i > 0; i >>= 1) {
108  if((value & (mask <<= i)) == 0) {
109  zeros += i;
110  value <<= i;
111  }
112  }
113 
114 #elif (TRICKLE_TIMER_MAX_IMAX_WIDTH == TRICKLE_TIMER_MAX_IMAX_16_BIT)
115  if((value & 0xFF00) == 0) {
116  zeros += 8;
117  value <<= 8;
118  }
119  if((value & 0xF000) == 0) {
120  zeros += 4;
121  value <<= 4;
122  }
123  if((value & 0xC000) == 0) {
124  zeros += 2;
125  value <<= 2;
126  }
127  if((value & 0x8000) == 0) {
128  zeros++;
129  }
130 #elif (TRICKLE_TIMER_MAX_IMAX_WIDTH == TRICKLE_TIMER_MAX_IMAX_32_BIT)
131  if((value & 0xFFFF0000) == 0) {
132  zeros += 16;
133  value <<= 16;
134  }
135  if((value & 0xFF000000) == 0) {
136  zeros += 8;
137  value <<= 8;
138  }
139  if((value & 0xF0000000) == 0) {
140  zeros += 4;
141  value <<= 4;
142  }
143  if((value & 0xC0000000) == 0) {
144  zeros += 2;
145  value <<= 2;
146  }
147  if((value & 0x80000000) == 0) {
148  zeros += 1;
149  }
150 #endif
151 
152  return zeros - 1; /* Always non-negative due to the range of 'value' */
153 }
154 #endif /* TRICKLE_TIMER_ERROR_CHECKING */
155 /*---------------------------------------------------------------------------*/
156 /* Returns a random time point t in [I/2 , I) */
157 static clock_time_t
158 get_t(clock_time_t i_cur)
159 {
160  i_cur >>= 1;
161 
162  PRINTF("trickle_timer get t: [%lu, %lu)\n", (unsigned long)i_cur,
163  (unsigned long)(i_cur << 1));
164 
165  return i_cur + (tt_rand() % i_cur);
166 }
167 /*---------------------------------------------------------------------------*/
168 static void
169 schedule_for_end(struct trickle_timer *tt)
170 {
171  /* Reset our ctimer, schedule interval_end to run at time I */
172  clock_time_t now = clock_time();
173 
174  loc_clock = TRICKLE_TIMER_INTERVAL_END(tt) - now;
175 
176  PRINTF("trickle_timer sched for end: at %lu, end in %ld\n",
177  (unsigned long)clock_time(), (signed long)loc_clock);
178 
179  /* Interval's end will happen in loc_clock ticks. Make sure this isn't in
180  * the past... */
181  if(loc_clock > (TRICKLE_TIMER_CLOCK_MAX >> 1)) {
182  loc_clock = 0; /* Interval ended in the past, schedule for in 0 */
183  PRINTF("trickle_timer doubling: Was in the past. Compensating\n");
184  }
185 
186  ctimer_set(&tt->ct, loc_clock, double_interval, tt);
187 }
188 /*---------------------------------------------------------------------------*/
189 /* This is used as a ctimer callback, thus its argument must be void *. ptr is
190  * a pointer to the struct trickle_timer that fired */
191 static void
192 double_interval(void *ptr)
193 {
194  clock_time_t last_end;
195 
196  /* 'cast' ptr to a struct trickle_timer */
197  loctt = (struct trickle_timer *)ptr;
198 
199  loctt->c = 0;
200 
201  PRINTF("trickle_timer doubling: at %lu, (was for %lu), ",
202  (unsigned long)clock_time(),
203  (unsigned long)TRICKLE_TIMER_INTERVAL_END(loctt));
204 
205  /* Remember the previous interval's end (absolute time), before we double */
206  last_end = TRICKLE_TIMER_INTERVAL_END(loctt);
207 
208  /* Double the interval if we have to */
209  if(loctt->i_cur <= TRICKLE_TIMER_INTERVAL_MAX(loctt) >> 1) {
210  /* If I <= Imax/2, we double */
211  loctt->i_cur <<= 1;
212  PRINTF("I << 1 = %lu\n", (unsigned long)loctt->i_cur);
213  } else {
214  /* We may have I > Imax/2 but I <> Imax, in which case we set to Imax
215  * This will happen when I didn't start as Imin (before the first reset) */
216  loctt->i_cur = TRICKLE_TIMER_INTERVAL_MAX(loctt);
217  PRINTF("I = Imax = %lu\n", (unsigned long)loctt->i_cur);
218  }
219 
220  /* Random t in [I/2, I) */
221  loc_clock = get_t(loctt->i_cur);
222 
223  PRINTF("trickle_timer doubling: t=%lu\n", (unsigned long)loc_clock);
224 
225 #if TRICKLE_TIMER_COMPENSATE_DRIFT
226  /* Schedule for t ticks after the previous interval's end, not after now. If
227  * that is in the past, schedule in 0 */
228  loc_clock = (last_end + loc_clock) - clock_time();
229  PRINTF("trickle_timer doubling: at %lu, in %ld ticks\n",
230  (unsigned long)clock_time(), (signed long)loc_clock);
231  if(loc_clock > (TRICKLE_TIMER_CLOCK_MAX >> 1)) {
232  /* Oops, that's in the past */
233  loc_clock = 0;
234  PRINTF("trickle_timer doubling: Was in the past. Compensating\n");
235  }
236  ctimer_set(&loctt->ct, loc_clock, fire, loctt);
237 
238  /* Store the actual interval start (absolute time), we need it later.
239  * We pretend that it started at the same time when the last one ended */
240  loctt->i_start = last_end;
241 #else
242  /* Assumed that the previous interval's end is 'now' and schedule in t ticks
243  * after 'now', ignoring potential offsets */
244  ctimer_set(&loctt->ct, loc_clock, fire, loctt);
245  /* Store the actual interval start (absolute time), we need it later */
246  loctt->i_start = loctt->ct.etimer.timer.start;
247 #endif
248 
249  PRINTF("trickle_timer doubling: Last end %lu, new end %lu, for %lu, I=%lu\n",
250  (unsigned long)last_end,
251  (unsigned long)TRICKLE_TIMER_INTERVAL_END(loctt),
252  (unsigned long)(loctt->ct.etimer.timer.start +
253  loctt->ct.etimer.timer.interval),
254  (unsigned long)(loctt->i_cur));
255 }
256 /*---------------------------------------------------------------------------*/
257 /* Called by the ctimer module at time t within the current interval. ptr is
258  * a pointer to the struct trickle_timer of interest */
259 static void
260 fire(void *ptr)
261 {
262  /* 'cast' c to a struct trickle_timer */
263  loctt = (struct trickle_timer *)ptr;
264 
265  PRINTF("trickle_timer fire: at %lu (was for %lu)\n",
266  (unsigned long)clock_time(),
267  (unsigned long)(loctt->ct.etimer.timer.start +
268  loctt->ct.etimer.timer.interval));
269 
270  if(loctt->cb) {
271  /*
272  * Call the protocol's TX callback, with the suppression status as an
273  * argument.
274  */
275  PRINTF("trickle_timer fire: Suppression Status %u (%u < %u)\n",
276  TRICKLE_TIMER_PROTO_TX_ALLOW(loctt), loctt->c, loctt->k);
277  loctt->cb(loctt->cb_arg, TRICKLE_TIMER_PROTO_TX_ALLOW(loctt));
278  }
279 
280  if(trickle_timer_is_running(loctt)) {
281  schedule_for_end(loctt);
282  }
283 }
284 /*---------------------------------------------------------------------------*/
285 /* New trickle interval, either due to a newly set trickle timer or due to an
286  * inconsistency. Schedule 'fire' to be called in t ticks. */
287 static void
288 new_interval(struct trickle_timer *tt)
289 {
290  tt->c = 0;
291 
292  /* Random t in [I/2, I) */
293  loc_clock = get_t(tt->i_cur);
294 
295  ctimer_set(&tt->ct, loc_clock, fire, tt);
296 
297  /* Store the actual interval start (absolute time), we need it later */
298  tt->i_start = tt->ct.etimer.timer.start;
299  PRINTF("trickle_timer new interval: at %lu, ends %lu, ",
300  (unsigned long)clock_time(),
301  (unsigned long)TRICKLE_TIMER_INTERVAL_END(tt));
302  PRINTF("t=%lu, I=%lu\n", (unsigned long)loc_clock, (unsigned long)tt->i_cur);
303 }
304 /*---------------------------------------------------------------------------*/
305 /* Functions to be called by the protocol implementation */
306 /*---------------------------------------------------------------------------*/
307 void
309 {
310  if(tt->i_cur == TRICKLE_TIMER_IS_STOPPED) {
311  return;
312  }
313  if(tt->c < 0xFF) {
314  tt->c++;
315  }
316  PRINTF("trickle_timer consistency: c=%u\n", tt->c);
317 }
318 /*---------------------------------------------------------------------------*/
319 void
321 {
322  if(tt->i_cur == TRICKLE_TIMER_IS_STOPPED) {
323  return;
324  }
325  /* "If I is equal to Imin when Trickle hears an "inconsistent" transmission,
326  * Trickle does nothing." */
327  if(tt->i_cur != tt->i_min) {
328  PRINTF("trickle_timer inconsistency\n");
329  tt->i_cur = tt->i_min;
330 
331  new_interval(tt);
332  }
333 }
334 /*---------------------------------------------------------------------------*/
335 uint8_t
336 trickle_timer_config(struct trickle_timer *tt, clock_time_t i_min,
337  uint8_t i_max, uint8_t k)
338 {
339 #if TRICKLE_TIMER_ERROR_CHECKING
340  /*
341  * Although in theory Imin=1 is a valid value, it would break get_t() and
342  * doesn't make sense anyway. Thus Valid Imin values are in the range:
343  * 1 < Imin <= (TRICKLE_TIMER_CLOCK_MAX >> 1) + 1
344  */
345  if(TRICKLE_TIMER_IMIN_IS_BAD(i_min)) {
346  PRINTF("trickle_timer config: Bad Imin value\n");
347  return TRICKLE_TIMER_ERROR;
348  }
349 
350  if(tt == NULL || i_max == 0 || k == 0) {
351  PRINTF("trickle_timer config: Bad arguments\n");
352  return TRICKLE_TIMER_ERROR;
353  }
354 
355  /*
356  * If clock_time_t is not wide enough to store Imin << Imax, we adjust Imax
357  *
358  * This means that 'we' are likely to have a different Imax than 'them'
359  * See RFC 6206, sec 6.3 for the consequences of this situation
360  */
361  if(TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max)) {
362  PRINTF("trickle_timer config: %lu << %u would exceed clock boundaries. ",
363  (unsigned long)i_min, i_max);
364 
365  /* For this Imin, get the maximum sane Imax */
366  i_max = max_imax(i_min);
367  PRINTF("trickle_timer config: Using Imax=%u\n", i_max);
368  }
369 #endif
370 
371  tt->i_min = i_min;
372  tt->i_max = i_max;
373  tt->i_max_abs = i_min << i_max;
374  tt->k = k;
376  tt->cb = NULL;
377 
378  PRINTF("trickle_timer config: Imin=%lu, Imax=%u, k=%u\n",
379  (unsigned long)tt->i_min, tt->i_max, tt->k);
380 
381  return TRICKLE_TIMER_SUCCESS;
382 }
383 /*---------------------------------------------------------------------------*/
384 uint8_t
386  void *ptr)
387 {
388 #if TRICKLE_TIMER_ERROR_CHECKING
389  /* Sanity checks */
390  if(tt == NULL || proto_cb == NULL) {
391  PRINTF("trickle_timer set: Bad arguments\n");
392  return TRICKLE_TIMER_ERROR;
393  }
394 #endif
395 
396  tt->cb = proto_cb;
397  tt->cb_arg = ptr;
398 
399  /* Random I in [Imin , Imax] */
400  tt->i_cur = tt->i_min +
401  (tt_rand() % (TRICKLE_TIMER_INTERVAL_MAX(tt) - tt->i_min + 1));
402 
403  PRINTF("trickle_timer set: I=%lu in [%lu , %lu]\n", (unsigned long)tt->i_cur,
404  (unsigned long)tt->i_min,
405  (unsigned long)TRICKLE_TIMER_INTERVAL_MAX(tt));
406 
407  new_interval(tt);
408 
409  PRINTF("trickle_timer set: at %lu, ends %lu, t=%lu in [%lu , %lu)\n",
410  (unsigned long)tt->i_start,
411  (unsigned long)TRICKLE_TIMER_INTERVAL_END(tt),
412  (unsigned long)tt->ct.etimer.timer.interval,
413  (unsigned long)tt->i_cur >> 1, (unsigned long)tt->i_cur);
414 
415  return TRICKLE_TIMER_SUCCESS;
416 }
417 /*---------------------------------------------------------------------------*/
418 /** @} */
#define TRICKLE_TIMER_INTERVAL_MAX(tt)
Returns a timer&#39;s maximum interval size (Imin << Imax) as a number of clock ticks.
A trickle timer.
Trickle timer library header file.
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)
#define trickle_timer_is_running(tt)
To be called in order to determine whether a trickle timer is running.
#define TRICKLE_TIMER_PROTO_TX_ALLOW(tt)
Determines whether the protocol must go ahead with a transmission.
trickle_timer_cb_t cb
Protocol&#39;s own callback, invoked at time t within the current interval.
#define TRICKLE_TIMER_CLOCK_MAX
cross-platform method to get the maximum clock_time_t value
clock_time_t i_min
Imin: Clock ticks.
Header file for the callback timer
void ctimer_set(struct ctimer *c, clock_time_t t, void(*f)(void *), void *ptr)
Set a callback timer.
Definition: ctimer.c:99
#define TRICKLE_TIMER_IMIN_IS_BAD(imin)
Checks whether an Imin value is invalid considering the various restrictions imposed by our platform&#39;...
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
#define TRICKLE_TIMER_IS_STOPPED
A trickle timer is considered &#39;stopped&#39; when i_cur == TRICKLE_TIMER_IS_STOPPED.
#define tt_rand()
Wide randoms for platforms using a 4-byte wide clock (see TRICKLE_TIMER_WIDE_RAND) ...
Definition: trickle-timer.c:66
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.
#define TRICKLE_TIMER_INTERVAL_END(tt)
Returns the current trickle interval&#39;s end (absolute time in ticks)
Default definitions of C compiler quirk work-arounds.
unsigned short random_rand(void)
Generates a new random number using the cc2538 RNG.
Definition: random.c:58
uint8_t c
c: Consistency Counter
uint8_t k
k: Redundancy Constant
#define TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max)
Checks whether Imin << Imax is unsuitable considering the boundaries of our platform&#39;s clock_time_t...