1 /**
2 * Copyright (c) 2021-2024 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 "lock_free_queue.h"
17
18 namespace ark::tooling::sampler {
19
Push(const FileInfo & data)20 void LockFreeQueue::Push(const FileInfo &data)
21 {
22 Node *newNode = new Node(std::make_unique<FileInfo>(data), nullptr);
23
24 for (;;) {
25 // Atomic with acquire order reason: to sync with push in other threads
26 Node *tail = tail_.load(std::memory_order_acquire);
27 ASSERT(tail != nullptr);
28 // Atomic with acquire order reason: to sync with push in other threads
29 Node *next = tail->next.load(std::memory_order_acquire);
30 // Atomic with acquire order reason: to sync with push in other threads
31 Node *tail2 = tail_.load(std::memory_order_acquire);
32 if (tail != tail2) {
33 continue;
34 }
35 if (next == nullptr) {
36 if (tail->next.compare_exchange_weak(next, newNode)) {
37 tail_.compare_exchange_strong(tail, newNode);
38 ++size_;
39 return;
40 }
41 } else {
42 Node *newTail = next;
43 tail_.compare_exchange_strong(tail, newTail);
44 }
45 }
46 }
47
48 // NOLINTNEXTLINE(performance-unnecessary-value-param)
Pop(FileInfo & ret)49 void LockFreeQueue::Pop(FileInfo &ret)
50 {
51 for (;;) {
52 // Atomic with acquire order reason: to sync with push in other threads
53 Node *head = head_.load(std::memory_order_acquire);
54 // Atomic with acquire order reason: to sync with push in other threads
55 Node *tail = tail_.load(std::memory_order_acquire);
56 // Atomic with acquire order reason: to sync with push in other threads
57 Node *next = head->next.load(std::memory_order_acquire);
58 // Atomic with acquire order reason: to sync with push in other threads
59 Node *head2 = head_.load(std::memory_order_acquire);
60 if (head != head2) {
61 continue;
62 }
63 if (head == tail) {
64 ASSERT(next != nullptr);
65 Node *newTail = next;
66 tail_.compare_exchange_strong(tail, newTail);
67 } else {
68 if (next == nullptr) {
69 continue;
70 }
71 ASSERT(next->data != nullptr);
72 ret = *(next->data);
73 Node *newHead = next;
74 if (head_.compare_exchange_weak(head, newHead)) {
75 delete head;
76 --size_;
77 return;
78 }
79 }
80 }
81 }
82
FindValue(uintptr_t data) const83 bool LockFreeQueue::FindValue(uintptr_t data) const
84 {
85 // Atomic with acquire order reason: to sync with push in other threads
86 Node *head = head_.load(std::memory_order_acquire);
87 // Atomic with acquire order reason: to sync with push in other threads
88 Node *tail = tail_.load(std::memory_order_acquire);
89
90 for (;;) {
91 ASSERT(head != nullptr);
92 // Should be only dummy Node, but keep that check
93 if (head->data == nullptr) {
94 if (head == tail) {
95 // here all nodes were checked
96 break;
97 }
98 head = head->next;
99 continue;
100 }
101
102 if (head->data->ptr == data) {
103 return true;
104 }
105
106 if (head == tail) {
107 // here all nodes were checked
108 break;
109 }
110 head = head->next;
111 }
112
113 return false;
114 }
115
116 } // namespace ark::tooling::sampler
117