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/locator_getters.hpp"
39 #include "common/message.hpp"
40 #include "common/random.hpp"
41 #include "common/serial_number.hpp"
42 #include "instance/instance.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 ClearAllBytes(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>().GetMeshLocalRloc())
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,const OffsetRange & aOffsetRange,const Address & aAddress,bool & aReceive)93 Error Mpl::ProcessOption(Message &aMessage, const OffsetRange &aOffsetRange, const Address &aAddress, 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(aOffsetRange, &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(aOffsetRange, 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());
126 #endif
127 }
128 else if (!aMessage.IsOriginThreadNetif())
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
DetermineMaxRetransmissions(void) const314 uint8_t Mpl::DetermineMaxRetransmissions(void) const
315 {
316 uint8_t maxRetx = 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 maxRetx = kChildRetransmissions;
326 break;
327
328 case Mle::kRoleRouter:
329 case Mle::kRoleLeader:
330 maxRetx = kRouterRetransmissions;
331 break;
332 }
333
334 return maxRetx;
335 }
336
AddBufferedMessage(Message & aMessage,uint16_t aSeedId,uint8_t aSequence)337 void Mpl::AddBufferedMessage(Message &aMessage, uint16_t aSeedId, uint8_t aSequence)
338 {
339 Error error = kErrorNone;
340 Message *messageCopy = nullptr;
341 Metadata metadata;
342 uint8_t hopLimit = 0;
343 uint8_t interval;
344
345 #if OPENTHREAD_CONFIG_MPL_DYNAMIC_INTERVAL_ENABLE
346 // adjust the first MPL forward interval dynamically according to the network scale
347 interval = (kDataMessageInterval / Mle::kMaxRouters) * Get<RouterTable>().GetNeighborCount(kLinkQuality1);
348 #else
349 interval = kDataMessageInterval;
350 #endif
351
352 VerifyOrExit(DetermineMaxRetransmissions() > 0);
353 VerifyOrExit((messageCopy = aMessage.Clone()) != nullptr, error = kErrorNoBufs);
354
355 if (aMessage.IsOriginThreadNetif())
356 {
357 IgnoreError(aMessage.Read(Header::kHopLimitFieldOffset, hopLimit));
358 VerifyOrExit(hopLimit-- > 1, error = kErrorDrop);
359 messageCopy->Write(Header::kHopLimitFieldOffset, hopLimit);
360 }
361
362 // If the message originates from Thread Netif (i.e., it was
363 // received over Thread radio), set the `mTransmissionCount` to
364 // zero. Otherwise, the message originates from the host and will
365 // be forwarded by `Ip6` to the Thread mesh, so the message itself
366 // will be the first transmission and we set `mTransmissionCount`
367 // to one.
368
369 metadata.mSeedId = aSeedId;
370 metadata.mSequence = aSequence;
371 metadata.mTransmissionCount = aMessage.IsOriginThreadNetif() ? 0 : 1;
372 metadata.mIntervalOffset = 0;
373 metadata.GenerateNextTransmissionTime(TimerMilli::GetNow(), interval);
374
375 SuccessOrExit(error = metadata.AppendTo(*messageCopy));
376 mBufferedMessageSet.Enqueue(*messageCopy);
377
378 mRetransmissionTimer.FireAtIfEarlier(metadata.mTransmissionTime);
379
380 exit:
381 FreeMessageOnError(messageCopy, error);
382 }
383
HandleRetransmissionTimer(void)384 void Mpl::HandleRetransmissionTimer(void)
385 {
386 NextFireTime nextTime;
387
388 for (Message &message : mBufferedMessageSet)
389 {
390 Metadata metadata;
391 Message *messageCopy;
392 uint8_t maxRetx;
393
394 metadata.ReadFrom(message);
395
396 if (nextTime.GetNow() < metadata.mTransmissionTime)
397 {
398 nextTime.UpdateIfEarlier(metadata.mTransmissionTime);
399 continue;
400 }
401
402 metadata.mTransmissionCount++;
403
404 maxRetx = DetermineMaxRetransmissions();
405
406 if (metadata.mTransmissionCount > maxRetx)
407 {
408 // If the number of tx already exceeds the limit, remove
409 // the message. This situation can potentially happen on
410 // a device role change, which then updates the max MPL
411 // retx.
412
413 mBufferedMessageSet.DequeueAndFree(message);
414 continue;
415 }
416
417 if (metadata.mTransmissionCount < maxRetx)
418 {
419 metadata.GenerateNextTransmissionTime(nextTime.GetNow(), kDataMessageInterval);
420 metadata.UpdateIn(message);
421
422 nextTime.UpdateIfEarlier(metadata.mTransmissionTime);
423
424 messageCopy = message.Clone();
425 }
426 else
427 {
428 // This is the last retx of message, we can use the
429 // `message` directly.
430
431 mBufferedMessageSet.Dequeue(message);
432 messageCopy = &message;
433 }
434
435 if (messageCopy != nullptr)
436 {
437 if (metadata.mTransmissionCount > 1)
438 {
439 // Mark all transmissions after the first one as "MPL
440 // retx". This is used to decide whether to send this
441 // message to the device's sleepy children.
442
443 messageCopy->SetSubType(Message::kSubTypeMplRetransmission);
444 }
445
446 metadata.RemoveFrom(*messageCopy);
447 messageCopy->SetLoopbackToHostAllowed(true);
448 messageCopy->SetOrigin(Message::kOriginHostTrusted);
449 Get<Ip6>().EnqueueDatagram(*messageCopy);
450 }
451 }
452
453 mRetransmissionTimer.FireAt(nextTime);
454 }
455
ReadFrom(const Message & aMessage)456 void Mpl::Metadata::ReadFrom(const Message &aMessage)
457 {
458 uint16_t length = aMessage.GetLength();
459
460 OT_ASSERT(length >= sizeof(*this));
461 IgnoreError(aMessage.Read(length - sizeof(*this), *this));
462 }
463
RemoveFrom(Message & aMessage) const464 void Mpl::Metadata::RemoveFrom(Message &aMessage) const { aMessage.RemoveFooter(sizeof(*this)); }
465
UpdateIn(Message & aMessage) const466 void Mpl::Metadata::UpdateIn(Message &aMessage) const { aMessage.Write(aMessage.GetLength() - sizeof(*this), *this); }
467
GenerateNextTransmissionTime(TimeMilli aCurrentTime,uint8_t aInterval)468 void Mpl::Metadata::GenerateNextTransmissionTime(TimeMilli aCurrentTime, uint8_t aInterval)
469 {
470 // Emulate Trickle timer behavior and set up the next retransmission within [0,I) range.
471 uint8_t t = (aInterval == 0) ? aInterval : Random::NonCrypto::GetUint8InRange(0, aInterval);
472
473 // Set transmission time at the beginning of the next interval.
474 mTransmissionTime = aCurrentTime + static_cast<uint32_t>(mIntervalOffset + t);
475 mIntervalOffset = aInterval - t;
476 }
477
478 #endif // OPENTHREAD_FTD
479
480 } // namespace Ip6
481 } // namespace ot
482
