1 /* 2 * Copyright (C) 2008 The Android Open Source Project 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in 12 * the documentation and/or other materials provided with the 13 * distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 #pragma once 30 31 #include <stdatomic.h> 32 #include <stdint.h> 33 #include <string.h> 34 #include <sys/mman.h> 35 36 #include "platform/bionic/macros.h" 37 38 #include "prop_info.h" 39 40 // Properties are stored in a hybrid trie/binary tree structure. 41 // Each property's name is delimited at '.' characters, and the tokens are put 42 // into a trie structure. Siblings at each level of the trie are stored in a 43 // binary tree. For instance, "ro.secure"="1" could be stored as follows: 44 // 45 // +-----+ children +----+ children +--------+ 46 // | |-------------->| ro |-------------->| secure | 47 // +-----+ +----+ +--------+ 48 // / \ / | 49 // left / \ right left / | prop +===========+ 50 // v v v +-------->| ro.secure | 51 // +-----+ +-----+ +-----+ +-----------+ 52 // | net | | sys | | com | | 1 | 53 // +-----+ +-----+ +-----+ +===========+ 54 55 // Represents a node in the trie. 56 struct prop_bt { 57 uint32_t namelen; 58 59 // The property trie is updated only by the init process (single threaded) which provides 60 // property service. And it can be read by multiple threads at the same time. 61 // As the property trie is not protected by locks, we use atomic_uint_least32_t types for the 62 // left, right, children "pointers" in the trie node. To make sure readers who see the 63 // change of "pointers" can also notice the change of prop_bt structure contents pointed by 64 // the "pointers", we always use release-consume ordering pair when accessing these "pointers". 65 66 // prop "points" to prop_info structure if there is a propery associated with the trie node. 67 // Its situation is similar to the left, right, children "pointers". So we use 68 // atomic_uint_least32_t and release-consume ordering to protect it as well. 69 70 // We should also avoid rereading these fields redundantly, since not 71 // all processor implementations ensure that multiple loads from the 72 // same field are carried out in the right order. 73 atomic_uint_least32_t prop; 74 75 atomic_uint_least32_t left; 76 atomic_uint_least32_t right; 77 78 atomic_uint_least32_t children; 79 80 char name[0]; 81 prop_btprop_bt82 prop_bt(const char* name, const uint32_t name_length) { 83 this->namelen = name_length; 84 memcpy(this->name, name, name_length); 85 this->name[name_length] = '\0'; 86 } 87 88 private: 89 BIONIC_DISALLOW_COPY_AND_ASSIGN(prop_bt); 90 }; 91 92 class prop_area { 93 public: 94 static prop_area* map_prop_area_rw(const char* filename, const char* context, 95 bool* fsetxattr_failed); 96 static prop_area* map_prop_area(const char* filename); unmap_prop_area(prop_area ** pa)97 static void unmap_prop_area(prop_area** pa) { 98 if (*pa) { 99 munmap(*pa, pa_size_); 100 *pa = nullptr; 101 } 102 } 103 prop_area(const uint32_t magic,const uint32_t version)104 prop_area(const uint32_t magic, const uint32_t version) : magic_(magic), version_(version) { 105 atomic_init(&serial_, 0u); 106 memset(reserved_, 0, sizeof(reserved_)); 107 // Allocate enough space for the root node. 108 bytes_used_ = sizeof(prop_bt); 109 // To make property reads wait-free, we reserve a 110 // PROP_VALUE_MAX-sized block of memory, the "dirty backup area", 111 // just after the root node. When we're about to modify a 112 // property, we copy the old value into the dirty backup area and 113 // copy the new value into the prop_info structure. Before 114 // starting the latter copy, we mark the property's serial as 115 // being dirty. If a reader comes along while we're doing the 116 // property update and sees a dirty serial, the reader copies from 117 // the dirty backup area instead of the property value 118 // proper. After the copy, the reader checks whether the property 119 // serial is the same: if it is, the dirty backup area hasn't been 120 // reused for something else and we can complete the 121 // read immediately. 122 bytes_used_ += __BIONIC_ALIGN(PROP_VALUE_MAX, sizeof(uint_least32_t)); 123 } 124 125 const prop_info* find(const char* name); 126 bool add(const char* name, unsigned int namelen, const char* value, unsigned int valuelen); 127 128 bool foreach (void (*propfn)(const prop_info* pi, void* cookie), void* cookie); 129 serial()130 atomic_uint_least32_t* serial() { 131 return &serial_; 132 } magic()133 uint32_t magic() const { 134 return magic_; 135 } version()136 uint32_t version() const { 137 return version_; 138 } dirty_backup_area()139 char* dirty_backup_area() { 140 return data_ + sizeof (prop_bt); 141 } 142 143 private: 144 static prop_area* map_fd_ro(const int fd); 145 146 void* allocate_obj(const size_t size, uint_least32_t* const off); 147 prop_bt* new_prop_bt(const char* name, uint32_t namelen, uint_least32_t* const off); 148 prop_info* new_prop_info(const char* name, uint32_t namelen, const char* value, uint32_t valuelen, 149 uint_least32_t* const off); 150 void* to_prop_obj(uint_least32_t off); 151 prop_bt* to_prop_bt(atomic_uint_least32_t* off_p); 152 prop_info* to_prop_info(atomic_uint_least32_t* off_p); 153 154 prop_bt* root_node(); 155 156 prop_bt* find_prop_bt(prop_bt* const bt, const char* name, uint32_t namelen, bool alloc_if_needed); 157 158 const prop_info* find_property(prop_bt* const trie, const char* name, uint32_t namelen, 159 const char* value, uint32_t valuelen, bool alloc_if_needed); 160 161 bool foreach_property(prop_bt* const trie, void (*propfn)(const prop_info* pi, void* cookie), 162 void* cookie); 163 164 // The original design doesn't include pa_size or pa_data_size in the prop_area struct itself. 165 // Since we'll need to be backwards compatible with that design, we don't gain much by adding it 166 // now, especially since we don't have any plans to make different property areas different sizes, 167 // and thus we share these two variables among all instances. 168 static size_t pa_size_; 169 static size_t pa_data_size_; 170 171 uint32_t bytes_used_; 172 atomic_uint_least32_t serial_; 173 uint32_t magic_; 174 uint32_t version_; 175 uint32_t reserved_[28]; 176 char data_[0]; 177 178 BIONIC_DISALLOW_COPY_AND_ASSIGN(prop_area); 179 }; 180