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 MPL.
32 */
33
34 #include "ip6_mpl.hpp"
35
36 #include "common/code_utils.hpp"
37 #include "common/debug.hpp"
38 #include "common/instance.hpp"
39 #include "common/locator_getters.hpp"
40 #include "common/message.hpp"
41 #include "common/random.hpp"
42 #include "common/serial_number.hpp"
43 #include "net/ip6.hpp"
44
45 namespace ot {
46 namespace Ip6 {
47
Mpl(Instance & aInstance)48 Mpl::Mpl(Instance &aInstance)
49 : InstanceLocator(aInstance)
50 , mSequence(0)
51 #if OPENTHREAD_FTD
52 , mRetransmissionTimer(aInstance)
53 #endif
54 {
55 memset(mSeedSet, 0, sizeof(mSeedSet));
56 }
57
Init(SeedIdLength aSeedIdLength)58 void MplOption::Init(SeedIdLength aSeedIdLength)
59 {
60 SetType(kType);
61
62 switch (aSeedIdLength)
63 {
64 case kSeedIdLength0:
65 SetLength(sizeof(*this) - sizeof(Option) - sizeof(mSeedId));
66 break;
67 case kSeedIdLength2:
68 SetLength(sizeof(*this) - sizeof(Option));
69 break;
70 default:
71 OT_ASSERT(false);
72 }
73
74 mControl = aSeedIdLength;
75 }
76
InitOption(MplOption & aOption,const Address & aAddress)77 void Mpl::InitOption(MplOption &aOption, const Address &aAddress)
78 {
79 if (aAddress == Get<Mle::Mle>().GetMeshLocal16())
80 {
81 // Seed ID can be elided when `aAddress` is RLOC.
82 aOption.Init(MplOption::kSeedIdLength0);
83 }
84 else
85 {
86 aOption.Init(MplOption::kSeedIdLength2);
87 aOption.SetSeedId(Get<Mle::Mle>().GetRloc16());
88 }
89
90 aOption.SetSequence(mSequence++);
91 }
92
ProcessOption(Message & aMessage,uint16_t aOffset,const Address & aAddress,bool aIsOutbound,bool & aReceive)93 Error Mpl::ProcessOption(Message &aMessage, uint16_t aOffset, const Address &aAddress, bool aIsOutbound, bool &aReceive)
94 {
95 Error error;
96 MplOption option;
97
98 // Read the min size bytes first, then check the expected
99 // `SeedIdLength` and read the full `MplOption` if needed.
100 SuccessOrExit(error = aMessage.Read(aOffset, &option, MplOption::kMinSize));
101
102 switch (option.GetSeedIdLength())
103 {
104 case MplOption::kSeedIdLength0:
105 // Retrieve Seed ID from the IPv6 Source Address RLOC.
106 VerifyOrExit(aAddress.GetIid().IsLocator(), error = kErrorDrop);
107 option.SetSeedId(aAddress.GetIid().GetLocator());
108 break;
109
110 case MplOption::kSeedIdLength2:
111 SuccessOrExit(error = aMessage.Read(aOffset, option));
112 break;
113
114 case MplOption::kSeedIdLength8:
115 case MplOption::kSeedIdLength16:
116 ExitNow(error = kErrorParse);
117 }
118
119 // Check if the MPL Data Message is new.
120 error = UpdateSeedSet(option.GetSeedId(), option.GetSequence());
121
122 if (error == kErrorNone)
123 {
124 #if OPENTHREAD_FTD
125 AddBufferedMessage(aMessage, option.GetSeedId(), option.GetSequence(), aIsOutbound);
126 #endif
127 }
128 else if (aIsOutbound)
129 {
130 aReceive = false;
131 // In case MPL Data Message is generated locally, ignore potential error of the MPL Seed Set
132 // to allow subsequent retransmissions with the same sequence number.
133 ExitNow(error = kErrorNone);
134 }
135
136 exit:
137 return error;
138 }
139
140 /*
141 * mSeedSet stores recently received (Seed ID, Sequence) values.
142 * - (Seed ID, Sequence) values are grouped by Seed ID.
143 * - (Seed ID, Sequence) groups are not sorted by Seed ID relative to other groups.
144 * - (Seed ID, Sequence) values within a group are sorted by Sequence.
145 * - All unused entries (marked by 0 lifetime) are grouped at the end.
146 *
147 * Update process:
148 *
149 * - Eviction selection:
150 * - If there are unused entries, mark the first unused entry for "eviction"
151 * - Otherwise, pick the first entry of the group that has the most entries.
152 *
153 * - Insert selection:
154 * - If there exists a group matching the Seed ID, select insert entry based on Sequence ordering.
155 * - Otherwise, set insert entry equal to evict entry.
156 *
157 * - If evicting a valid entry (lifetime non-zero):
158 * - Require group size to have >=2 entries.
159 * - If inserting into existing group, require Sequence to be larger than oldest stored Sequence in group.
160 */
UpdateSeedSet(uint16_t aSeedId,uint8_t aSequence)161 Error Mpl::UpdateSeedSet(uint16_t aSeedId, uint8_t aSequence)
162 {
163 Error error = kErrorNone;
164 SeedEntry *insert = nullptr;
165 SeedEntry *group = mSeedSet;
166 SeedEntry *evict = mSeedSet;
167 uint8_t curCount = 0;
168 uint8_t maxCount = 0;
169
170 for (uint32_t i = 0; i < kNumSeedEntries; i++, curCount++)
171 {
172 if (mSeedSet[i].mLifetime == 0)
173 {
174 // unused entries exist
175
176 if (insert == nullptr)
177 {
178 // no existing group, set insert and evict entry to be the same
179 insert = &mSeedSet[i];
180 }
181
182 // mark first unused entry for eviction
183 evict = &mSeedSet[i];
184 break;
185 }
186
187 if (mSeedSet[i].mSeedId != group->mSeedId)
188 {
189 // processing new group
190
191 if (aSeedId == group->mSeedId && insert == nullptr)
192 {
193 // insert at end of existing group
194 insert = &mSeedSet[i];
195 curCount++;
196 }
197
198 if (maxCount < curCount)
199 {
200 // look to evict an entry from the seed with the most entries
201 evict = group;
202 maxCount = curCount;
203 }
204
205 group = &mSeedSet[i];
206 curCount = 0;
207 }
208
209 if (aSeedId == mSeedSet[i].mSeedId)
210 {
211 // have existing entries for aSeedId
212
213 if (aSequence == mSeedSet[i].mSequence)
214 {
215 // already received, drop message
216
217 mSeedSet[i].mLifetime = kSeedEntryLifetime;
218 ExitNow(error = kErrorDrop);
219 }
220 else if (insert == nullptr && SerialNumber::IsLess(aSequence, mSeedSet[i].mSequence))
221 {
222 // insert in order of sequence
223 insert = &mSeedSet[i];
224 curCount++;
225 }
226 }
227 }
228
229 if (evict->mLifetime != 0)
230 {
231 // no free entries available, look to evict an existing entry
232 OT_ASSERT(curCount != 0);
233
234 if (aSeedId == group->mSeedId && insert == nullptr)
235 {
236 // insert at end of existing group
237 insert = &mSeedSet[kNumSeedEntries];
238 curCount++;
239 }
240
241 if (maxCount < curCount)
242 {
243 // look to evict an entry from the seed with the most entries
244 evict = group;
245 maxCount = curCount;
246 }
247
248 // require evict group size to have >= 2 entries
249 VerifyOrExit(maxCount > 1, error = kErrorDrop);
250
251 if (insert == nullptr)
252 {
253 // no existing entries for aSeedId
254 insert = evict;
255 }
256 else
257 {
258 // require Sequence to be larger than oldest stored Sequence in group
259 VerifyOrExit(insert > mSeedSet && aSeedId == (insert - 1)->mSeedId, error = kErrorDrop);
260 }
261 }
262
263 if (evict > insert)
264 {
265 OT_ASSERT(insert >= mSeedSet);
266 memmove(insert + 1, insert, static_cast<size_t>(evict - insert) * sizeof(SeedEntry));
267 }
268 else if (evict < insert)
269 {
270 OT_ASSERT(evict >= mSeedSet);
271 memmove(evict, evict + 1, static_cast<size_t>(insert - 1 - evict) * sizeof(SeedEntry));
272 insert--;
273 }
274
275 insert->mSeedId = aSeedId;
276 insert->mSequence = aSequence;
277 insert->mLifetime = kSeedEntryLifetime;
278
279 Get<TimeTicker>().RegisterReceiver(TimeTicker::kIp6Mpl);
280
281 exit:
282 return error;
283 }
284
HandleTimeTick(void)285 void Mpl::HandleTimeTick(void)
286 {
287 bool continueRxingTicks = false;
288 int j = 0;
289
290 for (int i = 0; i < kNumSeedEntries && mSeedSet[i].mLifetime; i++)
291 {
292 mSeedSet[i].mLifetime--;
293
294 if (mSeedSet[i].mLifetime > 0)
295 {
296 mSeedSet[j++] = mSeedSet[i];
297 continueRxingTicks = true;
298 }
299 }
300
301 for (; j < kNumSeedEntries && mSeedSet[j].mLifetime; j++)
302 {
303 mSeedSet[j].mLifetime = 0;
304 }
305
306 if (!continueRxingTicks)
307 {
308 Get<TimeTicker>().UnregisterReceiver(TimeTicker::kIp6Mpl);
309 }
310 }
311
312 #if OPENTHREAD_FTD
313
GetTimerExpirations(void) const314 uint8_t Mpl::GetTimerExpirations(void) const
315 {
316 uint8_t timerExpirations = 0;
317
318 switch (Get<Mle::Mle>().GetRole())
319 {
320 case Mle::kRoleDisabled:
321 case Mle::kRoleDetached:
322 break;
323
324 case Mle::kRoleChild:
325 timerExpirations = kChildTimerExpirations;
326 break;
327
328 case Mle::kRoleRouter:
329 case Mle::kRoleLeader:
330 timerExpirations = kRouterTimerExpirations;
331 break;
332 }
333
334 return timerExpirations;
335 }
336
AddBufferedMessage(Message & aMessage,uint16_t aSeedId,uint8_t aSequence,bool aIsOutbound)337 void Mpl::AddBufferedMessage(Message &aMessage, uint16_t aSeedId, uint8_t aSequence, bool aIsOutbound)
338 {
339 Error error = kErrorNone;
340 Message *messageCopy = nullptr;
341 Metadata metadata;
342 uint8_t hopLimit = 0;
343
344 #if OPENTHREAD_CONFIG_MPL_DYNAMIC_INTERVAL_ENABLE
345 // adjust the first MPL forward interval dynamically according to the network scale
346 uint8_t interval = (kDataMessageInterval / Mle::kMaxRouters) * Get<RouterTable>().GetNeighborCount();
347 #else
348 uint8_t interval = kDataMessageInterval;
349 #endif
350
351 VerifyOrExit(GetTimerExpirations() > 0);
352 VerifyOrExit((messageCopy = aMessage.Clone()) != nullptr, error = kErrorNoBufs);
353
354 if (!aIsOutbound)
355 {
356 IgnoreError(aMessage.Read(Header::kHopLimitFieldOffset, hopLimit));
357 VerifyOrExit(hopLimit-- > 1, error = kErrorDrop);
358 messageCopy->Write(Header::kHopLimitFieldOffset, hopLimit);
359 }
360
361 metadata.mSeedId = aSeedId;
362 metadata.mSequence = aSequence;
363 metadata.mTransmissionCount = aIsOutbound ? 1 : 0;
364 metadata.mIntervalOffset = 0;
365 metadata.GenerateNextTransmissionTime(TimerMilli::GetNow(), interval);
366
367 SuccessOrExit(error = metadata.AppendTo(*messageCopy));
368 mBufferedMessageSet.Enqueue(*messageCopy);
369
370 mRetransmissionTimer.FireAtIfEarlier(metadata.mTransmissionTime);
371
372 exit:
373 FreeMessageOnError(messageCopy, error);
374 }
375
HandleRetransmissionTimer(void)376 void Mpl::HandleRetransmissionTimer(void)
377 {
378 TimeMilli now = TimerMilli::GetNow();
379 TimeMilli nextTime = now.GetDistantFuture();
380 Metadata metadata;
381
382 for (Message &message : mBufferedMessageSet)
383 {
384 metadata.ReadFrom(message);
385
386 if (now < metadata.mTransmissionTime)
387 {
388 nextTime = Min(nextTime, metadata.mTransmissionTime);
389 }
390 else
391 {
392 uint8_t timerExpirations = GetTimerExpirations();
393
394 // Update the number of transmission timer expirations.
395 metadata.mTransmissionCount++;
396
397 if (metadata.mTransmissionCount < timerExpirations)
398 {
399 Message *messageCopy = message.Clone(message.GetLength() - sizeof(Metadata));
400
401 if (messageCopy != nullptr)
402 {
403 if (metadata.mTransmissionCount > 1)
404 {
405 messageCopy->SetSubType(Message::kSubTypeMplRetransmission);
406 }
407
408 Get<Ip6>().EnqueueDatagram(*messageCopy);
409 }
410
411 metadata.GenerateNextTransmissionTime(now, kDataMessageInterval);
412 metadata.UpdateIn(message);
413
414 nextTime = Min(nextTime, metadata.mTransmissionTime);
415 }
416 else
417 {
418 mBufferedMessageSet.Dequeue(message);
419
420 if (metadata.mTransmissionCount == timerExpirations)
421 {
422 if (metadata.mTransmissionCount > 1)
423 {
424 message.SetSubType(Message::kSubTypeMplRetransmission);
425 }
426
427 metadata.RemoveFrom(message);
428 Get<Ip6>().EnqueueDatagram(message);
429 }
430 else
431 {
432 // Stop retransmitting if the number of timer expirations is already exceeded.
433 message.Free();
434 }
435 }
436 }
437 }
438
439 if (nextTime < now.GetDistantFuture())
440 {
441 mRetransmissionTimer.FireAt(nextTime);
442 }
443 }
444
ReadFrom(const Message & aMessage)445 void Mpl::Metadata::ReadFrom(const Message &aMessage)
446 {
447 uint16_t length = aMessage.GetLength();
448
449 OT_ASSERT(length >= sizeof(*this));
450 IgnoreError(aMessage.Read(length - sizeof(*this), *this));
451 }
452
RemoveFrom(Message & aMessage) const453 void Mpl::Metadata::RemoveFrom(Message &aMessage) const
454 {
455 SuccessOrAssert(aMessage.SetLength(aMessage.GetLength() - sizeof(*this)));
456 }
457
UpdateIn(Message & aMessage) const458 void Mpl::Metadata::UpdateIn(Message &aMessage) const { aMessage.Write(aMessage.GetLength() - sizeof(*this), *this); }
459
GenerateNextTransmissionTime(TimeMilli aCurrentTime,uint8_t aInterval)460 void Mpl::Metadata::GenerateNextTransmissionTime(TimeMilli aCurrentTime, uint8_t aInterval)
461 {
462 // Emulate Trickle timer behavior and set up the next retransmission within [0,I) range.
463 uint8_t t = (aInterval == 0) ? aInterval : Random::NonCrypto::GetUint8InRange(0, aInterval);
464
465 // Set transmission time at the beginning of the next interval.
466 mTransmissionTime = aCurrentTime + static_cast<uint32_t>(mIntervalOffset + t);
467 mIntervalOffset = aInterval - t;
468 }
469
470 #endif // OPENTHREAD_FTD
471
472 } // namespace Ip6
473 } // namespace ot
474
