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#ifndef HIEPRF_UNIQUE_STACK_TABLE_H
16#define HIEPRF_UNIQUE_STACK_TABLE_H
17#include "utilities.h"
18#include <cinttypes>
19#include <linux/perf_event.h>
20#include <string>
21namespace OHOS {
22namespace Developtools {
23namespace HiPerf {
24
25#define ADDR_BIT_LENGTH        40
26#define IDX_BIT_LENGTH         23
27#define KERNEL_FLAG_BIT_LENGTH 1
28#define DECONFLICT_INCREASE_STEP  3
29#define RESIZE_MULTIPLE          2
30#define NR_BIT_LENGTH          41
31
32constexpr uint32_t INITIAL_TABLE_SIZE = 4 * 1024 * 1024;
33constexpr uint32_t MAX_NODES_CNT = 1 << IDX_BIT_LENGTH ;
34constexpr uint64_t IP_IN_KERNEL = 1uLL << 63;
35constexpr uint64_t HEAD_NODE_INDEX = 0;
36// FFFFFF0000000000
37constexpr uint64_t KERNEL_PREFIX = 0xFFFFFFull << 40;
38constexpr uint8_t INIT_DECONFLICT_ALLOWED = 22;
39constexpr uint8_t HASH_STEP_BASE_MULTIPLE = 2;
40constexpr uint8_t HASH_STEP_BASE_NUM = 1;
41
42// align
43#pragma pack(push, 4)
44
45union Node {
46    uint64_t value;
47    struct {
48        uint64_t ip : ADDR_BIT_LENGTH;
49        uint64_t prevIdx : IDX_BIT_LENGTH;
50        uint64_t inKernel : KERNEL_FLAG_BIT_LENGTH;
51    } section;
52};
53
54struct UniStackNode {
55    uint32_t index;
56    Node node;
57};
58
59struct UniStackTableInfo {
60    uint32_t pid;
61    uint32_t tableSize;
62    uint32_t numNodes;
63    std::vector<UniStackNode> nodes;
64};
65
66union StackId {
67    uint64_t value;
68    struct {
69        uint64_t id : IDX_BIT_LENGTH;
70        uint64_t nr : NR_BIT_LENGTH;
71    } section;
72};
73
74#pragma pack(pop)
75static_assert(sizeof(Node) == 8, "Node size must be 8 byte");
76
77class UniqueStackTable {
78public:
79    bool Init();
80    explicit UniqueStackTable(pid_t pid) : pid_(pid)
81    {
82        Init();
83    }
84
85    UniqueStackTable(pid_t pid, uint32_t size) : pid_(pid), tableSize_(size)
86    {
87        Init();
88    }
89    ~UniqueStackTable()
90    {
91        tableBuf_ = nullptr;
92    }
93
94    uint64_t PutIpsInTable(StackId *stackId, u64 *ips, u64 nr);
95    bool GetIpsByStackId(const StackId stackId, std::vector<u64>& ips);
96    bool ImportNode(uint32_t index, const Node& node);
97    size_t GetWriteSize();
98
99    bool Resize();
100
101    uint32_t GetPid()
102    {
103        return pid_;
104    }
105
106    uint32_t GetTabelSize()
107    {
108        return tableSize_;
109    }
110
111    std::vector<uint32_t>& GetUsedIndexes()
112    {
113        return usedSlots_;
114    }
115
116    Node* GetHeadNode()
117    {
118        return reinterpret_cast<Node *>(tableBuf_.get());
119    }
120
121private:
122    Node* GetFrame(uint64_t stackId);
123    uint64_t PutIpInSlot(uint64_t thisIp, uint64_t prevIdx);
124    u32 pid_;
125    uint32_t tableSize_ = INITIAL_TABLE_SIZE;
126    std::unique_ptr<uint8_t[]> tableBuf_ = nullptr;
127    std::vector<uint32_t> usedSlots_;
128    uint32_t totalNodes_ = 0;
129    // current available node count, include index 0
130    uint32_t availableNodes_ = 0;
131    uint32_t hashModulus_ = 1;
132    // 0 for reserved, start from 1
133    uint32_t availableIndex_ = 1;
134    // for de-conflict
135    uint64_t hashStep_ = 0;
136    uint8_t deconflictTimes_ = INIT_DECONFLICT_ALLOWED;
137};
138
139using ProcessStackMap = std::map<pid_t, std::shared_ptr<UniqueStackTable>>;
140} // namespace HiPerf
141} // namespace Developtools
142} // namespace OHOS
143#endif // HIEPRF_UNIQUE_STACK_TABLE_H