Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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> |
Dan Albert | 629c292 | 2017-12-13 13:41:14 -0800 | [diff] [blame] | 24 | #include <unistd.h> |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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 | |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 59 | // Binary search the list of types to find the index of a given type string. |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 60 | // Only should be used for TrieSerializer to construct the Trie. |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 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); |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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 | |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 91 | void PropertyInfoArea::CheckPrefixMatch(const char* remaining_name, const TrieNode& trie_node, |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 92 | uint32_t* context_index, uint32_t* type_index) const { |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 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)) { |
Tom Cherry | f5ed661 | 2017-12-19 15:46:07 -0800 | [diff] [blame] | 99 | if (trie_node.prefix(i)->context_index != ~0u) { |
| 100 | *context_index = trie_node.prefix(i)->context_index; |
| 101 | } |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 102 | if (trie_node.prefix(i)->type_index != ~0u) { |
| 103 | *type_index = trie_node.prefix(i)->type_index; |
Tom Cherry | f5ed661 | 2017-12-19 15:46:07 -0800 | [diff] [blame] | 104 | } |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 105 | return; |
| 106 | } |
| 107 | } |
| 108 | } |
| 109 | |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 110 | void PropertyInfoArea::GetPropertyInfoIndexes(const char* name, uint32_t* context_index, |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 111 | uint32_t* type_index) const { |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 112 | uint32_t return_context_index = ~0u; |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 113 | uint32_t return_type_index = ~0u; |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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 | } |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 123 | if (trie_node.type_index() != ~0u) { |
| 124 | return_type_index = trie_node.type_index(); |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 125 | } |
| 126 | |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 127 | // Check prefixes at this node. This comes after the node check since these prefixes are by |
| 128 | // definition longer than the node itself. |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 129 | CheckPrefixMatch(remaining_name, trie_node, &return_context_index, &return_type_index); |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 130 | |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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)) { |
Tom Cherry | f5ed661 | 2017-12-19 15:46:07 -0800 | [diff] [blame] | 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 | } |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 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; |
Tom Cherry | f5ed661 | 2017-12-19 15:46:07 -0800 | [diff] [blame] | 159 | } else { |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 160 | *type_index = return_type_index; |
Tom Cherry | f5ed661 | 2017-12-19 15:46:07 -0800 | [diff] [blame] | 161 | } |
| 162 | } |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 163 | return; |
| 164 | } |
| 165 | } |
| 166 | // Check prefix matches for prefixes not deliminated with '.' |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 167 | CheckPrefixMatch(remaining_name, trie_node, &return_context_index, &return_type_index); |
Tom Cherry | 26eba28 | 2017-12-13 00:29:30 -0800 | [diff] [blame] | 168 | // Return previously found prefix match. |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 169 | if (context_index != nullptr) *context_index = return_context_index; |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 170 | if (type_index != nullptr) *type_index = return_type_index; |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 171 | return; |
| 172 | } |
| 173 | |
| 174 | void PropertyInfoArea::GetPropertyInfo(const char* property, const char** context, |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 175 | const char** type) const { |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 176 | uint32_t context_index; |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 177 | uint32_t type_index; |
| 178 | GetPropertyInfoIndexes(property, &context_index, &type_index); |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 179 | if (context != nullptr) { |
| 180 | if (context_index == ~0u) { |
| 181 | *context = nullptr; |
| 182 | } else { |
| 183 | *context = this->context(context_index); |
| 184 | } |
| 185 | } |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 186 | if (type != nullptr) { |
| 187 | if (type_index == ~0u) { |
| 188 | *type = nullptr; |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 189 | } else { |
Tom Cherry | 4094e5e | 2018-01-11 16:26:10 -0800 | [diff] [blame] | 190 | *type = this->type(type_index); |
Tom Cherry | d853f77 | 2017-10-27 15:18:02 -0700 | [diff] [blame] | 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 |