1 /*
2 * Copyright (c) 2023 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 #include "unique_stack_table.h"
16 namespace OHOS {
17 namespace Developtools {
18 namespace HiPerf {
19
Init()20 bool UniqueStackTable::Init()
21 {
22 // index 0 for reserved
23 availableIndex_ = 1;
24 totalNodes_ = ((tableSize_ / sizeof(Node)) >> 1) << 1; // make it even.
25 if (totalNodes_ > MAX_NODES_CNT) {
26 HLOGE("Hashtable size limit, initial value too large!");
27 return false;
28 }
29
30 availableNodes_ = totalNodes_;
31 hashModulus_ = availableNodes_ >= 1 ? availableNodes_ - 1 : 0;
32 hashStep_ = (totalNodes_ / (deconflictTimes_ * HASH_STEP_BASE_MULTIPLE + HASH_STEP_BASE_NUM));
33 tableBuf_ = std::make_unique<uint8_t[]>(tableSize_);
34
35 HLOGI("Init totalNodes_: %u, availableNodes_: %u, availableIndex_: %u hashStep_: %" PRIu64 ", hashModulus_: %u",
36 totalNodes_, availableNodes_, availableIndex_, hashStep_, hashModulus_);
37 return true;
38 }
39
Resize()40 bool UniqueStackTable::Resize()
41 {
42 if (tableBuf_ == nullptr) {
43 HLOGE("Hashtable not exist, fatal error!");
44 return 0;
45 }
46 uint32_t oldNumNodes = totalNodes_;
47
48 HLOGI("Before resize, totalNodes_: %u, availableNodes_: %u, availableIndex_: %u hashStep_: %" PRIu64 "",
49 totalNodes_, availableNodes_, availableIndex_, hashStep_);
50
51 if ((totalNodes_ << RESIZE_MULTIPLE) > MAX_NODES_CNT) {
52 HLOGW("Hashtable size limit, resize failed current cnt: %u, max cnt: %u", totalNodes_, MAX_NODES_CNT);
53 return false;
54 }
55
56 uint32_t newtableSize = tableSize_ << RESIZE_MULTIPLE;
57 std::unique_ptr<uint8_t[]> newTable = std::make_unique<uint8_t[]>(newtableSize);
58 if (newTable.get() == nullptr) {
59 HLOGE("%s: malloc(%u) failed, errno: %d", __func__, newtableSize, errno);
60 return false;
61 }
62
63 if (memcpy_s(newTable.get(), tableSize_, tableBuf_.get(), tableSize_) != 0) {
64 HLOGE("%s: memcpy_s(%u) failed, errno: %d", __func__, tableSize_, errno);
65 return false;
66 }
67
68 tableBuf_ = std::move(newTable);
69 tableSize_ = newtableSize;
70 deconflictTimes_ += DECONFLICT_INCREASE_STEP;
71 availableIndex_ += availableNodes_;
72 totalNodes_ = ((newtableSize / sizeof(Node)) >> 1) << 1; // make it even.
73 availableNodes_ = totalNodes_ - oldNumNodes;
74 hashModulus_ = availableNodes_ >= 1 ? availableNodes_ - 1 : 0;
75 hashStep_ = availableNodes_ / (deconflictTimes_ * HASH_STEP_BASE_MULTIPLE + HASH_STEP_BASE_NUM);
76 HLOGI("After resize, totalNodes_: %u, availableNodes_: %u, availableIndex_: %u hashStep_: %" PRIu64 "",
77 totalNodes_, availableNodes_, availableIndex_, hashStep_);
78 return true;
79 }
80
PutIpInSlot(uint64_t thisIp,uint64_t prevIdx)81 uint64_t UniqueStackTable::PutIpInSlot(uint64_t thisIp, uint64_t prevIdx)
82 {
83 Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
84 uint64_t curIpIdx = (((thisIp >> 2) ^ (prevIdx << 4)) % hashModulus_) + availableIndex_;
85 uint8_t currentDeconflictTimes = deconflictTimes_;
86
87 Node node;
88 node.section.ip = thisIp;
89 node.section.prevIdx = prevIdx;
90 node.section.inKernel = !!(thisIp & IP_IN_KERNEL);
91 while (currentDeconflictTimes--) {
92 Node* tableNode = reinterpret_cast<Node *>(tableHead) + curIpIdx;
93 if (tableNode == nullptr) {
94 continue;
95 }
96 // empty case
97 if (tableNode->value == 0) {
98 tableNode->value = node.value;
99 usedSlots_.emplace_back(uint32_t(curIpIdx));
100 return curIpIdx;
101 }
102 // already inserted
103 if (tableNode->value == node.value) {
104 return curIpIdx;
105 }
106
107 curIpIdx += currentDeconflictTimes * hashStep_ + 1;
108 if (curIpIdx >= totalNodes_) {
109 // make sure index 0 do not occupy
110 curIpIdx -= (availableNodes_ >= 1 ? availableNodes_ - 1 : 0);
111 }
112 }
113
114 HLOGI("Collison unresolved, need resize, usedSlots_.size(): %zu, curIpIdx: %" PRIu64 "",
115 usedSlots_.size(), curIpIdx);
116 return 0;
117 }
118
PutIpsInTable(StackId * stackId,u64 * ips,u64 nr)119 uint64_t UniqueStackTable::PutIpsInTable(StackId *stackId, u64 *ips, u64 nr)
120 {
121 if (tableBuf_ == nullptr) {
122 HLOGE("Hashtable not exist, fatal error!");
123 return 0;
124 }
125 int64_t reverseIndex = static_cast<int64_t>(nr);
126 uint64_t prev = 0;
127 while (--reverseIndex >= 0) {
128 uint64_t pc = ips[reverseIndex];
129
130 if (pc == 0) {
131 continue;
132 }
133 prev = PutIpInSlot(pc, prev);
134 if (prev == 0) {
135 return 0;
136 }
137 }
138 if (stackId == nullptr) {
139 return 0;
140 }
141 stackId->section.id = prev;
142 stackId->section.nr = nr;
143 return prev;
144 }
145
GetWriteSize()146 size_t UniqueStackTable::GetWriteSize()
147 {
148 if (tableBuf_ == nullptr) {
149 HLOGE("Hashtable not exist, fatal error!");
150 return 0;
151 }
152 size_t size = 0;
153 size += sizeof(pid_);
154 size += sizeof(tableSize_);
155 uint32_t usedNodes = usedSlots_.size();
156 size += sizeof(usedNodes);
157 size += usedNodes * sizeof(uint32_t); // key index
158 size += usedNodes * sizeof(uint64_t); // node value
159 return size;
160 }
161
GetFrame(uint64_t stackId)162 Node* UniqueStackTable::GetFrame(uint64_t stackId)
163 {
164 Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
165 if (stackId >= totalNodes_) {
166 // should not occur
167 HLOGE("Failed to find frame by index: %" PRIu64 "", stackId);
168 return nullptr;
169 }
170
171 return reinterpret_cast<Node *>(&tableHead[stackId]);
172 }
173
GetIpsByStackId(StackId stackId,std::vector<u64> & ips)174 bool UniqueStackTable::GetIpsByStackId(StackId stackId, std::vector<u64>& ips)
175 {
176 if (tableBuf_ == nullptr) {
177 HLOGE("Hashtable not exist, failed to find frame!");
178 return false;
179 }
180 uint64_t nr = stackId.section.nr;
181 uint64_t tailIdx = stackId.section.id;
182
183 Node *node = GetFrame(tailIdx);
184 while (node != nullptr && nr > 0) {
185 ips.push_back(
186 node->section.inKernel ? (node->section.ip | KERNEL_PREFIX) : node->section.ip);
187 if (node->section.prevIdx == HEAD_NODE_INDEX) {
188 break;
189 }
190 node = GetFrame(node->section.prevIdx);
191 nr--;
192 }
193 return true;
194 }
195
ImportNode(uint32_t index,const Node & node)196 bool UniqueStackTable::ImportNode(uint32_t index, const Node& node)
197 {
198 Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
199 if (index >= tableSize_) {
200 return false;
201 }
202 tableHead[index].value = node.value;
203 return true;
204 }
205
206 } // namespace HiPerf
207 } // namespace Developtools
208 } // namespace OHOS