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 #include <stdarg.h>
30 
31 #include "common/debug.hpp"
32 #include "common/message.hpp"
33 #include "instance/instance.hpp"
34 
35 #include "test_platform.h"
36 #include "test_util.h"
37 
38 namespace ot {
39 
40 #define kNumNewPriorityTestMessages 2
41 #define kNumSetPriorityTestMessages 2
42 #define kNumTestMessages (kNumNewPriorityTestMessages + kNumSetPriorityTestMessages)
43 
44 // This function verifies the content of the priority queue to match the passed in messages
VerifyPriorityQueueContent(PriorityQueue & aPriorityQueue,int aExpectedLength,...)45 void VerifyPriorityQueueContent(PriorityQueue &aPriorityQueue, int aExpectedLength, ...)
46 {
47     const PriorityQueue &constQueue = aPriorityQueue;
48     va_list              args;
49     Message             *message;
50     Message             *msgArg;
51     int8_t               curPriority = Message::kNumPriorities;
52     PriorityQueue::Info  info;
53 
54     // Check the `GetInfo`
55     memset(&info, 0, sizeof(info));
56     aPriorityQueue.GetInfo(info);
57     VerifyOrQuit(info.mNumMessages == aExpectedLength, "GetInfo() result does not match expected len.");
58 
59     va_start(args, aExpectedLength);
60 
61     if (aExpectedLength == 0)
62     {
63         message = aPriorityQueue.GetHead();
64         VerifyOrQuit(message == nullptr, "PriorityQueue is not empty when expected len is zero.");
65 
66         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(Message::kPriorityLow) == nullptr);
67         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(Message::kPriorityNormal) == nullptr);
68         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(Message::kPriorityHigh) == nullptr);
69         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(Message::kPriorityNet) == nullptr);
70     }
71     else
72     {
73         // Go through all messages in the queue and verify they match the passed-in messages
74         for (message = aPriorityQueue.GetHead(); message != nullptr; message = message->GetNext())
75         {
76             VerifyOrQuit(aExpectedLength != 0, "PriorityQueue contains more entries than expected.");
77 
78             msgArg = va_arg(args, Message *);
79 
80             if (msgArg->GetPriority() != curPriority)
81             {
82                 for (curPriority--; curPriority != msgArg->GetPriority(); curPriority--)
83                 {
84                     // Check the `GetHeadForPriority` is nullptr if there are no expected message for this priority
85                     // level.
86                     VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<Message::Priority>(curPriority)) ==
87                                      nullptr,
88                                  "is non-nullptr when no expected msg for this priority.");
89                 }
90 
91                 // Check the `GetHeadForPriority`.
92                 VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<Message::Priority>(curPriority)) == msgArg);
93             }
94 
95             // Check the queued message to match the one from argument list
96             VerifyOrQuit(msgArg == message, "PriorityQueue content does not match what is expected.");
97 
98             aExpectedLength--;
99         }
100 
101         VerifyOrQuit(aExpectedLength == 0, "PriorityQueue contains less entries than expected.");
102 
103         // Check the `GetHeadForPriority` is nullptr if there are no expected message for any remaining priority level.
104         for (curPriority--; curPriority >= 0; curPriority--)
105         {
106             VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<Message::Priority>(curPriority)) == nullptr,
107                          "is non-nullptr when no expected msg for this priority.");
108         }
109     }
110 
111     va_end(args);
112 
113     // Check range-based `for` loop iteration using non-const iterator
114 
115     message = aPriorityQueue.GetHead();
116 
117     for (Message &msg : aPriorityQueue)
118     {
119         VerifyOrQuit(message == &msg, "`for` loop iteration does not match expected");
120         message = message->GetNext();
121     }
122 
123     VerifyOrQuit(message == nullptr, "`for` loop iteration resulted in fewer entries than expected");
124 
125     // Check  range-base `for` iteration using const iterator
126 
127     message = aPriorityQueue.GetHead();
128 
129     for (const Message &constMsg : constQueue)
130     {
131         VerifyOrQuit(message == &constMsg, "`for` loop iteration does not match expected");
132         message = message->GetNext();
133     }
134 
135     VerifyOrQuit(message == nullptr, "`for` loop iteration resulted in fewer entries than expected");
136 }
137 
138 // This function verifies the content of the message queue to match the passed in messages
VerifyMsgQueueContent(MessageQueue & aMessageQueue,int aExpectedLength,...)139 void VerifyMsgQueueContent(MessageQueue &aMessageQueue, int aExpectedLength, ...)
140 {
141     va_list  args;
142     Message *message;
143     Message *msgArg;
144 
145     va_start(args, aExpectedLength);
146 
147     if (aExpectedLength == 0)
148     {
149         message = aMessageQueue.GetHead();
150         VerifyOrQuit(message == nullptr, "is not empty when expected len is zero.");
151     }
152     else
153     {
154         for (message = aMessageQueue.GetHead(); message != nullptr; message = message->GetNext())
155         {
156             VerifyOrQuit(aExpectedLength != 0, "contains more entries than expected");
157 
158             msgArg = va_arg(args, Message *);
159             VerifyOrQuit(msgArg == message, "content does not match what is expected.");
160 
161             aExpectedLength--;
162         }
163 
164         VerifyOrQuit(aExpectedLength == 0, "contains less entries than expected");
165     }
166 
167     va_end(args);
168 }
169 
TestPriorityQueue(void)170 void TestPriorityQueue(void)
171 {
172     Instance     *instance;
173     MessagePool  *messagePool;
174     PriorityQueue queue;
175     MessageQueue  messageQueue;
176     Message      *msgNet[kNumTestMessages];
177     Message      *msgHigh[kNumTestMessages];
178     Message      *msgNor[kNumTestMessages];
179     Message      *msgLow[kNumTestMessages];
180 
181     instance = testInitInstance();
182     VerifyOrQuit(instance != nullptr, "Null OpenThread instance");
183 
184     messagePool = &instance->Get<MessagePool>();
185 
186     // Use the function "Allocate()" to allocate messages with different priorities
187     for (int i = 0; i < kNumNewPriorityTestMessages; i++)
188     {
189         msgNet[i] = messagePool->Allocate(Message::kTypeIp6, 0, Message::Settings(Message::kPriorityNet));
190         VerifyOrQuit(msgNet[i] != nullptr);
191         msgHigh[i] = messagePool->Allocate(Message::kTypeIp6, 0, Message::Settings(Message::kPriorityHigh));
192         VerifyOrQuit(msgHigh[i] != nullptr);
193         msgNor[i] = messagePool->Allocate(Message::kTypeIp6, 0, Message::Settings(Message::kPriorityNormal));
194         VerifyOrQuit(msgNor[i] != nullptr);
195         msgLow[i] = messagePool->Allocate(Message::kTypeIp6, 0, Message::Settings(Message::kPriorityLow));
196         VerifyOrQuit(msgLow[i] != nullptr);
197     }
198 
199     // Use the function "SetPriority()" to allocate messages with different priorities
200     for (int i = kNumNewPriorityTestMessages; i < kNumTestMessages; i++)
201     {
202         msgNet[i] = messagePool->Allocate(Message::kTypeIp6);
203         VerifyOrQuit(msgNet[i] != nullptr);
204         SuccessOrQuit(msgNet[i]->SetPriority(Message::kPriorityNet));
205         msgHigh[i] = messagePool->Allocate(Message::kTypeIp6);
206         VerifyOrQuit(msgHigh[i] != nullptr);
207         SuccessOrQuit(msgHigh[i]->SetPriority(Message::kPriorityHigh));
208         msgNor[i] = messagePool->Allocate(Message::kTypeIp6);
209         VerifyOrQuit(msgNor[i] != nullptr);
210         SuccessOrQuit(msgNor[i]->SetPriority(Message::kPriorityNormal));
211         msgLow[i] = messagePool->Allocate(Message::kTypeIp6);
212         VerifyOrQuit(msgLow[i] != nullptr);
213         SuccessOrQuit(msgLow[i]->SetPriority(Message::kPriorityLow));
214     }
215 
216     // Check the `GetPriority()`
217     for (int i = 0; i < kNumTestMessages; i++)
218     {
219         VerifyOrQuit(msgLow[i]->GetPriority() == Message::kPriorityLow);
220         VerifyOrQuit(msgNor[i]->GetPriority() == Message::kPriorityNormal);
221         VerifyOrQuit(msgHigh[i]->GetPriority() == Message::kPriorityHigh);
222         VerifyOrQuit(msgNet[i]->GetPriority() == Message::kPriorityNet);
223     }
224 
225     // Verify case of an empty queue.
226     VerifyPriorityQueueContent(queue, 0);
227 
228     // Add msgs in different orders and check the content of queue.
229     queue.Enqueue(*msgHigh[0]);
230     VerifyPriorityQueueContent(queue, 1, msgHigh[0]);
231     queue.Enqueue(*msgHigh[1]);
232     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgHigh[1]);
233     queue.Enqueue(*msgNet[0]);
234     VerifyPriorityQueueContent(queue, 3, msgNet[0], msgHigh[0], msgHigh[1]);
235     queue.Enqueue(*msgNet[1]);
236     VerifyPriorityQueueContent(queue, 4, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1]);
237     queue.Enqueue(*msgHigh[2]);
238     VerifyPriorityQueueContent(queue, 5, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2]);
239     queue.Enqueue(*msgLow[0]);
240     VerifyPriorityQueueContent(queue, 6, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgLow[0]);
241     queue.Enqueue(*msgNor[0]);
242     VerifyPriorityQueueContent(queue, 7, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgNor[0],
243                                msgLow[0]);
244     queue.Enqueue(*msgHigh[3]);
245     VerifyPriorityQueueContent(queue, 8, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgHigh[3],
246                                msgNor[0], msgLow[0]);
247 
248     // Remove messages in different order and check the content of queue in each step.
249     queue.Dequeue(*msgNet[0]);
250     VerifyPriorityQueueContent(queue, 7, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgHigh[3], msgNor[0],
251                                msgLow[0]);
252     queue.Dequeue(*msgHigh[2]);
253     VerifyPriorityQueueContent(queue, 6, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[3], msgNor[0], msgLow[0]);
254     queue.Dequeue(*msgNor[0]);
255     VerifyPriorityQueueContent(queue, 5, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[3], msgLow[0]);
256     queue.Dequeue(*msgHigh[1]);
257     VerifyPriorityQueueContent(queue, 4, msgNet[1], msgHigh[0], msgHigh[3], msgLow[0]);
258     queue.Dequeue(*msgLow[0]);
259     VerifyPriorityQueueContent(queue, 3, msgNet[1], msgHigh[0], msgHigh[3]);
260     queue.Dequeue(*msgNet[1]);
261     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgHigh[3]);
262     queue.Dequeue(*msgHigh[0]);
263     VerifyPriorityQueueContent(queue, 1, msgHigh[3]);
264     queue.Dequeue(*msgHigh[3]);
265     VerifyPriorityQueueContent(queue, 0);
266 
267     // Change the priority of an already queued message and check the order change in the queue.
268     queue.Enqueue(*msgNor[0]);
269     VerifyPriorityQueueContent(queue, 1, msgNor[0]);
270     queue.Enqueue(*msgHigh[0]);
271     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgNor[0]);
272     queue.Enqueue(*msgLow[0]);
273     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgNor[0], msgLow[0]);
274 
275     SuccessOrQuit(msgNor[0]->SetPriority(Message::kPriorityNet));
276     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
277     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityLow));
278     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
279     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityNormal));
280     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
281     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityHigh));
282     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
283     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityNet));
284     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgLow[0], msgHigh[0]);
285     SuccessOrQuit(msgNor[0]->SetPriority(Message::kPriorityNormal));
286     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityLow));
287     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgNor[0], msgLow[0]);
288 
289     messageQueue.Enqueue(*msgNor[1]);
290     messageQueue.Enqueue(*msgHigh[1]);
291     messageQueue.Enqueue(*msgNet[1]);
292     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
293 
294     // Change priority of message and check for not in messageQueue.
295     SuccessOrQuit(msgNor[1]->SetPriority(Message::kPriorityNet));
296     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
297 
298     SuccessOrQuit(msgLow[0]->SetPriority(Message::kPriorityHigh));
299     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgLow[0], msgNor[0]);
300     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
301 
302     // Remove messages from the two queues
303     queue.Dequeue(*msgHigh[0]);
304     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
305     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
306 
307     messageQueue.Dequeue(*msgNet[1]);
308     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
309     VerifyMsgQueueContent(messageQueue, 2, msgNor[1], msgHigh[1]);
310 
311     messageQueue.Dequeue(*msgHigh[1]);
312     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
313     VerifyMsgQueueContent(messageQueue, 1, msgNor[1]);
314 
315     queue.Dequeue(*msgLow[0]);
316     VerifyPriorityQueueContent(queue, 1, msgNor[0]);
317     VerifyMsgQueueContent(messageQueue, 1, msgNor[1]);
318 
319     queue.Dequeue(*msgNor[0]);
320     VerifyPriorityQueueContent(queue, 0);
321     messageQueue.Dequeue(*msgNor[1]);
322     VerifyMsgQueueContent(messageQueue, 0);
323 
324     for (Message *message : msgNor)
325     {
326         SuccessOrQuit(message->SetPriority(Message::kPriorityNormal));
327     }
328 
329     // Range-based `for` and dequeue during iteration
330 
331     for (uint16_t removeIndex = 0; removeIndex < 4; removeIndex++)
332     {
333         uint16_t index = 0;
334 
335         queue.Enqueue(*msgNor[0]);
336         queue.Enqueue(*msgNor[1]);
337         queue.Enqueue(*msgNor[2]);
338         queue.Enqueue(*msgNor[3]);
339         VerifyPriorityQueueContent(queue, 4, msgNor[0], msgNor[1], msgNor[2], msgNor[3]);
340 
341         // While iterating over the queue remove the entry at `removeIndex`
342         for (Message &message : queue)
343         {
344             if (index == removeIndex)
345             {
346                 queue.Dequeue(message);
347             }
348 
349             VerifyOrQuit(&message == msgNor[index++]);
350         }
351 
352         index = 0;
353 
354         // Iterate over the queue and remove all
355         for (Message &message : queue)
356         {
357             if (index == removeIndex)
358             {
359                 index++;
360             }
361 
362             VerifyOrQuit(&message == msgNor[index++]);
363             queue.Dequeue(message);
364         }
365 
366         VerifyPriorityQueueContent(queue, 0);
367     }
368 
369     testFreeInstance(instance);
370 }
371 
372 } // namespace ot
373 
main(void)374 int main(void)
375 {
376     ot::TestPriorityQueue();
377     printf("All tests passed\n");
378     return 0;
379 }
380