1 /*
2 * Copyright (c) 2025 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "softbus_conn_fair_priority_queue.h"
17
18 #include <list>
19 #include <memory>
20 #include <random>
21
22 #include <gtest/gtest.h>
23
24 #include "softbus_adapter_timer.h"
25
26 #include "conn_log.h"
27
28 using namespace testing::ext;
29 using namespace testing;
30
31 extern "C" {
32 struct DummyQueueItem {
33 CONN_QUEUE_ITEM_BASE;
34 int payload;
35 };
36 }
37
38 namespace OHOS::SoftBus {
39 class ConnQueueTest : public testing::Test {
40 public:
SetUpTestCase()41 static void SetUpTestCase() { }
42
TearDownTestCase()43 static void TearDownTestCase() { }
44
SetUp()45 void SetUp() override { }
46
TearDown()47 void TearDown() override { }
48 };
49
50 struct TestAction;
51 struct TestAction {
52 // 0: enqueue, other: dequeue
53 int operation_;
54 // it should declare as pointer type, as we should assert it is the same object or not
55 std::shared_ptr<DummyQueueItem> item_;
56 int32_t timeoutMs_;
57 bool wait_;
58 int32_t ret_;
59
TestActionOHOS::SoftBus::TestAction60 TestAction(int operation, std::shared_ptr<DummyQueueItem> &item, int32_t timeoutMs, bool wait, int32_t ret)
61 {
62 operation_ = operation;
63 item_ = std::shared_ptr(item);
64 timeoutMs_ = timeoutMs;
65 wait_ = wait;
66 ret_ = ret;
67 }
68
69 ~TestAction() = default;
70 };
71
Dump(const TestAction & action,const DummyQueueItem * item)72 static void Dump(const TestAction &action, const DummyQueueItem *item)
73 {
74 if (item != nullptr) {
75 CONN_LOGI(CONN_TEST,
76 "operation=%{public}d, timeout=%{public}dms, wait=%{public}d, ret code=%{public}d;"
77 "id=%{public}d, priority=%{public}d, payload=%{public}d",
78 action.operation_, action.timeoutMs_, action.wait_, action.ret_, item->id, item->priority,
79 item->payload);
80 } else {
81 CONN_LOGI(CONN_TEST,
82 "operation=%{public}d, timeout=%{public}dms, wait=%{public}d, ret code=%{public}d, item is not exist",
83 action.operation_, action.timeoutMs_, action.wait_, action.ret_);
84 }
85 }
86
RunTestCase(const std::string & name,ConnFairPriorityQueue * queue,std::list<std::shared_ptr<TestAction>> & actions,bool verbose=false)87 static bool RunTestCase(const std::string &name, ConnFairPriorityQueue *queue,
88 std::list<std::shared_ptr<TestAction>> &actions, bool verbose = false)
89 {
90 int32_t i = 0;
91
92 if (verbose) {
93 for (const auto &action : actions) {
94 CONN_LOGI(CONN_TEST, "%{public}s: the %{public}d th dump before any action", name.c_str(), i);
95 Dump(*action, action->item_.get());
96 }
97 }
98
99 i = 0;
100 for (const auto &action : actions) {
101 int32_t ret;
102 DummyQueueItem *item = nullptr;
103 auto before = SoftBusGetSysTimeMs();
104 if (action->operation_ == 0) {
105 item = action->item_.get();
106 ret = ConnEnqueue(queue, (struct ConnQueueItem *)item, action->timeoutMs_);
107 } else {
108 item = nullptr;
109 ret = ConnDequeue(queue, (struct ConnQueueItem **)&item, action->timeoutMs_);
110 }
111
112 auto duration = SoftBusGetSysTimeMs() - before;
113 if (action->ret_ != ret) {
114 ADD_FAILURE() << name << ", failed on " << i << "th action, expect code " << action->ret_ << " actual is "
115 << ret;
116 return false;
117 }
118
119 if (action->ret_ == SOFTBUS_OK) {
120 DummyQueueItem *expected = action->item_.get();
121 if (expected != nullptr && item != expected) {
122 ADD_FAILURE() << name << ", failed on " << i << "th action, item not match";
123 return false;
124 }
125 }
126
127 if (action->wait_ && duration < action->timeoutMs_) {
128 ADD_FAILURE() << name << ", failed on " << i << "th action, expect wait " << action->timeoutMs_
129 << ", actual just passed " << duration << " ms";
130 return false;
131 }
132 if (!action->wait_ && duration >= action->timeoutMs_) {
133 ADD_FAILURE() << name << ", failed on " << i << "th action, expect not wait " << action->timeoutMs_
134 << ", actual passed " << duration << " ms";
135 return false;
136 }
137 i++;
138 }
139 return true;
140 }
141
PickTestcase(int id,ConnPriority lastPriority,std::list<std::shared_ptr<TestAction>> & actions,std::list<std::shared_ptr<TestAction>> & result)142 static int32_t PickTestcase(int id, ConnPriority lastPriority, std::list<std::shared_ptr<TestAction>> &actions,
143 std::list<std::shared_ptr<TestAction>> &result)
144 {
145 for (int32_t priority = CONN_PRIORITY_HIGH; priority <= lastPriority; priority++) {
146 for (auto it = actions.begin(); it != actions.end(); it++) {
147 auto action = *it;
148 if (action->item_->id == id && action->item_->priority == priority) {
149 result.push_back(action);
150 actions.erase(it);
151 return SOFTBUS_OK;
152 }
153 }
154 }
155 return SOFTBUS_NOT_FIND;
156 }
157
FairPrioritySort(std::list<std::shared_ptr<TestAction>> & actions)158 static void FairPrioritySort(std::list<std::shared_ptr<TestAction>> &actions)
159 {
160 std::list<int> idSequence;
161 std::list<std::shared_ptr<TestAction>> result;
162
163 for (auto &action : actions) {
164 auto id = action->item_->id;
165 if (id == 0) {
166 continue;
167 }
168 auto it = std::find(idSequence.begin(), idSequence.end(), id);
169 if (it == idSequence.end()) {
170 idSequence.push_back(id);
171 }
172 }
173
174 int32_t ret;
175 do {
176 ret = PickTestcase(0, CONN_PRIORITY_MIDDLE, actions, result);
177 } while (ret == SOFTBUS_OK);
178
179 while (!idSequence.empty()) {
180 auto id = idSequence.front();
181 idSequence.pop_front();
182 ret = PickTestcase(id, CONN_PRIORITY_LOW, actions, result);
183 if (ret == SOFTBUS_OK) {
184 idSequence.push_back(id);
185 }
186 }
187 do {
188 ret = PickTestcase(0, CONN_PRIORITY_LOW, actions, result);
189 } while (ret == SOFTBUS_OK);
190
191 for (auto it = result.begin(); it != result.end(); it = result.erase(it)) {
192 auto action = *it;
193 actions.push_back(action);
194 }
195 }
196
197 /*
198 * @tc.name: DequeueDequeueAlternateTest
199 * @tc.desc: alternate enqueue and dequeue
200 * @tc.type: FUNC
201 * @tc.require:
202 */
203 HWTEST_F(ConnQueueTest, DequeueDequeueAlternateTest, TestSize.Level1)
204 {
205 constexpr uint32_t size = 4;
206 auto queue = ConnCreateQueue(size);
207 ASSERT_NE(queue, nullptr);
208
209 auto actions = std::list<std::shared_ptr<TestAction>>();
210 for (int i = 0; i < 10; i++) {
211 auto item = std::make_shared<DummyQueueItem>();
212 item->id = 0;
213 item->priority = CONN_PRIORITY_HIGH;
214 item->payload = i;
215
216 auto ea = std::make_shared<TestAction>(0, item, 1500, false, SOFTBUS_OK);
217 actions.push_back(ea);
218
219 auto da = std::make_shared<TestAction>(1, item, 1500, false, SOFTBUS_OK);
220 actions.push_back(da);
221 }
222 auto result = RunTestCase("enqueue dequeue alternate test", queue, actions, false);
223 EXPECT_TRUE(result);
224 ConnDestroyQueue(queue);
225 }
226
227 /*
228 * @tc.name: EnqueueBlockTest
229 * @tc.desc: enqueue block
230 * @tc.type: FUNC
231 * @tc.require:
232 */
233
234 HWTEST_F(ConnQueueTest, EnqueueDequeueBlockTest, TestSize.Level1)
235 {
236 constexpr uint32_t size = 4;
237 auto queue = ConnCreateQueue(size);
238 ASSERT_NE(queue, nullptr);
239
240 auto enqueueActions = std::list<std::shared_ptr<TestAction>>();
241 auto dequeueActions = std::list<std::shared_ptr<TestAction>>();
242 for (int i = 0; i < size - 1; i++) {
243 auto item = std::make_shared<DummyQueueItem>();
244 item->id = 1;
245 item->priority = CONN_PRIORITY_HIGH;
246 item->payload = i;
247
248 auto ea = std::make_shared<TestAction>(0, item, 100, false, SOFTBUS_OK);
249 enqueueActions.push_back(ea);
250
251 auto da = std::make_shared<TestAction>(1, item, 100, false, SOFTBUS_OK);
252 dequeueActions.push_back(da);
253 }
254
255 for (int i = 0; i < 3; i++) {
256 auto item = std::make_shared<DummyQueueItem>();
257 item->id = 1;
258 item->priority = CONN_PRIORITY_HIGH;
259 item->payload = i;
260
261 auto ea = std::make_shared<TestAction>(0, item, 100, true, SOFTBUS_TIMOUT);
262 enqueueActions.push_back(ea);
263
264 auto da = std::make_shared<TestAction>(1, item, 100, true, SOFTBUS_TIMOUT);
265 dequeueActions.push_back(da);
266 }
267
268 auto result = RunTestCase("enqueue block test", queue, enqueueActions, true);
269 EXPECT_TRUE(result);
270 result = RunTestCase("dequeue block test", queue, dequeueActions, true);
271 EXPECT_TRUE(result);
272 ConnDestroyQueue(queue);
273 }
274
275 /*
276 * @tc.name: PriorityQueueTest
277 * @tc.desc: test priority queue behavior
278 * @tc.type: FUNC
279 * @tc.require:
280 */
281
282 HWTEST_F(ConnQueueTest, PriorityQueueTest, TestSize.Level1)
283 {
284 constexpr uint32_t size = 1 << 8;
285 auto queue = ConnCreateQueue(size);
286 ASSERT_NE(queue, nullptr);
287
288 auto enqueueActions = std::list<std::shared_ptr<TestAction>>();
289 auto dequeueActions = std::list<std::shared_ptr<TestAction>>();
290
291 std::random_device rd;
292 std::mt19937 gen(rd());
293 std::uniform_int_distribution<> distId(0, 3);
294 std::uniform_int_distribution<> distPriority(0, 2);
295 for (auto i = 0; i < 10; i++) {
296 auto item = std::make_shared<DummyQueueItem>();
297 item->id = distId(gen);
298 item->priority = static_cast<ConnPriority>(distPriority(gen));
299 item->payload = i;
300
301 auto ea = std::make_shared<TestAction>(0, item, 100, false, SOFTBUS_OK);
302 enqueueActions.push_back(ea);
303
304 auto da = std::make_shared<TestAction>(1, item, 100, false, SOFTBUS_OK);
305 dequeueActions.push_back(da);
306 }
307 FairPrioritySort(dequeueActions);
308
309 // add one more dequeue action, check all item is dequeued
310 std::shared_ptr<DummyQueueItem> item = nullptr;
311 auto dta = std::make_shared<TestAction>(1, item, 100, true, SOFTBUS_TIMOUT);
312 dequeueActions.push_back(dta);
313
314 auto result = RunTestCase("priority enqueue test", queue, enqueueActions, true);
315 EXPECT_TRUE(result);
316 result = RunTestCase("priority dequeue test", queue, dequeueActions, true);
317 EXPECT_TRUE(result);
318
319 ConnDestroyQueue(queue);
320 }
321
322 } // namespace OHOS::SoftBus