1 // 2 // Copyright (C) 2017 The Android Open Source Project 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 17 #include "property_info_parser/property_info_parser.h" 18 19 #include <fcntl.h> 20 #include <string.h> 21 #include <sys/mman.h> 22 #include <sys/stat.h> 23 #include <sys/types.h> 24 #include <unistd.h> 25 26 namespace android { 27 namespace properties { 28 29 namespace { 30 31 // Binary search to find index of element in an array compared via f(search). 32 template <typename F> 33 int Find(uint32_t array_length, F&& f) { 34 int bottom = 0; 35 int top = array_length - 1; 36 while (top >= bottom) { 37 int search = (top + bottom) / 2; 38 39 auto cmp = f(search); 40 41 if (cmp == 0) return search; 42 if (cmp < 0) bottom = search + 1; 43 if (cmp > 0) top = search - 1; 44 } 45 return -1; 46 } 47 48 } // namespace 49 50 // Binary search the list of contexts to find the index of a given context string. 51 // Only should be used for TrieSerializer to construct the Trie. 52 int PropertyInfoArea::FindContextIndex(const char* context) const { 53 return Find(num_contexts(), [this, context](auto array_offset) { 54 auto string_offset = uint32_array(contexts_array_offset())[array_offset]; 55 return strcmp(c_string(string_offset), context); 56 }); 57 } 58 59 // Binary search the list of types to find the index of a given type string. 60 // Only should be used for TrieSerializer to construct the Trie. 61 int PropertyInfoArea::FindTypeIndex(const char* type) const { 62 return Find(num_types(), [this, type](auto array_offset) { 63 auto string_offset = uint32_array(types_array_offset())[array_offset]; 64 return strcmp(c_string(string_offset), type); 65 }); 66 } 67 68 // Binary search the list of children nodes to find a TrieNode for a given property piece. 69 // Used to traverse the Trie in GetPropertyInfoIndexes(). 70 bool TrieNode::FindChildForString(const char* name, uint32_t namelen, TrieNode* child) const { 71 auto node_index = Find(trie_node_base_->num_child_nodes, [this, name, namelen](auto array_offset) { 72 const char* child_name = child_node(array_offset).name(); 73 int cmp = strncmp(child_name, name, namelen); 74 if (cmp == 0 && child_name[namelen] != '\0') { 75 // We use strncmp() since name isn't null terminated, but we don't want to match only a 76 // prefix of a child node's name, so we check here if we did only match a prefix and 77 // return 1, to indicate to the binary search to search earlier in the array for the real 78 // match. 79 return 1; 80 } 81 return cmp; 82 }); 83 84 if (node_index == -1) { 85 return false; 86 } 87 *child = child_node(node_index); 88 return true; 89 } 90 91 void PropertyInfoArea::CheckPrefixMatch(const char* remaining_name, const TrieNode& trie_node, 92 uint32_t* context_index, uint32_t* type_index) const { 93 const uint32_t remaining_name_size = strlen(remaining_name); 94 for (uint32_t i = 0; i < trie_node.num_prefixes(); ++i) { 95 auto prefix_len = trie_node.prefix(i)->namelen; 96 if (prefix_len > remaining_name_size) continue; 97 98 if (!strncmp(c_string(trie_node.prefix(i)->name_offset), remaining_name, prefix_len)) { 99 if (trie_node.prefix(i)->context_index != ~0u) { 100 *context_index = trie_node.prefix(i)->context_index; 101 } 102 if (trie_node.prefix(i)->type_index != ~0u) { 103 *type_index = trie_node.prefix(i)->type_index; 104 } 105 return; 106 } 107 } 108 } 109 110 void PropertyInfoArea::GetPropertyInfoIndexes(const char* name, uint32_t* context_index, 111 uint32_t* type_index) const { 112 uint32_t return_context_index = ~0u; 113 uint32_t return_type_index = ~0u; 114 const char* remaining_name = name; 115 auto trie_node = root_node(); 116 while (true) { 117 const char* sep = strchr(remaining_name, '.'); 118 119 // Apply prefix match for prefix deliminated with '.' 120 if (trie_node.context_index() != ~0u) { 121 return_context_index = trie_node.context_index(); 122 } 123 if (trie_node.type_index() != ~0u) { 124 return_type_index = trie_node.type_index(); 125 } 126 127 // Check prefixes at this node. This comes after the node check since these prefixes are by 128 // definition longer than the node itself. 129 CheckPrefixMatch(remaining_name, trie_node, &return_context_index, &return_type_index); 130 131 if (sep == nullptr) { 132 break; 133 } 134 135 const uint32_t substr_size = sep - remaining_name; 136 TrieNode child_node; 137 if (!trie_node.FindChildForString(remaining_name, substr_size, &child_node)) { 138 break; 139 } 140 141 trie_node = child_node; 142 remaining_name = sep + 1; 143 } 144 145 // We've made it to a leaf node, so check contents and return appropriately. 146 // Check exact matches 147 for (uint32_t i = 0; i < trie_node.num_exact_matches(); ++i) { 148 if (!strcmp(c_string(trie_node.exact_match(i)->name_offset), remaining_name)) { 149 if (context_index != nullptr) { 150 if (trie_node.exact_match(i)->context_index != ~0u) { 151 *context_index = trie_node.exact_match(i)->context_index; 152 } else { 153 *context_index = return_context_index; 154 } 155 } 156 if (type_index != nullptr) { 157 if (trie_node.exact_match(i)->type_index != ~0u) { 158 *type_index = trie_node.exact_match(i)->type_index; 159 } else { 160 *type_index = return_type_index; 161 } 162 } 163 return; 164 } 165 } 166 // Check prefix matches for prefixes not deliminated with '.' 167 CheckPrefixMatch(remaining_name, trie_node, &return_context_index, &return_type_index); 168 // Return previously found prefix match. 169 if (context_index != nullptr) *context_index = return_context_index; 170 if (type_index != nullptr) *type_index = return_type_index; 171 return; 172 } 173 174 void PropertyInfoArea::GetPropertyInfo(const char* property, const char** context, 175 const char** type) const { 176 uint32_t context_index; 177 uint32_t type_index; 178 GetPropertyInfoIndexes(property, &context_index, &type_index); 179 if (context != nullptr) { 180 if (context_index == ~0u) { 181 *context = nullptr; 182 } else { 183 *context = this->context(context_index); 184 } 185 } 186 if (type != nullptr) { 187 if (type_index == ~0u) { 188 *type = nullptr; 189 } else { 190 *type = this->type(type_index); 191 } 192 } 193 } 194 195 bool PropertyInfoAreaFile::LoadDefaultPath() { 196 return LoadPath("/dev/__properties__/property_info"); 197 } 198 199 bool PropertyInfoAreaFile::LoadPath(const char* filename) { 200 int fd = open(filename, O_CLOEXEC | O_NOFOLLOW | O_RDONLY); 201 202 struct stat fd_stat; 203 if (fstat(fd, &fd_stat) < 0) { 204 close(fd); 205 return false; 206 } 207 208 if ((fd_stat.st_uid != 0) || (fd_stat.st_gid != 0) || 209 ((fd_stat.st_mode & (S_IWGRP | S_IWOTH)) != 0) || 210 (fd_stat.st_size < static_cast<off_t>(sizeof(PropertyInfoArea)))) { 211 close(fd); 212 return false; 213 } 214 215 auto mmap_size = fd_stat.st_size; 216 217 void* map_result = mmap(nullptr, mmap_size, PROT_READ, MAP_SHARED, fd, 0); 218 if (map_result == MAP_FAILED) { 219 close(fd); 220 return false; 221 } 222 223 auto property_info_area = reinterpret_cast<PropertyInfoArea*>(map_result); 224 if (property_info_area->minimum_supported_version() > 1 || 225 property_info_area->size() != mmap_size) { 226 munmap(map_result, mmap_size); 227 close(fd); 228 return false; 229 } 230 231 close(fd); 232 mmap_base_ = map_result; 233 mmap_size_ = mmap_size; 234 return true; 235 } 236 237 void PropertyInfoAreaFile::Reset() { 238 if (mmap_size_ > 0) { 239 munmap(mmap_base_, mmap_size_); 240 } 241 mmap_base_ = nullptr; 242 mmap_size_ = 0; 243 } 244 245 } // namespace properties 246 } // namespace android 247
