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 "sehap_contexts_trie.h"
16 #include <deque>
17
18 #include "src/callbacks.h"
19 #include "selinux/selinux.h"
20 #include "selinux_log.h"
21 #include <iostream>
22
SplitString(const std::string & paraName)23 std::vector<std::string> SehapContextsTrie::SplitString(const std::string& paraName)
24 {
25 std::vector<std::string> words;
26 std::string delimiter = ".";
27 size_t len = paraName.length();
28 size_t index = 0;
29 while (index < len) {
30 size_t pos;
31 if ((pos = paraName.substr(index).find(delimiter)) == std::string::npos) {
32 break;
33 }
34 std::string element = paraName.substr(index, pos);
35 if (!element.empty()) {
36 words.emplace_back(element);
37 }
38 index += pos + delimiter.length();
39 }
40 if (!paraName.substr(index).empty()) {
41 words.emplace_back(paraName.substr(index));
42 }
43 return words;
44 }
45
FindChild(const std::string & element)46 SehapContextsTrie* SehapContextsTrie::FindChild(const std::string& element)
47 {
48 SehapContextsTrie* node = this;
49 auto iter = node->children.find(element);
50 if (iter != node->children.end()) {
51 return iter->second;
52 }
53 return nullptr;
54 }
55
Insert(const std::string & domain,const std::string & type,const std::string & extension)56 void NodeTypeInfo::Insert(const std::string& domain, const std::string& type, const std::string& extension)
57 {
58 if (!extension.empty()) {
59 ExtensionInfo extInfo;
60 extInfo.domain = domain;
61 extensionMap[extension] = extInfo;
62 } else {
63 this->domain = domain;
64 this->type = type;
65 }
66 this->isEnd = true;
67 }
68
Insert(const std::string & paraName,const std::string & domain,const std::string & type,const std::string & extension)69 bool SehapContextsTrie::Insert(const std::string& paraName, const std::string& domain,
70 const std::string& type, const std::string& extension)
71 {
72 SehapContextsTrie* node = this;
73 std::vector<std::string> words = SplitString(paraName);
74 for (const std::string& word : words) {
75 if (word == "*") {
76 break;
77 }
78 if (node->children[word] == nullptr) {
79 node->children[word] = new (std::nothrow) SehapContextsTrie();
80 if (node->children[word] == nullptr) {
81 selinux_log(SELINUX_ERROR, "new child sehapcontextstrie failed!");
82 return false;
83 }
84 }
85 node = node->children[word];
86 }
87
88 if ((paraName.back() == '.') || (paraName.back() == '*')) {
89 node->prefixInfo.Insert(domain, type, extension);
90 } else {
91 node->matchedInfo.Insert(domain, type, extension);
92 }
93
94 return true;
95 }
96
Search(bool isDomain,const std::string & extension) const97 std::string NodeTypeInfo::Search(bool isDomain, const std::string& extension) const
98 {
99 if (isDomain && !extension.empty()) {
100 auto it = extensionMap.find(extension);
101 if (it != extensionMap.end()) {
102 return it->second.domain;
103 }
104 }
105 return isDomain ? domain : type;
106 }
107
Search(const std::string & paraName,bool isDomain,const std::string & extension)108 std::string SehapContextsTrie::Search(const std::string& paraName, bool isDomain, const std::string& extension)
109 {
110 std::vector<std::string> words = SplitString(paraName);
111 std::string type = "";
112 SehapContextsTrie* root = this;
113 for (size_t i = 0; i < words.size(); i++) {
114 const std::string& word = words[i];
115 auto child = root->FindChild(word);
116 if (child == nullptr) {
117 break;
118 }
119 root = child;
120 if ((root->prefixInfo.isEnd) && (i != words.size() - 1)) {
121 type = root->prefixInfo.Search(isDomain, extension);
122 }
123 if ((root->matchedInfo.isEnd) && (i == words.size() - 1)) {
124 type = root->matchedInfo.Search(isDomain, extension);
125 }
126 }
127 return type;
128 }
129
Clear()130 void SehapContextsTrie::Clear()
131 {
132 SehapContextsTrie* root = this;
133 std::deque<SehapContextsTrie*> nodeDeque;
134 for (auto child : root->children) {
135 nodeDeque.emplace_back(child.second);
136 }
137 while (!nodeDeque.empty()) {
138 root = nodeDeque.front();
139 nodeDeque.pop_front();
140 if (root != nullptr) {
141 for (auto child : root->children) {
142 nodeDeque.emplace_back(child.second);
143 }
144 delete root;
145 }
146 }
147 }