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
19namespace OHOS {
20namespace Developtools {
21namespace HiPerf {
22
23bool 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
43bool 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
81uint64_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
119uint64_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        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
142size_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
155Node* 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
164bool UniqueStackTable::GetIpsByStackId(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
183bool UniqueStackTable::ImportNode(uint32_t index, const Node& node)
184{
185    Node *tableHead = reinterpret_cast<Node *>(tableBuf_.get());
186    CHECK_TRUE(index >= tableSize_, false, 0, "");
187    tableHead[index].value = node.value;
188    return true;
189}
190
191} // namespace HiPerf
192} // namespace Developtools
193} // namespace OHOS