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