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/instance.hpp"
33 #include "common/message.hpp"
34 
35 #include "test_platform.h"
36 #include "test_util.h"
37 
38 #define kNumNewPriorityTestMessages 2
39 #define kNumSetPriorityTestMessages 2
40 #define kNumTestMessages (kNumNewPriorityTestMessages + kNumSetPriorityTestMessages)
41 
42 // This function verifies the content of the priority queue to match the passed in messages
VerifyPriorityQueueContent(ot::PriorityQueue & aPriorityQueue,int aExpectedLength,...)43 void VerifyPriorityQueueContent(ot::PriorityQueue &aPriorityQueue, int aExpectedLength, ...)
44 {
45     va_list      args;
46     ot::Message *message;
47     ot::Message *msgArg;
48     int8_t       curPriority = ot::Message::kNumPriorities;
49     uint16_t     msgCount, bufCount;
50 
51     // Check the `GetInfo`
52     aPriorityQueue.GetInfo(msgCount, bufCount);
53     VerifyOrQuit(msgCount == aExpectedLength, "GetInfo() result does not match expected len.");
54 
55     va_start(args, aExpectedLength);
56 
57     if (aExpectedLength == 0)
58     {
59         message = aPriorityQueue.GetHead();
60         VerifyOrQuit(message == nullptr, "PriorityQueue is not empty when expected len is zero.");
61 
62         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(ot::Message::kPriorityLow) == nullptr);
63         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(ot::Message::kPriorityNormal) == nullptr);
64         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(ot::Message::kPriorityHigh) == nullptr);
65         VerifyOrQuit(aPriorityQueue.GetHeadForPriority(ot::Message::kPriorityNet) == nullptr);
66     }
67     else
68     {
69         // Go through all messages in the queue and verify they match the passed-in messages
70         for (message = aPriorityQueue.GetHead(); message != nullptr; message = message->GetNext())
71         {
72             VerifyOrQuit(aExpectedLength != 0, "PriorityQueue contains more entries than expected.");
73 
74             msgArg = va_arg(args, ot::Message *);
75 
76             if (msgArg->GetPriority() != curPriority)
77             {
78                 for (curPriority--; curPriority != msgArg->GetPriority(); curPriority--)
79                 {
80                     // Check the `GetHeadForPriority` is nullptr if there are no expected message for this priority
81                     // level.
82                     VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<ot::Message::Priority>(curPriority)) ==
83                                      nullptr,
84                                  "is non-nullptr when no expected msg for this priority.");
85                 }
86 
87                 // Check the `GetHeadForPriority`.
88                 VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<ot::Message::Priority>(curPriority)) ==
89                              msgArg);
90             }
91 
92             // Check the queued message to match the one from argument list
93             VerifyOrQuit(msgArg == message, "PriorityQueue content does not match what is expected.");
94 
95             aExpectedLength--;
96         }
97 
98         VerifyOrQuit(aExpectedLength == 0, "PriorityQueue contains less entries than expected.");
99 
100         // Check the `GetHeadForPriority` is nullptr if there are no expected message for any remaining priority level.
101         for (curPriority--; curPriority >= 0; curPriority--)
102         {
103             VerifyOrQuit(aPriorityQueue.GetHeadForPriority(static_cast<ot::Message::Priority>(curPriority)) == nullptr,
104                          "is non-nullptr when no expected msg for this priority.");
105         }
106     }
107 
108     va_end(args);
109 }
110 
111 // This function verifies the content of the message queue to match the passed in messages
VerifyMsgQueueContent(ot::MessageQueue & aMessageQueue,int aExpectedLength,...)112 void VerifyMsgQueueContent(ot::MessageQueue &aMessageQueue, int aExpectedLength, ...)
113 {
114     va_list      args;
115     ot::Message *message;
116     ot::Message *msgArg;
117 
118     va_start(args, aExpectedLength);
119 
120     if (aExpectedLength == 0)
121     {
122         message = aMessageQueue.GetHead();
123         VerifyOrQuit(message == nullptr, "is not empty when expected len is zero.");
124     }
125     else
126     {
127         for (message = aMessageQueue.GetHead(); message != nullptr; message = message->GetNext())
128         {
129             VerifyOrQuit(aExpectedLength != 0, "contains more entries than expected");
130 
131             msgArg = va_arg(args, ot::Message *);
132             VerifyOrQuit(msgArg == message, "content does not match what is expected.");
133 
134             aExpectedLength--;
135         }
136 
137         VerifyOrQuit(aExpectedLength == 0, "contains less entries than expected");
138     }
139 
140     va_end(args);
141 }
142 
TestPriorityQueue(void)143 void TestPriorityQueue(void)
144 {
145     ot::Instance *    instance;
146     ot::MessagePool * messagePool;
147     ot::PriorityQueue queue;
148     ot::MessageQueue  messageQueue;
149     ot::Message *     msgNet[kNumTestMessages];
150     ot::Message *     msgHigh[kNumTestMessages];
151     ot::Message *     msgNor[kNumTestMessages];
152     ot::Message *     msgLow[kNumTestMessages];
153 
154     instance = testInitInstance();
155     VerifyOrQuit(instance != nullptr, "Null OpenThread instance");
156 
157     messagePool = &instance->Get<ot::MessagePool>();
158 
159     // Use the function "New()" to allocate messages with different priorities
160     for (int i = 0; i < kNumNewPriorityTestMessages; i++)
161     {
162         msgNet[i] = messagePool->New(ot::Message::kTypeIp6, 0, ot::Message::kPriorityNet);
163         VerifyOrQuit(msgNet[i] != nullptr);
164         msgHigh[i] = messagePool->New(ot::Message::kTypeIp6, 0, ot::Message::kPriorityHigh);
165         VerifyOrQuit(msgHigh[i] != nullptr);
166         msgNor[i] = messagePool->New(ot::Message::kTypeIp6, 0, ot::Message::kPriorityNormal);
167         VerifyOrQuit(msgNor[i] != nullptr);
168         msgLow[i] = messagePool->New(ot::Message::kTypeIp6, 0, ot::Message::kPriorityLow);
169         VerifyOrQuit(msgLow[i] != nullptr);
170     }
171 
172     // Use the function "SetPriority()" to allocate messages with different priorities
173     for (int i = kNumNewPriorityTestMessages; i < kNumTestMessages; i++)
174     {
175         msgNet[i] = messagePool->New(ot::Message::kTypeIp6, 0);
176         VerifyOrQuit(msgNet[i] != nullptr);
177         SuccessOrQuit(msgNet[i]->SetPriority(ot::Message::kPriorityNet));
178         msgHigh[i] = messagePool->New(ot::Message::kTypeIp6, 0);
179         VerifyOrQuit(msgHigh[i] != nullptr);
180         SuccessOrQuit(msgHigh[i]->SetPriority(ot::Message::kPriorityHigh));
181         msgNor[i] = messagePool->New(ot::Message::kTypeIp6, 0);
182         VerifyOrQuit(msgNor[i] != nullptr);
183         SuccessOrQuit(msgNor[i]->SetPriority(ot::Message::kPriorityNormal));
184         msgLow[i] = messagePool->New(ot::Message::kTypeIp6, 0);
185         VerifyOrQuit(msgLow[i] != nullptr);
186         SuccessOrQuit(msgLow[i]->SetPriority(ot::Message::kPriorityLow));
187     }
188 
189     // Check the `GetPriority()`
190     for (int i = 0; i < kNumTestMessages; i++)
191     {
192         VerifyOrQuit(msgLow[i]->GetPriority() == ot::Message::kPriorityLow);
193         VerifyOrQuit(msgNor[i]->GetPriority() == ot::Message::kPriorityNormal);
194         VerifyOrQuit(msgHigh[i]->GetPriority() == ot::Message::kPriorityHigh);
195         VerifyOrQuit(msgNet[i]->GetPriority() == ot::Message::kPriorityNet);
196     }
197 
198     // Verify case of an empty queue.
199     VerifyPriorityQueueContent(queue, 0);
200 
201     // Add msgs in different orders and check the content of queue.
202     queue.Enqueue(*msgHigh[0]);
203     VerifyPriorityQueueContent(queue, 1, msgHigh[0]);
204     queue.Enqueue(*msgHigh[1]);
205     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgHigh[1]);
206     queue.Enqueue(*msgNet[0]);
207     VerifyPriorityQueueContent(queue, 3, msgNet[0], msgHigh[0], msgHigh[1]);
208     queue.Enqueue(*msgNet[1]);
209     VerifyPriorityQueueContent(queue, 4, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1]);
210     queue.Enqueue(*msgHigh[2]);
211     VerifyPriorityQueueContent(queue, 5, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2]);
212     queue.Enqueue(*msgLow[0]);
213     VerifyPriorityQueueContent(queue, 6, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgLow[0]);
214     queue.Enqueue(*msgNor[0]);
215     VerifyPriorityQueueContent(queue, 7, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgNor[0],
216                                msgLow[0]);
217     queue.Enqueue(*msgHigh[3]);
218     VerifyPriorityQueueContent(queue, 8, msgNet[0], msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgHigh[3],
219                                msgNor[0], msgLow[0]);
220 
221     // Remove messages in different order and check the content of queue in each step.
222     queue.Dequeue(*msgNet[0]);
223     VerifyPriorityQueueContent(queue, 7, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[2], msgHigh[3], msgNor[0],
224                                msgLow[0]);
225     queue.Dequeue(*msgHigh[2]);
226     VerifyPriorityQueueContent(queue, 6, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[3], msgNor[0], msgLow[0]);
227     queue.Dequeue(*msgNor[0]);
228     VerifyPriorityQueueContent(queue, 5, msgNet[1], msgHigh[0], msgHigh[1], msgHigh[3], msgLow[0]);
229     queue.Dequeue(*msgHigh[1]);
230     VerifyPriorityQueueContent(queue, 4, msgNet[1], msgHigh[0], msgHigh[3], msgLow[0]);
231     queue.Dequeue(*msgLow[0]);
232     VerifyPriorityQueueContent(queue, 3, msgNet[1], msgHigh[0], msgHigh[3]);
233     queue.Dequeue(*msgNet[1]);
234     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgHigh[3]);
235     queue.Dequeue(*msgHigh[0]);
236     VerifyPriorityQueueContent(queue, 1, msgHigh[3]);
237     queue.Dequeue(*msgHigh[3]);
238     VerifyPriorityQueueContent(queue, 0);
239 
240     // Change the priority of an already queued message and check the order change in the queue.
241     queue.Enqueue(*msgNor[0]);
242     VerifyPriorityQueueContent(queue, 1, msgNor[0]);
243     queue.Enqueue(*msgHigh[0]);
244     VerifyPriorityQueueContent(queue, 2, msgHigh[0], msgNor[0]);
245     queue.Enqueue(*msgLow[0]);
246     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgNor[0], msgLow[0]);
247 
248     SuccessOrQuit(msgNor[0]->SetPriority(ot::Message::kPriorityNet));
249     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
250     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityLow));
251     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
252     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityNormal));
253     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
254     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityHigh));
255     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgHigh[0], msgLow[0]);
256     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityNet));
257     VerifyPriorityQueueContent(queue, 3, msgNor[0], msgLow[0], msgHigh[0]);
258     SuccessOrQuit(msgNor[0]->SetPriority(ot::Message::kPriorityNormal));
259     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityLow));
260     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgNor[0], msgLow[0]);
261 
262     messageQueue.Enqueue(*msgNor[1]);
263     messageQueue.Enqueue(*msgHigh[1]);
264     messageQueue.Enqueue(*msgNet[1]);
265     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
266 
267     // Change priority of message and check for not in messageQueue.
268     SuccessOrQuit(msgNor[1]->SetPriority(ot::Message::kPriorityNet));
269     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
270 
271     SuccessOrQuit(msgLow[0]->SetPriority(ot::Message::kPriorityHigh));
272     VerifyPriorityQueueContent(queue, 3, msgHigh[0], msgLow[0], msgNor[0]);
273     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
274 
275     // Remove messages from the two queues
276     queue.Dequeue(*msgHigh[0]);
277     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
278     VerifyMsgQueueContent(messageQueue, 3, msgNor[1], msgHigh[1], msgNet[1]);
279 
280     messageQueue.Dequeue(*msgNet[1]);
281     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
282     VerifyMsgQueueContent(messageQueue, 2, msgNor[1], msgHigh[1]);
283 
284     messageQueue.Dequeue(*msgHigh[1]);
285     VerifyPriorityQueueContent(queue, 2, msgLow[0], msgNor[0]);
286     VerifyMsgQueueContent(messageQueue, 1, msgNor[1]);
287 
288     queue.Dequeue(*msgLow[0]);
289     VerifyPriorityQueueContent(queue, 1, msgNor[0]);
290     VerifyMsgQueueContent(messageQueue, 1, msgNor[1]);
291 
292     testFreeInstance(instance);
293 }
294 
main(void)295 int main(void)
296 {
297     TestPriorityQueue();
298     printf("All tests passed\n");
299     return 0;
300 }
301