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
17 #include "hiperf_hilog.h"
18
19 namespace OHOS {
20 namespace Developtools {
21 namespace HiPerf {
22
Init()23 bool UniqueStackTable::Init()
24 {
25 // index 0 for reserved
26 availableIndex_ = 1;
27 totalNodes_ = ((tableSize_ / sizeof(Node)) >> 1) << 1; // make it even.
28 if (totalNodes_ > MAX_NODES_CNT) {
29 HLOGE("Hashtable size limit, initial value too large!");
30 return false;
31 }
32
33 availableNodes_ = totalNodes_;
34 hashModulus_ = availableNodes_ > 1 ? availableNodes_ - 1 : 1;
35 hashStep_ = (totalNodes_ / (deconflictTimes_ * HASH_STEP_BASE_MULTIPLE + HASH_STEP_BASE_NUM));
36 tableBuf_ = std::make_unique<uint8_t[]>(tableSize_);
37
38 HLOGI("Init totalNodes_: %u, availableNodes_: %u, availableIndex_: %u hashStep_: %" PRIu64 ", hashModulus_: %u",
39 totalNodes_, availableNodes_, availableIndex_, hashStep_, hashModulus_);
40 return true;
41 }
42
Resize()43 bool UniqueStackTable::Resize()
44 {
45 CHECK_TRUE(tableBuf_ != nullptr, 0, 1, "Hashtable not exist, fatal error!");
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 : 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(const uint64_t thisIp,const uint64_t prevIdx)81 uint64_t UniqueStackTable::PutIpInSlot(const uint64_t thisIp, const 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,const u64 * ips,const u64 nr)119 uint64_t UniqueStackTable::PutIpsInTable(StackId *stackId, const u64 *ips, const 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 CHECK_TRUE(prev != 0, 0, 0, "");
135 }
136 CHECK_TRUE(stackId != nullptr, 0, 0, "");
137 stackId->section.id = prev;
138 stackId->section.nr = nr;
139 return prev;
140 }
141
GetWriteSize()142 size_t UniqueStackTable::GetWriteSize()
143 {
144 CHECK_TRUE(tableBuf_ != nullptr, 0, 1, "Hashtable not exist, fatal error!");
145 size_t size = 0;
146 size += sizeof(pid_);
147 size += sizeof(tableSize_);
148 uint32_t usedNodes = usedSlots_.size();
149 size += sizeof(usedNodes);
150 size += usedNodes * sizeof(uint32_t); // key index
151 size += usedNodes * sizeof(uint64_t); // node value
152 return size;
153 }
154
GetFrame(uint64_t stackId)155 Node* UniqueStackTable::GetFrame(uint64_t stackId)
156 {
157 Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
158 // should not occur
159 CHECK_TRUE(stackId < totalNodes_, nullptr, 1, "Failed to find frame by index: %" PRIu64 "", stackId);
160
161 return reinterpret_cast<Node *>(&tableHead[stackId]);
162 }
163
GetIpsByStackId(const StackId stackId,std::vector<u64> & ips)164 bool UniqueStackTable::GetIpsByStackId(const StackId stackId, std::vector<u64>& ips)
165 {
166 CHECK_TRUE(tableBuf_ != nullptr, false, 1, "Hashtable not exist, failed to find frame!");
167 uint64_t nr = stackId.section.nr;
168 uint64_t tailIdx = stackId.section.id;
169
170 Node *node = GetFrame(tailIdx);
171 while (node != nullptr && nr > 0) {
172 ips.push_back(
173 node->section.inKernel ? (node->section.ip | KERNEL_PREFIX) : node->section.ip);
174 if (node->section.prevIdx == HEAD_NODE_INDEX) {
175 break;
176 }
177 node = GetFrame(node->section.prevIdx);
178 nr--;
179 }
180 return true;
181 }
182
ImportNode(const uint32_t index,const Node & node)183 bool UniqueStackTable::ImportNode(const uint32_t index, const Node& node)
184 {
185 CHECK_TRUE(index < tableSize_, false, 0, "");
186 Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
187 tableHead[index].value = node.value;
188 return true;
189 }
190
191 } // namespace HiPerf
192 } // namespace Developtools
193 } // namespace OHOS