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"
21 namespace OHOS {
22 namespace HiviewDFX {
Instance()23 UniqueStackTable* UniqueStackTable::Instance()
24 {
25     static UniqueStackTable* instance = new UniqueStackTable();
26     return instance;
27 }
28 
Init()29 bool 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         LOGW("%s", "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         LOGW("%s", "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     LOGD(
57         "Init totalNodes_: %u, availableNodes_: %u, availableIndex_: %u \
58         hashStep_: %" PRIu64 ", hashModulus_: %u",
59         totalNodes_, availableNodes_, availableIndex_, hashStep_, hashModulus_);
60     return true;
61 }
62 
Resize()63 bool UniqueStackTable::Resize()
64 {
65     std::lock_guard<std::mutex> guard(stackTableMutex_);
66     if (tableBufMMap_ == nullptr) {
67         LOGW("%s", "Hashtable not exist, fatal error!");
68         return false;
69     }
70 
71     uint32_t oldNumNodes = totalNodes_;
72     LOGW("Before resize, totalNodes_: %u, availableNodes_: %u, \
73         availableIndex_: %u  hashStep_: %" PRIu64 "",
74         totalNodes_, availableNodes_, availableIndex_, hashStep_);
75 
76     if ((totalNodes_ << RESIZE_MULTIPLE) > MAX_NODES_CNT) {
77         LOGW("Hashtable size limit, resize failed current cnt: %u, max cnt: %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         LOGE("%s", "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     LOGW("After resize, totalNodes_: %u, availableNodes_: %u, \
105         availableIndex_: %u hashStep_: %" PRIu64 "",
106         totalNodes_, availableNodes_, availableIndex_, hashStep_);
107     return true;
108 }
109 
PutPcInSlot(uint64_t thisPc,uint64_t prevIdx)110 uint64_t UniqueStackTable::PutPcInSlot(uint64_t thisPc, uint64_t prevIdx)
111 {
112     Node *tableHead = reinterpret_cast<Node *>(tableBufMMap_);
113     if (hashModulus_ == 0) {
114         LOGW("%s", "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     LOGW("Collison unresolved, need resize, usedSlots_.size(): %zu, curPcIdx: %" PRIu64 "",
149         usedSlots_.size(), curPcIdx);
150     return 0;
151 }
152 
153 // todo add lock
PutPcsInTable(StackId * stackId,uintptr_t * pcs,size_t nr)154 uint64_t UniqueStackTable::PutPcsInTable(StackId *stackId, uintptr_t* pcs, size_t nr)
155 {
156     if (!Init()) {
157         LOGW("%s", "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 
GetWriteSize()180 size_t UniqueStackTable::GetWriteSize()
181 {
182     std::lock_guard<std::mutex> guard(stackTableMutex_);
183     if (tableBufMMap_ == nullptr) {
184         LOGW("%s", "Hashtable not exist, fatal error!");
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 
GetFrame(uint64_t stackId)197 Node* UniqueStackTable::GetFrame(uint64_t stackId)
198 {
199     Node *tableHead = reinterpret_cast<Node *>(tableBufMMap_);
200     if (stackId >= totalNodes_) {
201         // should not occur
202         LOGW("Failed to find frame by index: %" PRIu64 "", stackId);
203         return nullptr;
204     }
205 
206     return (Node *)&tableHead[stackId];
207 }
208 
GetPcsByStackId(StackId stackId,std::vector<uintptr_t> & pcs)209 bool UniqueStackTable::GetPcsByStackId(StackId stackId, std::vector<uintptr_t>& pcs)
210 {
211     std::lock_guard<std::mutex> guard(stackTableMutex_);
212     if (tableBufMMap_ == nullptr) {
213         LOGW("%s", "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 
ImportNode(uint32_t index,const Node & node)231 bool 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