1 /*
2  * Copyright (c) 2022 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 
16 #include "param_trie.h"
17 
18 #include <errno.h>
19 
20 #include "init_param.h"
21 #include "param_base.h"
22 #include "param_manager.h"
23 #include "param_osadp.h"
24 #include "param_utils.h"
25 #include "param_include.h"
26 
27 #define OFFSET_ERR 0
28 
29 static uint32_t AllocateParamTrieNode(WorkSpace *workSpace, const char *key, uint32_t keyLen);
30 
GetRealFileName(WorkSpace * workSpace,char * buffer,uint32_t size)31 static int GetRealFileName(WorkSpace *workSpace, char *buffer, uint32_t size)
32 {
33     int ret = PARAM_SPRINTF(buffer, size, "%s/%s", PARAM_STORAGE_PATH, workSpace->fileName);
34     PARAM_CHECK(ret > 0, return -1, "Failed to copy file name %s", workSpace->fileName);
35     buffer[ret] = '\0';
36     return 0;
37 }
38 
InitWorkSpace_(WorkSpace * workSpace,uint32_t spaceSize,int readOnly)39 static int InitWorkSpace_(WorkSpace *workSpace, uint32_t spaceSize, int readOnly)
40 {
41     PARAM_CHECK(workSpace != NULL, return PARAM_CODE_INVALID_PARAM, "Invalid workSpace");
42     PARAM_CHECK(sizeof(ParamTrieHeader) < spaceSize,
43         return PARAM_CODE_INVALID_PARAM, "Invalid spaceSize %u name %s", spaceSize, workSpace->fileName);
44 
45     char buffer[FILENAME_LEN_MAX] = {0};
46     int ret = GetRealFileName(workSpace, buffer, sizeof(buffer));
47     PARAM_CHECK(ret == 0, return -1, "Failed to get file name %s", workSpace->fileName);
48     void *areaAddr = GetSharedMem(buffer, &workSpace->memHandle, spaceSize, readOnly);
49     PARAM_ONLY_CHECK(areaAddr != NULL, return PARAM_CODE_MEMORY_MAP_FAILED);
50     if (!readOnly) {
51         workSpace->area = (ParamTrieHeader *)areaAddr;
52         ATOMIC_UINT64_INIT(&workSpace->area->commitId, 0);
53         ATOMIC_UINT64_INIT(&workSpace->area->commitPersistId, 0);
54         workSpace->area->trieNodeCount = 0;
55         workSpace->area->paramNodeCount = 0;
56         workSpace->area->securityNodeCount = 0;
57         workSpace->area->dataSize = spaceSize - sizeof(ParamTrieHeader);
58         workSpace->area->spaceSizeOffset = 0;
59         workSpace->area->currOffset = 0;
60         uint32_t offset = AllocateParamTrieNode(workSpace, "#", 1);
61         workSpace->area->firstNode = offset;
62     } else {
63         workSpace->area = (ParamTrieHeader *)areaAddr;
64     }
65     PARAM_LOGV("InitWorkSpace success, readOnly %d currOffset %u firstNode %u dataSize %u",
66         readOnly, workSpace->area->currOffset, workSpace->area->firstNode, workSpace->area->dataSize);
67     return 0;
68 }
69 
AllocateParamTrieNode(WorkSpace * workSpace,const char * key,uint32_t keyLen)70 static uint32_t AllocateParamTrieNode(WorkSpace *workSpace, const char *key, uint32_t keyLen)
71 {
72     uint32_t len = keyLen + sizeof(ParamTrieNode) + 1;
73     len = PARAM_ALIGN(len);
74     PARAM_CHECK((workSpace->area->currOffset + len) < workSpace->area->dataSize, return 0,
75         "Failed to allocate currOffset %d, dataSize %d space %s",
76         workSpace->area->currOffset, workSpace->area->dataSize, workSpace->fileName);
77     ParamTrieNode *node = (ParamTrieNode *)(workSpace->area->data + workSpace->area->currOffset);
78     node->length = keyLen;
79     int ret = PARAM_MEMCPY(node->key, keyLen, key, keyLen);
80     PARAM_CHECK(ret == 0, return 0, "Failed to copy key");
81     node->key[keyLen] = '\0';
82     node->left = 0;
83     node->right = 0;
84     node->child = 0;
85     node->dataIndex = 0;
86     node->labelIndex = 0;
87     uint32_t offset = workSpace->area->currOffset;
88     workSpace->area->currOffset += len;
89     workSpace->area->trieNodeCount++;
90     return offset;
91 }
92 
InitWorkSpace(WorkSpace * workSpace,int onlyRead,uint32_t spaceSize)93 INIT_LOCAL_API int InitWorkSpace(WorkSpace *workSpace, int onlyRead, uint32_t spaceSize)
94 {
95     PARAM_CHECK(workSpace != NULL, return PARAM_CODE_INVALID_NAME, "Invalid workSpace");
96     if (PARAM_TEST_FLAG(workSpace->flags, WORKSPACE_FLAGS_INIT)) {
97         return 0;
98     }
99     int ret = InitWorkSpace_(workSpace, spaceSize, onlyRead);
100     PARAM_ONLY_CHECK(ret == 0, return ret);
101     PARAM_SET_FLAG(workSpace->flags, WORKSPACE_FLAGS_INIT);
102     PARAM_LOGV("InitWorkSpace %s for %s", workSpace->fileName, (onlyRead == 0) ? "init" : "other");
103     return ret;
104 }
105 
CloseWorkSpace(WorkSpace * workSpace)106 INIT_LOCAL_API void CloseWorkSpace(WorkSpace *workSpace)
107 {
108     PARAM_CHECK(workSpace != NULL, return, "The workspace is null");
109     PARAM_LOGV("CloseWorkSpace %s", workSpace->fileName);
110     if (!PARAM_TEST_FLAG(workSpace->flags, WORKSPACE_FLAGS_INIT)) {
111         return;
112     }
113     PARAM_CHECK(workSpace->area != NULL, return, "The workspace area is null");
114 #ifdef WORKSPACE_AREA_NEED_MUTEX
115     ParamRWMutexDelete(&workSpace->rwlock);
116 #endif
117     FreeSharedMem(&workSpace->memHandle, workSpace->area, workSpace->area->dataSize);
118     workSpace->area = NULL;
119 }
120 
CheckWorkSpace(const WorkSpace * workSpace)121 static int CheckWorkSpace(const WorkSpace *workSpace)
122 {
123     PARAM_CHECK(workSpace != NULL && workSpace->area != NULL, return PARAM_WORKSPACE_NOT_INIT, "The workspace is null");
124     if (!PARAM_TEST_FLAG(workSpace->flags, WORKSPACE_FLAGS_INIT)) {
125         return PARAM_WORKSPACE_NOT_INIT;
126     }
127     return 0;
128 }
129 
CompareParamTrieNode(const ParamTrieNode * node,const char * key,uint32_t keyLen)130 static int CompareParamTrieNode(const ParamTrieNode *node, const char *key, uint32_t keyLen)
131 {
132     if (node->length > keyLen) {
133         return -1;
134     } else if (node->length < keyLen) {
135         return 1;
136     }
137     return memcmp(node->key, key, keyLen);
138 }
139 
AddToSubTrie(WorkSpace * workSpace,ParamTrieNode * current,const char * key,uint32_t keyLen)140 static ParamTrieNode *AddToSubTrie(WorkSpace *workSpace, ParamTrieNode *current, const char *key, uint32_t keyLen)
141 {
142     if (current == NULL) {
143         return NULL;
144     }
145     ParamTrieNode *subTrie = NULL;
146     int ret = CompareParamTrieNode(current, key, keyLen);
147     if (ret == 0) {
148         return current;
149     }
150     if (ret < 0) {
151         subTrie = GetTrieNode(workSpace, current->left);
152         if (subTrie == NULL) {
153             uint32_t offset = AllocateParamTrieNode(workSpace, key, keyLen);
154             PARAM_CHECK(offset != 0, return NULL,
155                 "Failed to allocate key '%s' in space '%s'", key, workSpace->fileName);
156             SaveIndex(&current->left, offset);
157             return GetTrieNode(workSpace, current->left);
158         }
159     } else {
160         subTrie = GetTrieNode(workSpace, current->right);
161         if (subTrie == NULL) {
162             uint32_t offset = AllocateParamTrieNode(workSpace, key, keyLen);
163             PARAM_CHECK(offset != 0, return NULL,
164                 "Failed to allocate key '%s' in space '%s'", key, workSpace->fileName);
165             SaveIndex(&current->right, offset);
166             return GetTrieNode(workSpace, current->right);
167         }
168     }
169     return AddToSubTrie(workSpace, subTrie, key, keyLen);
170 }
171 
AddTrieNode(WorkSpace * workSpace,const char * key,uint32_t keyLen)172 ParamTrieNode *AddTrieNode(WorkSpace *workSpace, const char *key, uint32_t keyLen)
173 {
174     PARAM_CHECK(key != NULL && keyLen > 0, return NULL, "Invalid param ");
175     PARAM_CHECK(CheckWorkSpace(workSpace) == 0, return NULL, "Invalid workSpace %s", key);
176     const char *remainingKey = key;
177     ParamTrieNode *current = GetTrieRoot(workSpace);
178     PARAM_CHECK(current != NULL, return NULL, "Invalid current param %s", key);
179     while (1) {
180         uint32_t subKeyLen = 0;
181         char *subKey = NULL;
182         GetNextKey(&remainingKey, &subKey, &subKeyLen, key + keyLen);
183         if (!subKeyLen) {
184             return NULL;
185         }
186         if (current->child != 0) {  // 如果child存在，则检查是否匹配
187             ParamTrieNode *next = GetTrieNode(workSpace, current->child);
188             current = AddToSubTrie(workSpace, next, remainingKey, subKeyLen);
189         } else {
190             uint32_t dataOffset = AllocateParamTrieNode(workSpace, remainingKey, subKeyLen);
191             PARAM_CHECK(dataOffset != 0, return NULL,
192                 "Failed to allocate key '%s' in space '%s'", key, workSpace->fileName);
193             SaveIndex(&current->child, dataOffset);
194             current = (ParamTrieNode *)GetTrieNode(workSpace, current->child);
195         }
196         if (current == NULL) {
197             return NULL;
198         }
199         if (subKey == NULL || strcmp(subKey, ".") == 0) {
200             break;
201         }
202         remainingKey = subKey + 1;
203     }
204     return current;
205 }
206 
TraversalSubTrieNode(const WorkSpace * workSpace,const ParamTrieNode * current,TraversalTrieNodePtr walkFunc,const void * cookie)207 static int TraversalSubTrieNode(const WorkSpace *workSpace,
208     const ParamTrieNode *current, TraversalTrieNodePtr walkFunc, const void *cookie)
209 {
210     if (current == NULL) {
211         return 0;
212     }
213 
214     walkFunc(workSpace, (ParamTrieNode *)current, cookie);
215     TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->child), walkFunc, cookie);
216     TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->left), walkFunc, cookie);
217     TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->right), walkFunc, cookie);
218     return 0;
219 }
220 
TraversalTrieNode(const WorkSpace * workSpace,const ParamTrieNode * root,TraversalTrieNodePtr walkFunc,const void * cookie)221 INIT_LOCAL_API int TraversalTrieNode(const WorkSpace *workSpace,
222     const ParamTrieNode *root, TraversalTrieNodePtr walkFunc, const void *cookie)
223 {
224     PARAM_CHECK(walkFunc != NULL, return PARAM_CODE_INVALID_PARAM, "Invalid param");
225     PARAM_CHECK(CheckWorkSpace(workSpace) == 0, return PARAM_CODE_INVALID_PARAM, "Invalid workSpace");
226     ParamTrieNode *current = (ParamTrieNode *)root;
227     if (root == NULL) {
228         current = GetTrieRoot(workSpace);
229     }
230     PARAM_CHECK(current != NULL, return 0, "Invalid current node");
231     walkFunc(workSpace, (ParamTrieNode *)current, cookie);
232     TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->child), walkFunc, cookie);
233     if (root == NULL) {
234         TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->left), walkFunc, cookie);
235         TraversalSubTrieNode(workSpace, GetTrieNode(workSpace, current->right), walkFunc, cookie);
236     }
237     return 0;
238 }
239 
AddParamSecurityNode(WorkSpace * workSpace,const ParamAuditData * auditData)240 INIT_LOCAL_API uint32_t AddParamSecurityNode(WorkSpace *workSpace, const ParamAuditData *auditData)
241 {
242     PARAM_CHECK(CheckWorkSpace(workSpace) == 0, return OFFSET_ERR, "Invalid workSpace");
243     PARAM_CHECK(auditData != NULL, return OFFSET_ERR, "Invalid auditData");
244     uint32_t realLen = PARAM_ALIGN(sizeof(ParamSecurityNode) + sizeof(uid_t) * auditData->memberNum);
245     PARAM_CHECK((workSpace->area->currOffset + realLen) < workSpace->area->dataSize,
246         return OFFSET_ERR, "Failed to allocate currOffset %u, dataSize %u datalen %u",
247         workSpace->area->currOffset, workSpace->area->dataSize, realLen);
248     ParamSecurityNode *node = (ParamSecurityNode *)(workSpace->area->data + workSpace->area->currOffset);
249     node->uid = auditData->dacData.uid;
250     node->gid = auditData->dacData.gid;
251     node->mode = auditData->dacData.mode;
252     node->type = auditData->dacData.paramType & PARAM_TYPE_MASK;
253 #ifdef PARAM_SUPPORT_SELINUX
254     node->selinuxIndex = auditData->selinuxIndex;
255 #else
256     node->selinuxIndex = 0;
257 #endif
258     if (auditData->memberNum > 0) {
259         // copy member
260         int ret = PARAM_MEMCPY(node->members,
261             realLen - sizeof(ParamSecurityNode), auditData->members, auditData->memberNum * sizeof(uid_t));
262         PARAM_CHECK(ret == 0, return OFFSET_ERR, "Failed to copy members");
263     }
264     node->memberNum = auditData->memberNum;
265     uint32_t offset = workSpace->area->currOffset;
266     workSpace->area->currOffset += realLen;
267     workSpace->area->securityNodeCount++;
268     return offset;
269 }
270 
AddParamNode(WorkSpace * workSpace,uint8_t type,const char * key,uint32_t keyLen,const char * value,uint32_t valueLen,int mode)271 INIT_LOCAL_API uint32_t AddParamNode(WorkSpace *workSpace, uint8_t type,
272     const char *key, uint32_t keyLen, const char *value, uint32_t valueLen, int mode)
273 {
274     PARAM_CHECK(key != NULL && value != NULL, return OFFSET_ERR, "Invalid param");
275     PARAM_CHECK(CheckWorkSpace(workSpace) == 0, return OFFSET_ERR, "Invalid workSpace %s", key);
276 
277     uint32_t realLen = sizeof(ParamNode) + 1 + 1;
278     // for const parameter, alloc memory on demand
279     if ((valueLen > PARAM_VALUE_LEN_MAX) || IS_READY_ONLY(key)) {
280         realLen += keyLen + valueLen;
281     } else {
282         realLen += keyLen + GetParamMaxLen(type);
283     }
284     realLen = PARAM_ALIGN(realLen);
285     PARAM_CHECK((workSpace->area->currOffset + realLen) < workSpace->area->dataSize,
286         return OFFSET_ERR, "Failed to allocate currOffset %u, dataSize %u datalen %u",
287         workSpace->area->currOffset, workSpace->area->dataSize, realLen);
288 
289     ParamNode *node = (ParamNode *)(workSpace->area->data + workSpace->area->currOffset);
290     ATOMIC_INIT(&node->commitId, 0);
291 
292     node->type = type;
293     node->keyLength = keyLen;
294     node->valueLength = valueLen;
295     int ret = PARAM_SPRINTF(node->data, realLen, "%s=%s", key, value);
296     PARAM_CHECK(ret > 0, return OFFSET_ERR, "Failed to sprint key and value");
297 
298     if (((unsigned int)mode & LOAD_PARAM_PERSIST) != 0) {
299         node->commitId |= PARAM_FLAGS_PERSIST;
300     }
301     uint32_t offset = workSpace->area->currOffset;
302     workSpace->area->currOffset += realLen;
303     workSpace->area->paramNodeCount++;
304     return offset;
305 }
306 
SaveIndex(uint32_t * index,uint32_t offset)307 INIT_LOCAL_API void SaveIndex(uint32_t *index, uint32_t offset)
308 {
309     PARAM_ONLY_CHECK(index != NULL, return);
310     *index = offset;
311 }
312 
FindTrieNode(WorkSpace * workSpace,const char * key,uint32_t keyLen,uint32_t * matchLabel)313 INIT_LOCAL_API ParamTrieNode *FindTrieNode(WorkSpace *workSpace,
314     const char *key, uint32_t keyLen, uint32_t *matchLabel)
315 {
316     PARAM_ONLY_CHECK(key != NULL && keyLen > 0, return NULL);
317     PARAM_CHECK(workSpace != NULL, return NULL, "Invalid workspace for %s", key);
318     uint32_t tmpMatchLen = 0;
319     ParamTrieNode *node = NULL;
320     PARAMSPACE_AREA_RD_LOCK(workSpace);
321     node = FindTrieNode_(workSpace, key, keyLen, &tmpMatchLen);
322     PARAMSPACE_AREA_RW_UNLOCK(workSpace);
323     if (matchLabel != NULL) {
324         *matchLabel = tmpMatchLen;
325     }
326     if (node != NULL && node->dataIndex != 0) {
327         ParamNode *entry = (ParamNode *)GetTrieNode(workSpace, node->dataIndex);
328         if (entry != NULL && entry->keyLength == keyLen) {
329             return node;
330         }
331         return NULL;
332     }
333     return node;
334 }
335 
GetParamMaxLen(uint8_t type)336 INIT_LOCAL_API uint32_t GetParamMaxLen(uint8_t type)
337 {
338     static const uint32_t typeLengths[] = {
339         PARAM_VALUE_LEN_MAX, 32, 8 // 8 max bool length 32 max int length
340     };
341     if (type >= ARRAY_LENGTH(typeLengths)) {
342         return PARAM_VALUE_LEN_MAX;
343     }
344     return typeLengths[type];
345 }
346 
GetParamNode(uint32_t index,const char * name)347 INIT_LOCAL_API ParamNode *GetParamNode(uint32_t index, const char *name)
348 {
349     uint32_t labelIndex = 0;
350     WorkSpace *space = GetWorkSpace(index);
351     ParamTrieNode *entry = FindTrieNode(space, name, strlen(name), &labelIndex);
352     if (entry == NULL || entry->dataIndex == 0) {
353         return NULL;
354     }
355     return (ParamNode *)GetTrieNode(space, entry->dataIndex);
356 }
357 
AddParamEntry(uint32_t index,uint8_t type,const char * name,const char * value)358 INIT_LOCAL_API int AddParamEntry(uint32_t index, uint8_t type, const char *name, const char *value)
359 {
360     WorkSpace *workSpace = GetWorkSpace(WORKSPACE_INDEX_BASE);
361     PARAM_CHECK(workSpace != NULL, return PARAM_CODE_ERROR, "Invalid workspace");
362     ParamTrieNode *node = FindTrieNode(workSpace, name, strlen(name), NULL);
363     if (node != NULL && node->dataIndex != 0) {
364         return 0;
365     }
366     node = AddTrieNode(workSpace, name, strlen(name));
367     PARAM_CHECK(node != NULL, return PARAM_CODE_REACHED_MAX, "Failed to add node");
368     ParamNode *entry = (ParamNode *)GetTrieNode(workSpace, node->dataIndex);
369     if (entry == NULL) {
370         uint32_t offset = AddParamNode(workSpace, type, name, strlen(name), value, strlen(value), 0);
371         PARAM_CHECK(offset > 0, return PARAM_CODE_REACHED_MAX, "Failed to allocate name %s", name);
372         SaveIndex(&node->dataIndex, offset);
373     }
374     return 0;
375 }
376 
AddSecurityLabel(const ParamAuditData * auditData)377 INIT_LOCAL_API int AddSecurityLabel(const ParamAuditData *auditData)
378 {
379     PARAM_CHECK(auditData != NULL && auditData->name != NULL, return PARAM_CODE_INVALID_PARAM, "Invalid auditData");
380     WorkSpace *workSpace = GetWorkSpace(WORKSPACE_INDEX_DAC);
381     PARAM_CHECK(workSpace != NULL, return PARAM_WORKSPACE_NOT_INIT, "Invalid workSpace");
382     ParamTrieNode *node = GetTrieRoot(workSpace);
383     if ((node == NULL) || (CompareParamTrieNode(node, auditData->name, strlen(auditData->name)) != 0)) {
384         node = FindTrieNode(workSpace, auditData->name, strlen(auditData->name), NULL);
385         if (node == NULL) {
386             node = AddTrieNode(workSpace, auditData->name, strlen(auditData->name));
387         }
388         PARAM_CHECK(node != NULL, return PARAM_CODE_REACHED_MAX, "Failed to add node %s", auditData->name);
389     }
390     uint32_t offset = node->labelIndex;
391     if (node->labelIndex == 0) {  // can not support update for label
392         offset = AddParamSecurityNode(workSpace, auditData);
393         PARAM_CHECK(offset > 0, return PARAM_CODE_REACHED_MAX, "Failed to add label");
394         SaveIndex(&node->labelIndex, offset);
395     } else {
396         ParamSecurityNode *label = (ParamSecurityNode *)GetTrieNode(workSpace, node->labelIndex);
397         PARAM_CHECK(label != NULL, return -1, "Failed to get trie node");
398 #ifdef PARAM_SUPPORT_SELINUX
399         if (auditData->selinuxIndex != 0) {
400             label->selinuxIndex = auditData->selinuxIndex;
401         } else
402 #endif
403         {
404 #ifdef STARTUP_INIT_TEST
405             label->mode = auditData->dacData.mode;
406             label->uid = auditData->dacData.uid;
407             label->gid = auditData->dacData.gid;
408             label->type = auditData->dacData.paramType & PARAM_TYPE_MASK;
409 #endif
410             PARAM_LOGV("Repeat to add label for name %s", auditData->name);
411         }
412     }
413     PARAM_LOGV("AddSecurityLabel label %d gid %d uid %d mode %o type:%d name: %s", offset,
414         auditData->dacData.gid, auditData->dacData.uid, auditData->dacData.mode,
415         auditData->dacData.paramType, auditData->name);
416     return 0;
417 }
418