1 /*
2 * Copyright (c) 2016, The OpenThread Authors.
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 are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Neither the name of the copyright holder nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /**
30 * @file
31 * This file implements the trickle timer logic.
32 */
33
34 #include "trickle_timer.hpp"
35
36 #include "common/code_utils.hpp"
37 #include "common/debug.hpp"
38 #include "common/num_utils.hpp"
39 #include "common/random.hpp"
40
41 namespace ot {
42
TrickleTimer(Instance & aInstance,Handler aHandler)43 TrickleTimer::TrickleTimer(Instance &aInstance, Handler aHandler)
44 : TimerMilli(aInstance, TrickleTimer::HandleTimer)
45 , mIntervalMin(0)
46 , mIntervalMax(0)
47 , mInterval(0)
48 , mTimeInInterval(0)
49 , mRedundancyConstant(0)
50 , mCounter(0)
51 , mHandler(aHandler)
52 , mMode(kModeTrickle)
53 , mPhase(kBeforeRandomTime)
54 {
55 }
56
GetStartTimeOfCurrentInterval(void) const57 TimeMilli TrickleTimer::GetStartTimeOfCurrentInterval(void) const
58 {
59 // Determines and returns the start time of the current
60 // interval.
61
62 TimeMilli startTime = TimerMilli::GetFireTime();
63
64 if (mMode == kModePlainTimer)
65 {
66 startTime -= mInterval;
67 ExitNow();
68 }
69
70 switch (mPhase)
71 {
72 case kBeforeRandomTime:
73 startTime -= mTimeInInterval;
74 break;
75
76 case kAfterRandomTime:
77 startTime -= mInterval;
78 break;
79 }
80
81 exit:
82 return startTime;
83 }
84
SetIntervalMin(uint32_t aIntervalMin)85 void TrickleTimer::SetIntervalMin(uint32_t aIntervalMin)
86 {
87 VerifyOrExit(IsRunning());
88
89 mIntervalMin = aIntervalMin;
90
91 if (mIntervalMax < mIntervalMin)
92 {
93 SetIntervalMax(mIntervalMin);
94 }
95
96 exit:
97 return;
98 }
99
SetIntervalMax(uint32_t aIntervalMax)100 void TrickleTimer::SetIntervalMax(uint32_t aIntervalMax)
101 {
102 TimeMilli endOfInterval;
103
104 VerifyOrExit(IsRunning());
105
106 aIntervalMax = Max(mIntervalMin, aIntervalMax);
107 VerifyOrExit(aIntervalMax != mIntervalMax);
108
109 mIntervalMax = aIntervalMax;
110
111 // If the new `aIntervalMax` is greater than the current
112 // `mInterval`, no action is needed. The new `aIntervalMax` will be
113 // used as the `mInterval` grows.
114
115 VerifyOrExit(mIntervalMax < mInterval);
116
117 // Determine the end of the interval as if the new and shorter
118 // `mIntervalMax` would have been used. The calculated time may
119 // be in the past. In this case, `FireAt(endOfInterval)` will
120 // cause the timer to fire immediately.
121
122 endOfInterval = GetStartTimeOfCurrentInterval() + mIntervalMax;
123
124 if (mMode == kModePlainTimer)
125 {
126 TimerMilli::FireAt(endOfInterval);
127 ExitNow();
128 }
129
130 // Trickle mode possible scenarios:
131 //
132 // We are in `kBeforeRandomTime` phase.
133 //
134 // a) If the new `aIntervalMax < mTimeInInterval`:
135 // - Reschedule the timer to fire at new `endOfInterval`
136 // (which may fire immediately).
137 // - Set `mTimeInInterval = aIntervalMax`
138 // - Set `mInterval` to use the shorter `aIntervalMax`.
139 //
140 // |<---- mInterval ----------------^------------------>|
141 // |<---- mTimeInInterval ----------^---->| |
142 // |<---- aIntervalMax -------->| ^ | |
143 // | | now | |
144 //
145 // b) If the new `aIntervalMax >= mTimeInInterval`:
146 // - Keep timer unchanged to fire at `mTimeInInterval`
147 // - Keep `mTimeInInterval` unchanged.
148 // - Set `mInterval` to use the shorter `aIntervalMax`.
149 //
150 // |<---- mInterval ----------------^------------------>|
151 // |<---- mTimeInInterval ----------^---->| | |
152 // |<---- aIntervalMax -------------^--------->| |
153 // | now | |
154 //
155 // We are in `kAfterRandomTime` phase.
156 //
157 // c) If the new `aIntervalMax < mTimeInInterval`:
158 // - Act as if current interval is already finished.
159 // - Reschedule the timer to fire at new `endOfInterval`
160 // (which should fire immediately).
161 // - Set `mInterval` to use the shorter `aIntervalMax`.
162 // - The `mTimeInInterval` value does not matter as we
163 // are in `kAfterRandomTime` phase. Keep it unchanged.
164 //
165 // |<---- mInterval ---------------------------^------->|
166 // |<---- mTimeInInterval --------------->| ^ |
167 // |<---- aIntervalMax -------->| | ^ |
168 // | | | now |
169 //
170 // d) If the new `aIntervalMax >= mTimeInInterval`:
171 // - Reschedule the timer to fire at new `endOfInterval`
172 // - Set `mInterval` to use the shorter `aIntervalMax`.
173 // - The `mTimeInInterval` value does not matter as we
174 // are in `kAfterRandomTime` phase. Keep it unchanged.
175 //
176 // |<---- mInterval ---------------------------^------->|
177 // |<---- mTimeInInterval --------------->| ^ | |
178 // |<---- aIntervalMax ------------------------^-->| |
179 // | | now | |
180
181 // In all cases we need to set `mInterval` to the new
182 // shorter `aIntervalMax`.
183
184 mInterval = aIntervalMax;
185
186 switch (mPhase)
187 {
188 case kBeforeRandomTime:
189 if (aIntervalMax < mTimeInInterval)
190 {
191 mTimeInInterval = aIntervalMax;
192 }
193 else
194 {
195 break;
196 }
197
198 OT_FALL_THROUGH;
199
200 case kAfterRandomTime:
201 TimerMilli::FireAt(endOfInterval);
202 break;
203 }
204
205 exit:
206 return;
207 }
208
Start(Mode aMode,uint32_t aIntervalMin,uint32_t aIntervalMax,uint16_t aRedundancyConstant)209 void TrickleTimer::Start(Mode aMode, uint32_t aIntervalMin, uint32_t aIntervalMax, uint16_t aRedundancyConstant)
210 {
211 OT_ASSERT((aIntervalMax >= aIntervalMin) && (aIntervalMin > 0));
212
213 mIntervalMin = aIntervalMin;
214 mIntervalMax = aIntervalMax;
215 mRedundancyConstant = aRedundancyConstant;
216 mMode = aMode;
217
218 // Select interval randomly from range [Imin, Imax].
219 mInterval = Random::NonCrypto::GetUint32InRange(mIntervalMin, mIntervalMax + 1);
220
221 StartNewInterval();
222 }
223
IndicateConsistent(void)224 void TrickleTimer::IndicateConsistent(void)
225 {
226 if (mCounter < kInfiniteRedundancyConstant)
227 {
228 mCounter++;
229 }
230 }
231
IndicateInconsistent(void)232 void TrickleTimer::IndicateInconsistent(void)
233 {
234 VerifyOrExit(mMode == kModeTrickle);
235
236 // If interval is equal to minimum when an "inconsistent" event
237 // is received, do nothing.
238
239 VerifyOrExit(IsRunning() && (mInterval != mIntervalMin));
240
241 mInterval = mIntervalMin;
242 StartNewInterval();
243
244 exit:
245 return;
246 }
247
StartNewInterval(void)248 void TrickleTimer::StartNewInterval(void)
249 {
250 uint32_t halfInterval;
251
252 switch (mMode)
253 {
254 case kModePlainTimer:
255 mTimeInInterval = mInterval;
256 break;
257
258 case kModeTrickle:
259 // Select a random point in the interval taken from the range [I/2, I).
260 halfInterval = mInterval / 2;
261 mTimeInInterval =
262 (halfInterval < mInterval) ? Random::NonCrypto::GetUint32InRange(halfInterval, mInterval) : halfInterval;
263 mCounter = 0;
264 mPhase = kBeforeRandomTime;
265 break;
266 }
267
268 TimerMilli::Start(mTimeInInterval);
269 }
270
HandleTimer(Timer & aTimer)271 void TrickleTimer::HandleTimer(Timer &aTimer) { static_cast<TrickleTimer *>(&aTimer)->HandleTimer(); }
272
HandleTimer(void)273 void TrickleTimer::HandleTimer(void)
274 {
275 switch (mMode)
276 {
277 case kModePlainTimer:
278 mInterval = Random::NonCrypto::GetUint32InRange(mIntervalMin, mIntervalMax + 1);
279 StartNewInterval();
280 break;
281
282 case kModeTrickle:
283 switch (mPhase)
284 {
285 case kBeforeRandomTime:
286 // We reached end of random `mTimeInInterval` (aka `t`)
287 // within the current interval. Trickle timer invokes
288 // handler if and only if the counter is less than the
289 // redundancy constant.
290
291 mPhase = kAfterRandomTime;
292 TimerMilli::Start(mInterval - mTimeInInterval);
293 VerifyOrExit(mCounter < mRedundancyConstant);
294 break;
295
296 case kAfterRandomTime:
297 // Interval has expired. Double the interval length and
298 // ensure result is below max.
299
300 if (mInterval == 0)
301 {
302 mInterval = 1;
303 }
304 else if (mInterval <= mIntervalMax - mInterval)
305 {
306 mInterval *= 2;
307 }
308 else
309 {
310 mInterval = mIntervalMax;
311 }
312
313 StartNewInterval();
314 ExitNow(); // Exit so to not call `mHandler`
315 }
316
317 break;
318 }
319
320 mHandler(*this);
321
322 exit:
323 return;
324 }
325
326 } // namespace ot
327
