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;
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;
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
94 // empty case
95 if (tableNode->value == 0) {
96 tableNode->value = node.value;
97 usedSlots_.emplace_back(uint32_t(curIpIdx));
98 return curIpIdx;
99 }
100 // already inserted
101 if (tableNode->value == node.value) {
102 return curIpIdx;
103 }
104
105 curIpIdx += currentDeconflictTimes_ * hashStep_ + 1;
106 if (curIpIdx >= totalNodes_) {
107 // make sure index 0 do not occupy
108 curIpIdx -= (availableNodes_ - 1);
109 }
110 }
111
112 HLOGI("Collison unresolved, need resize, usedSlots_.size(): %zu, curIpIdx: %" PRIu64 "",
113 usedSlots_.size(), curIpIdx);
114 return 0;
115 }
116
PutIpsInTable(StackId * stackId,u64 * ips,u64 nr)117 uint64_t UniqueStackTable::PutIpsInTable(StackId *stackId, u64 *ips, u64 nr)
118 {
119 if (tableBuf_ == nullptr) {
120 HLOGE("Hashtable not exist, fatal error!");
121 return 0;
122 }
123 int64_t reverseIndex = static_cast<int64_t>(nr);
124 uint64_t prev = 0;
125 while (--reverseIndex >= 0) {
126 uint64_t pc = ips[reverseIndex];
127
128 if (pc == 0) {
129 continue;
130 }
131 prev = PutIpInSlot(pc, prev);
132 if (prev == 0) {
133 return 0;
134 }
135 }
136
137 stackId->section.id = prev;
138 stackId->section.nr = nr;
139 return prev;
140 }
141
GetWriteSize()142 size_t UniqueStackTable::GetWriteSize()
143 {
144 if (tableBuf_ == nullptr) {
145 HLOGE("Hashtable not exist, fatal error!");
146 return 0;
147 }
148 size_t size = 0;
149 size += sizeof(pid_);
150 size += sizeof(tableSize_);
151 uint32_t usedNodes = usedSlots_.size();
152 size += sizeof(usedNodes);
153 size += usedNodes * sizeof(uint32_t); // key index
154 size += usedNodes * sizeof(uint64_t); // node value
155 return size;
156 }
157
GetFrame(uint64_t stackId)158 Node* UniqueStackTable::GetFrame(uint64_t stackId)
159 {
160 Node *tableHead_ = reinterpret_cast<Node *>(tableBuf_.get());
161 if (stackId >= totalNodes_) {
162 // should not occur
163 HLOGE("Failed to find frame by index: %" PRIu64 "", stackId);
164 return nullptr;
165 }
166
167 return (Node *)&tableHead_[stackId];
168 }
169
GetIpsByStackId(StackId stackId,std::vector<u64> & ips)170 bool UniqueStackTable::GetIpsByStackId(StackId stackId, std::vector<u64>& ips)
171 {
172 if (tableBuf_ == nullptr) {
173 HLOGE("Hashtable not exist, failed to find frame!");
174 return false;
175 }
176 uint64_t nr = stackId.section.nr;
177 uint64_t tailIdx = stackId.section.id;
178
179 Node *node = GetFrame(tailIdx);
180 while (node != nullptr && nr > 0) {
181 ips.push_back(
182 node->section.inKernel ? (node->section.ip | KERNEL_PREFIX) : node->section.ip);
183 if (node->section.prevIdx == HEAD_NODE_INDEX) {
184 break;
185 }
186 node = GetFrame(node->section.prevIdx);
187 nr--;
188 }
189 return true;
190 }
191
ImportNode(uint32_t index,const Node & node)192 bool UniqueStackTable::ImportNode(uint32_t index, const Node& node)
193 {
194 Node *tableHead_ = reinterpret_cast<Node *>(tableBuf_.get());
195 if (index >= tableSize_) {
196 return false;
197 }
198 tableHead_[index].value = node.value;
199 return true;
200 }
201
202 } // namespace HiPerf
203 } // namespace Developtools
204 } // namespace OHOS