1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "gtest/gtest.h"
18
19 #include <pthread.h>
20
21 #include "berberis/base/lock_free_stack.h"
22
23 namespace berberis {
24
25 namespace {
26
27 struct Node {
28 int data;
29 Node* next;
30 };
31
TEST(LockFreeStackTest,Basic)32 TEST(LockFreeStackTest, Basic) {
33 Node node_0{0, nullptr};
34 Node node_1{1, nullptr};
35 Node node_2{2, nullptr};
36 Node node_3{3, nullptr};
37
38 LockFreeStack<Node> st;
39
40 ASSERT_TRUE(st.Empty());
41
42 st.Push(&node_0);
43 st.Push(&node_1);
44 st.Push(&node_2);
45
46 ASSERT_FALSE(st.Empty());
47
48 ASSERT_EQ(st.Pop(), &node_2);
49 ASSERT_EQ(st.Pop(), &node_1);
50 ASSERT_EQ(st.Pop(), &node_0);
51
52 ASSERT_TRUE(st.Empty());
53
54 st.Push(&node_3);
55
56 node_0.next = &node_3;
57 node_1.next = &node_0;
58 node_2.next = &node_1;
59 st.PushRange(&node_2, &node_0);
60
61 ASSERT_FALSE(st.Empty());
62
63 ASSERT_EQ(st.Pop(), &node_2);
64 ASSERT_EQ(st.Pop(), &node_1);
65
66 ASSERT_FALSE(st.Empty());
67
68 st.Push(&node_2);
69
70 ASSERT_EQ(st.Pop(), &node_2);
71 ASSERT_EQ(st.Pop(), &node_0);
72 ASSERT_EQ(st.Pop(), &node_3);
73
74 ASSERT_TRUE(st.Empty());
75 }
76
77 constexpr size_t kNumThreads = 50;
78 constexpr size_t kNumNodesPerThread = 50;
79 constexpr size_t kNumItersPerThread = 2000;
80
81 Node g_nodes[kNumThreads * kNumNodesPerThread];
82 LockFreeStack<Node> g_st;
83
CheckStressPushPop(size_t idx)84 void CheckStressPushPop(size_t idx) {
85 Node* nodes[kNumNodesPerThread];
86
87 // Get initial set of nodes.
88 for (size_t i = 0; i < kNumNodesPerThread; ++i) {
89 nodes[i] = &g_nodes[kNumNodesPerThread * idx + i];
90 }
91
92 // On each iteration, push and pop idx + 1 nodes.
93 for (size_t j = 0; j < kNumItersPerThread; ++j) {
94 // Push nodes
95 for (size_t i = 0; i < idx + 1; ++i) {
96 g_st.Push(nodes[i]);
97 }
98 ASSERT_FALSE(g_st.Empty());
99
100 // Pop nodes
101 for (size_t i = 0; i < idx + 1; ++i) {
102 nodes[i] = g_st.Pop();
103 ASSERT_NE(nodes[i], nullptr);
104 }
105
106 // Push range
107 Node* next = nullptr;
108 for (size_t i = 0; i < idx + 1; ++i) {
109 nodes[i]->next = next;
110 next = nodes[i];
111 }
112 g_st.PushRange(next, nodes[0]);
113 ASSERT_FALSE(g_st.Empty());
114
115 // Pop nodes
116 for (size_t i = 0; i < idx + 1; ++i) {
117 nodes[i] = g_st.Pop();
118 ASSERT_NE(nodes[i], nullptr);
119 }
120 }
121 }
122
StressFunc(void * arg)123 void* StressFunc(void* arg) {
124 CheckStressPushPop(reinterpret_cast<size_t>(arg));
125 return nullptr;
126 }
127
TEST(LockFreeStackTest,Stress)128 TEST(LockFreeStackTest, Stress) {
129 ASSERT_TRUE(g_st.Empty());
130
131 pthread_t threads[kNumThreads];
132
133 for (size_t i = 0; i < kNumThreads; ++i) {
134 int res = pthread_create(&threads[i], nullptr, StressFunc, reinterpret_cast<void*>(i));
135 ASSERT_EQ(res, 0);
136 }
137
138 for (size_t i = 0; i < kNumThreads; ++i) {
139 int res = pthread_join(threads[i], nullptr);
140 ASSERT_EQ(res, 0);
141 }
142
143 ASSERT_TRUE(g_st.Empty());
144 }
145
146 } // namespace
147
148 } // namespace berberis
149