1/*
2 * Copyright (c) 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#include "unique_stack_table.h"
16
17#include <sys/mman.h>
18#include <sys/prctl.h>
19#include <securec.h>
20#include "dfx_log.h"
21namespace OHOS {
22namespace HiviewDFX {
23UniqueStackTable* UniqueStackTable::Instance()
24{
25    static UniqueStackTable* instance = new UniqueStackTable();
26    return instance;
27}
28
29bool UniqueStackTable::Init()
30{
31    std::lock_guard<std::mutex> guard(stackTableMutex_);
32    // index 0 for reserved
33    if (tableBufMMap_ != nullptr) {
34        return true;
35    }
36    availableIndex_ = 1;
37    totalNodes_ = ((tableSize_ / sizeof(Node)) >> 1) << 1; // make it even.
38    if (totalNodes_ > MAX_NODES_CNT) {
39        DFXLOGW("Hashtable size limit, initial value too large!\n");
40        return false;
41    }
42
43    availableNodes_ = totalNodes_;
44    if (availableNodes_ == 0) {
45        return false;
46    }
47    hashModulus_ = availableNodes_ - 1;
48    hashStep_ = (totalNodes_ / (deconflictTimes_ * 2 + 1)); // 2 : double times
49    auto retBufMMap = mmap(NULL, tableSize_, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
50    if (retBufMMap == MAP_FAILED) {
51        DFXLOGW("Failed to mmap!\n");
52        return false;
53    }
54    tableBufMMap_ = retBufMMap;
55    prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, tableBufMMap_, tableSize_, "async_stack_table");
56    DFXLOGD(
57        "Init totalNodes_: %{public}u, availableNodes_: %{public}u, availableIndex_: %{public}u \
58        hashStep_: %{public}" PRIu64 ", hashModulus_: %{public}u",
59        totalNodes_, availableNodes_, availableIndex_, hashStep_, hashModulus_);
60    return true;
61}
62
63bool UniqueStackTable::Resize()
64{
65    std::lock_guard<std::mutex> guard(stackTableMutex_);
66    if (tableBufMMap_ == nullptr) {
67        DFXLOGW("[%{public}d]: Hashtable not exist, fatal error!", __LINE__);
68        return false;
69    }
70
71    uint32_t oldNumNodes = totalNodes_;
72    DFXLOGW("Before resize, totalNodes_: %{public}u, availableNodes_: %{public}u, " \
73        "availableIndex_: %{public}u  hashStep_: %{public}" PRIu64 "",
74        totalNodes_, availableNodes_, availableIndex_, hashStep_);
75
76    if ((totalNodes_ << RESIZE_MULTIPLE) > MAX_NODES_CNT) {
77        DFXLOGW("Hashtable size limit, resize failed current cnt: %{public}u, max cnt: %{public}u",
78            totalNodes_,
79            MAX_NODES_CNT);
80        return false;
81    }
82
83    uint32_t newtableSize = tableSize_ << RESIZE_MULTIPLE;
84    void* newTableBuf = mmap(NULL, newtableSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
85    if (newTableBuf == MAP_FAILED) {
86        return false;
87    }
88    prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, newTableBuf, newtableSize, "async_stack_table");
89    if (memcpy_s(newTableBuf, newtableSize, tableBufMMap_, tableSize_) != 0) {
90        DFXLOGE("Failed to memcpy table buffer");
91    }
92    munmap(tableBufMMap_, tableSize_);
93    tableBufMMap_ = newTableBuf;
94    tableSize_ = newtableSize;
95    deconflictTimes_ += DECONFLICT_INCREASE_STEP;
96    availableIndex_ += availableNodes_;
97    totalNodes_ = ((newtableSize / sizeof(Node)) >> 1) << 1; // make it even.
98    availableNodes_ = totalNodes_ - oldNumNodes;
99    if (availableNodes_ == 0) {
100        return false;
101    }
102    hashModulus_ = availableNodes_ - 1;
103    hashStep_ = availableNodes_ / (deconflictTimes_ * 2 + 1); // 2: double times
104    DFXLOGW("After resize, totalNodes_: %{public}u, availableNodes_: %{public}u, " \
105        "availableIndex_: %{public}u hashStep_: %{public}" PRIu64 "",
106        totalNodes_, availableNodes_, availableIndex_, hashStep_);
107    return true;
108}
109
110uint64_t UniqueStackTable::PutPcInSlot(uint64_t thisPc, uint64_t prevIdx)
111{
112    Node *tableHead = reinterpret_cast<Node *>(tableBufMMap_);
113    if (hashModulus_ == 0) {
114        DFXLOGW("The value of the hashModulus_ is zero\n");
115        return 0;
116    }
117    uint64_t curPcIdx = (((thisPc >> 2) ^ (prevIdx << 4)) % hashModulus_) + availableIndex_;
118    uint8_t currentDeconflictTimes_ = deconflictTimes_;
119
120    Node node;
121    node.section.pc = thisPc;
122    node.section.prevIdx = prevIdx;
123    node.section.inKernel = !!(thisPc & PC_IN_KERNEL);
124    while (currentDeconflictTimes_--) {
125        Node* tableNode = (Node*)tableHead + curPcIdx;
126
127        // empty case
128        if (tableNode->value == 0) {
129            tableNode->value = node.value;
130            usedSlots_.emplace_back(uint32_t(curPcIdx));
131            return curPcIdx;
132        }
133        // already inserted
134        if (tableNode->value == node.value) {
135            return curPcIdx;
136        }
137
138        curPcIdx += currentDeconflictTimes_ * hashStep_ + 1;
139        if (availableNodes_ == 0) {
140            return 0;
141        }
142        if (curPcIdx >= totalNodes_) {
143            // make sure index 0 do not occupy
144            curPcIdx -= (availableNodes_ - 1);
145        }
146    }
147
148    DFXLOGW("Collison unresolved, need resize, usedSlots_.size(): %{public}zu, curPcIdx: %{public}" PRIu64 "",
149        usedSlots_.size(), curPcIdx);
150    return 0;
151}
152
153// todo add lock
154uint64_t UniqueStackTable::PutPcsInTable(StackId *stackId, uintptr_t* pcs, size_t nr)
155{
156    if (!Init()) {
157        DFXLOGW("init Hashtable failed, fatal error!");
158        return 0;
159    }
160    std::lock_guard<std::mutex> guard(stackTableMutex_);
161    int64_t reverseIndex = static_cast<int64_t>(nr);
162    uint64_t prev = 0;
163    while (--reverseIndex >= 0) {
164        uint64_t pc = pcs[reverseIndex];
165
166        if (pc == 0) {
167            continue;
168        }
169        prev = PutPcInSlot(pc, prev);
170        if (prev == 0) {
171            return 0;
172        }
173    }
174
175    stackId->section.id = prev;
176    stackId->section.nr = static_cast<uint64_t>(nr);
177    return prev;
178}
179
180size_t UniqueStackTable::GetWriteSize()
181{
182    std::lock_guard<std::mutex> guard(stackTableMutex_);
183    if (tableBufMMap_ == nullptr) {
184        DFXLOGW("[%{public}d]: Hashtable not exist, fatal error!", __LINE__);
185        return 0;
186    }
187    size_t size = 0;
188    size += sizeof(pid_);
189    size += sizeof(tableSize_);
190    uint32_t usedNodes = usedSlots_.size();
191    size += sizeof(usedNodes);
192    size += usedNodes * sizeof(uint32_t); // key index
193    size += usedNodes * sizeof(uint64_t); // node value
194    return size;
195}
196
197Node* UniqueStackTable::GetFrame(uint64_t stackId)
198{
199    Node *tableHead = reinterpret_cast<Node *>(tableBufMMap_);
200    if (stackId >= totalNodes_) {
201        // should not occur
202        DFXLOGW("Failed to find frame by index: %{public}" PRIu64 "", stackId);
203        return nullptr;
204    }
205
206    return (Node *)&tableHead[stackId];
207}
208
209bool UniqueStackTable::GetPcsByStackId(StackId stackId, std::vector<uintptr_t>& pcs)
210{
211    std::lock_guard<std::mutex> guard(stackTableMutex_);
212    if (tableBufMMap_ == nullptr) {
213        DFXLOGW("Hashtable not exist, failed to find frame!");
214        return false;
215    }
216    uint64_t nr = stackId.section.nr;
217    uint64_t tailIdx = stackId.section.id;
218
219    Node *node = GetFrame(tailIdx);
220    while (nr-- && node != nullptr) {
221        pcs.push_back(
222            node->section.inKernel ? (node->section.pc | KERNEL_PREFIX) : node->section.pc);
223        if (node->section.prevIdx == HEAD_NODE_INDEX) {
224            break;
225        }
226        node = GetFrame(node->section.prevIdx);
227    }
228    return true;
229}
230
231bool UniqueStackTable::ImportNode(uint32_t index, const Node& node)
232{
233    std::lock_guard<std::mutex> guard(stackTableMutex_);
234    Node *tableHead = reinterpret_cast<Node *>(tableBufMMap_);
235    if (index >= tableSize_) {
236        return false;
237    }
238    tableHead[index].value = node.value;
239    return true;
240}
241}
242} // namespace OHOS
243