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/*---------------------------------------------------------------------------*/
71static struct trickle_timer *loctt; /* Pointer to a struct for local use */
72static clock_time_t loc_clock; /* A local, general-purpose placeholder */
73
74static void fire(void *ptr);
75static 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 */
81static uint32_t
82wide_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
97static uint8_t
98max_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) */
157static clock_time_t
158get_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/*---------------------------------------------------------------------------*/
168static void
169schedule_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 */
191static void
192double_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 */
259static void
260fire(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. */
287static void
288new_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/*---------------------------------------------------------------------------*/
307void
309{
311 return;
312 }
313 if(tt->c < 0xFF) {
314 tt->c++;
315 }
316 PRINTF("trickle_timer consistency: c=%u\n", tt->c);
317}
318/*---------------------------------------------------------------------------*/
319void
321{
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/*---------------------------------------------------------------------------*/
335uint8_t
336trickle_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 */
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 */
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/*---------------------------------------------------------------------------*/
384uint8_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/** @} */
Default definitions of C compiler quirk work-arounds.
Header file for the callback timer.
clock_time_t clock_time(void)
Get the current clock time.
Definition: clock.c:118
unsigned short random_rand(void)
Generates a new random number using the cc2538 RNG.
Definition: random.c:58
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_INTERVAL_MAX(tt)
Returns a timer's maximum interval size (Imin << Imax) as a number of clock ticks.
#define TRICKLE_TIMER_PROTO_TX_ALLOW(tt)
Determines whether the protocol must go ahead with a transmission.
void(* trickle_timer_cb_t)(void *ptr, uint8_t suppress)
typedef for a callback function to be defined in the protocol's implementation.
#define TRICKLE_TIMER_IS_STOPPED
A trickle timer is considered 'stopped' when i_cur == TRICKLE_TIMER_IS_STOPPED.
#define TRICKLE_TIMER_IMIN_IS_BAD(imin)
Checks whether an Imin value is invalid considering the various restrictions imposed by our platform'...
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.
uint8_t trickle_timer_set(struct trickle_timer *tt, trickle_timer_cb_t proto_cb, void *ptr)
Start a previously configured trickle timer.
#define trickle_timer_is_running(tt)
To be called in order to determine whether a trickle timer is running.
#define TRICKLE_TIMER_IPAIR_IS_BAD(i_min, i_max)
Checks whether Imin << Imax is unsuitable considering the boundaries of our platform's clock_time_t.
#define TRICKLE_TIMER_CLOCK_MAX
cross-platform method to get the maximum clock_time_t value
void trickle_timer_inconsistency(struct trickle_timer *tt)
To be called by the protocol when it hears an inconsistent transmission.
#define TRICKLE_TIMER_INTERVAL_END(tt)
Returns the current trickle interval's end (absolute time in ticks)
#define tt_rand()
Wide randoms for platforms using a 4-byte wide clock (see TRICKLE_TIMER_WIDE_RAND)
Definition: trickle-timer.c:66
void trickle_timer_consistency(struct trickle_timer *tt)
To be called by the protocol when it hears a consistent transmission.
A trickle timer.
uint8_t c
c: Consistency Counter
void * cb_arg
Opaque pointer to be used as the argument of the protocol's callback.
clock_time_t i_cur
I: Current interval in clock_ticks.
uint8_t i_max
Imax: Max number of doublings.
clock_time_t i_max_abs
Maximum interval size in clock ticks (and not in number of doublings).
uint8_t k
k: Redundancy Constant
trickle_timer_cb_t cb
Protocol's own callback, invoked at time t within the current interval.
struct ctimer ct
A Callback timer used internally.
clock_time_t i_min
Imin: Clock ticks.
clock_time_t i_start
Start of this interval (absolute clock_time)
Trickle timer library header file.