From 996cdc4b1a7fcae89650bee0a44b6cb7900a4a3c Mon Sep 17 00:00:00 2001 From: Greg Hackmann Date: Thu, 20 Jun 2013 11:27:56 -0700 Subject: [PATCH] bionic: reimplement property area as hybrid trie/binary tree See the comments for an explanation of how properties are stored. The trie structure is designed to scale better than the previous array-based implementation. Searching an array with n properties required average O(n) string compares of the entire key; searching the trie requires average O(log n) string compares of each token (substrings between '.' characters). Signed-off-by: Greg Hackmann (cherry picked from commit 6ac8e6a46d71a51bec16938efa89f275fa89cf7d) Change-Id: Icbe31908572f33b4d9b85d5b62ac837cbd0f85e0 --- libc/bionic/system_properties.c | 353 ++++++++++++++++++++++++++-------- libc/include/sys/_system_properties.h | 12 +- 2 files changed, 272 insertions(+), 93 deletions(-) diff --git a/libc/bionic/system_properties.c b/libc/bionic/system_properties.c index b12879e47..126fea56a 100644 --- a/libc/bionic/system_properties.c +++ b/libc/bionic/system_properties.c @@ -34,6 +34,7 @@ #include #include #include +#include #include @@ -51,12 +52,15 @@ #include #include +#define ALIGN(x, a) (((x) + (a - 1)) & ~(a - 1)) + struct prop_area { - unsigned volatile count; + unsigned bytes_used; unsigned volatile serial; unsigned magic; unsigned version; - unsigned toc[1]; + unsigned reserved[28]; + char data[0]; }; typedef struct prop_area prop_area; @@ -69,11 +73,46 @@ struct prop_info { typedef struct prop_info prop_info; +/* + * Properties are stored in a hybrid trie/binary tree structure. + * Each property's name is delimited at '.' characters, and the tokens are put + * into a trie structure. Siblings at each level of the trie are stored in a + * binary tree. For instance, "ro.secure"="1" could be stored as follows: + * + * +-----+ children +----+ children +--------+ + * | |-------------->| ro |-------------->| secure | + * +-----+ +----+ +--------+ + * / \ / | + * left / \ right left / | prop +===========+ + * v v v +-------->| ro.secure | + * +-----+ +-----+ +-----+ +-----------+ + * | net | | sys | | com | | 1 | + * +-----+ +-----+ +-----+ +===========+ + */ + +typedef volatile uint32_t prop_off_t; +struct prop_bt { + char name[PROP_NAME_MAX]; + uint8_t namelen; + uint8_t reserved[3]; + + prop_off_t prop; + + prop_off_t left; + prop_off_t right; + + prop_off_t children; +}; + +typedef struct prop_bt prop_bt; + static const char property_service_socket[] = "/dev/socket/" PROP_SERVICE_NAME; static char property_filename[PATH_MAX] = PROP_FILENAME; prop_area *__system_property_regions__[PA_REGION_COUNT] = { NULL, }; +const size_t PA_DATA_SIZE = PA_SIZE - sizeof(prop_area); + static int get_fd_from_env(void) { char *env = getenv("ANDROID_PROPERTY_WORKSPACE"); @@ -120,6 +159,11 @@ static int map_prop_region_rw(size_t region) pa->magic = PROP_AREA_MAGIC; pa->version = PROP_AREA_VERSION; + if (!region) { + /* reserve root node */ + pa->bytes_used += sizeof(prop_bt); + } + /* plug into the lib property services */ __system_property_regions__[region] = pa; @@ -225,83 +269,183 @@ int __system_properties_init() return map_prop_region(0); } -int __system_property_foreach( - void (*propfn)(const prop_info *pi, void *cookie), - void *cookie) +static void *new_prop_obj(size_t size, prop_off_t *off) { - size_t region; + prop_area *pa; + size_t i, idx; + size = ALIGN(size, sizeof(uint32_t)); - for (region = 0; region < PA_REGION_COUNT; region++) { - prop_area *pa; - unsigned i; + for (i = 0; i < PA_REGION_COUNT; i++) { + int err = map_prop_region_rw(i); + if (err < 0) { + return NULL; + } - int err = map_prop_region(region); - if (err < 0) + pa = __system_property_regions__[i]; + if (pa->bytes_used + size <= PA_DATA_SIZE) break; - pa = __system_property_regions__[region]; + } - for (i = 0; i < pa->count; i++) { - unsigned entry = pa->toc[i]; - prop_info *pi = TOC_TO_INFO(pa, entry); - propfn(pi, cookie); - } + if (i == PA_REGION_COUNT) + return NULL; + + idx = pa->bytes_used; + *off = idx + i * PA_DATA_SIZE; + pa->bytes_used += size; + return pa->data + idx; +} + +static prop_bt *new_prop_bt(const char *name, uint8_t namelen, prop_off_t *off) +{ + prop_off_t off_tmp; + prop_bt *bt = new_prop_obj(sizeof(prop_bt), &off_tmp); + if (bt) { + memcpy(bt->name, name, namelen); + bt->name[namelen] = '\0'; + bt->namelen = namelen; + ANDROID_MEMBAR_FULL(); + *off = off_tmp; } - return 0; + return bt; } -const prop_info *__system_property_find_nth(unsigned n) +static prop_info *new_prop_info(const char *name, uint8_t namelen, + const char *value, uint8_t valuelen, prop_off_t *off) { - size_t region = n / PA_COUNT_MAX; - prop_area *pa; + prop_off_t off_tmp; + prop_info *info = new_prop_obj(sizeof(prop_info), &off_tmp); + if (info) { + memcpy(info->name, name, namelen); + info->name[namelen] = '\0'; + info->serial = (valuelen << 24); + memcpy(info->value, value, valuelen); + info->value[valuelen] = '\0'; + ANDROID_MEMBAR_FULL(); + *off = off_tmp; + } - int err = map_prop_region(region); - if (err < 0) + return info; +} + +static void *to_prop_obj(prop_off_t off) +{ + size_t region = off / PA_DATA_SIZE; + size_t idx = off % PA_DATA_SIZE; + + if (region > PA_REGION_COUNT) return NULL; - pa = __system_property_regions__[region]; - if((n % PA_COUNT_MAX) >= pa->count) { - return 0; - } else { - return TOC_TO_INFO(pa, pa->toc[n]); - } + if (map_prop_region(region) < 0) + return NULL; + + return __system_property_regions__[region]->data + idx; } -const prop_info *__system_property_find(const char *name) +static prop_bt *root_node() { - unsigned len = strlen(name); - size_t region; + return to_prop_obj(0); +} - if (len >= PROP_NAME_MAX) - return 0; - if (len < 1) - return 0; +static int cmp_prop_name(const char *one, uint8_t one_len, const char *two, + uint8_t two_len) +{ + if (one_len < two_len) + return -1; + else if (one_len > two_len) + return 1; + else + return strncmp(one, two, one_len); +} - for (region = 0; region < PA_REGION_COUNT; region++) { - prop_area *pa; - unsigned count; - unsigned *toc; - prop_info *pi; +static prop_bt *find_prop_bt(prop_bt *bt, const char *name, uint8_t namelen, + bool alloc_if_needed) +{ + while (true) { + int ret; + if (!bt) + return bt; + ret = cmp_prop_name(name, namelen, bt->name, bt->namelen); + + if (ret == 0) { + return bt; + } else if (ret < 0) { + if (bt->left) { + bt = to_prop_obj(bt->left); + } else { + if (!alloc_if_needed) + return NULL; + + bt = new_prop_bt(name, namelen, &bt->left); + } + } else { + if (bt->right) { + bt = to_prop_obj(bt->right); + } else { + if (!alloc_if_needed) + return NULL; - int err = map_prop_region(region); - if (err < 0) - return 0; - pa = __system_property_regions__[region]; - count = pa->count; - toc = pa->toc; + bt = new_prop_bt(name, namelen, &bt->right); + } + } + } +} - while(count--) { - unsigned entry = *toc++; - if(TOC_NAME_LEN(entry) != len) continue; +static const prop_info *find_property(prop_bt *trie, const char *name, + uint8_t namelen, const char *value, uint8_t valuelen, + bool alloc_if_needed) +{ + const char *remaining_name = name; + + while (true) { + char *sep = strchr(remaining_name, '.'); + bool want_subtree = (sep != NULL); + uint8_t substr_size; + + prop_bt *root; + + if (want_subtree) { + substr_size = sep - remaining_name; + } else { + substr_size = strlen(remaining_name); + } - pi = TOC_TO_INFO(pa, entry); - if(memcmp(name, pi->name, len)) continue; + if (!substr_size) + return NULL; - return pi; + if (trie->children) { + root = to_prop_obj(trie->children); + } else if (alloc_if_needed) { + root = new_prop_bt(remaining_name, substr_size, &trie->children); + } else { + root = NULL; } + + if (!root) + return NULL; + + trie = find_prop_bt(root, remaining_name, substr_size, alloc_if_needed); + if (!trie) + return NULL; + + if (!want_subtree) + break; + + remaining_name = sep + 1; } - return 0; + if (trie->prop) { + return to_prop_obj(trie->prop); + } else if (alloc_if_needed) { + return new_prop_info(name, namelen, value, valuelen, &trie->prop); + } else { + return NULL; + } +} + +const prop_info *__system_property_find(const char *name) +{ + return find_property(root_node(), name, strlen(name), NULL, 0, false); } int __system_property_read(const prop_info *pi, char *name, char *value) @@ -463,10 +607,8 @@ int __system_property_update(prop_info *pi, const char *value, unsigned int len) int __system_property_add(const char *name, unsigned int namelen, const char *value, unsigned int valuelen) { - prop_area *pa; - prop_info *pa_info_array; - prop_info *pi; - size_t region; + prop_area *pa = __system_property_regions__[0]; + const prop_info *pi; if (namelen >= PROP_NAME_MAX) return -1; @@ -475,34 +617,12 @@ int __system_property_add(const char *name, unsigned int namelen, if (namelen < 1) return -1; - for (region = 0; region < PA_REGION_COUNT; region++) - { - int err = map_prop_region_rw(region); - if (err < 0) - return -1; - - pa = __system_property_regions__[region]; - - if (pa->count < PA_COUNT_MAX) - break; - } - - if (region == PA_REGION_COUNT) + pi = find_property(root_node(), name, namelen, value, valuelen, true); + if (!pi) return -1; - pa_info_array = (void*) (((char*) pa) + PA_INFO_START); - pi = pa_info_array + pa->count; - pi->serial = (valuelen << 24); - memcpy(pi->name, name, namelen + 1); - memcpy(pi->value, value, valuelen + 1); - - pa->toc[pa->count] = (namelen << 24) | (((unsigned) pi) - ((unsigned) pa)); - ANDROID_MEMBAR_FULL(); - - pa->count++; pa->serial++; __futex_wake(&pa->serial, INT32_MAX); - return 0; } @@ -521,3 +641,72 @@ unsigned int __system_property_wait_any(unsigned int serial) return pa->serial; } + +struct find_nth_cookie { + unsigned count; + unsigned n; + const prop_info *pi; +}; + +static void find_nth_fn(const prop_info *pi, void *ptr) +{ + struct find_nth_cookie *cookie = ptr; + + if (cookie->n == cookie->count) + cookie->pi = pi; + + cookie->count++; +} + +const prop_info *__system_property_find_nth(unsigned n) +{ + struct find_nth_cookie cookie; + int err; + + memset(&cookie, 0, sizeof(cookie)); + cookie.n = n; + + err = __system_property_foreach(find_nth_fn, &cookie); + if (err < 0) + return NULL; + + return cookie.pi; +} + +static int foreach_property(prop_off_t off, + void (*propfn)(const prop_info *pi, void *cookie), void *cookie) +{ + prop_bt *trie = to_prop_obj(off); + if (!trie) + return -1; + + if (trie->left) { + int err = foreach_property(trie->left, propfn, cookie); + if (err < 0) + return -1; + } + if (trie->prop) { + prop_info *info = to_prop_obj(trie->prop); + if (!info) + return -1; + propfn(info, cookie); + } + if (trie->children) { + int err = foreach_property(trie->children, propfn, cookie); + if (err < 0) + return -1; + } + if (trie->right) { + int err = foreach_property(trie->right, propfn, cookie); + if (err < 0) + return -1; + } + + return 0; +} + +int __system_property_foreach(void (*propfn)(const prop_info *pi, void *cookie), + void *cookie) +{ + return foreach_property(0, propfn, cookie); +} diff --git a/libc/include/sys/_system_properties.h b/libc/include/sys/_system_properties.h index 4971a4c12..9c48e1b3e 100644 --- a/libc/include/sys/_system_properties.h +++ b/libc/include/sys/_system_properties.h @@ -37,7 +37,7 @@ typedef struct prop_msg prop_msg; #define PROP_AREA_MAGIC 0x504f5250 -#define PROP_AREA_VERSION 0x45434f76 +#define PROP_AREA_VERSION 0xfc6ed0ab #define PROP_SERVICE_NAME "property_service" #define PROP_FILENAME "/dev/__properties__" @@ -45,14 +45,9 @@ typedef struct prop_msg prop_msg; /* (4 header words + 28 toc words) = 128 bytes */ /* 128 bytes header and toc + 28 prop_infos @ 128 bytes = 3712 bytes */ -#define PA_COUNT_MAX 28 #define PA_REGION_COUNT 128 -#define PA_INFO_START 128 #define PA_SIZE 4096 -#define TOC_NAME_LEN(toc) ((toc) >> 24) -#define TOC_TO_INFO(area, toc) ((prop_info*) (((char*) area) + ((toc) & 0xFFFFFF))) - #define SERIAL_VALUE_LEN(serial) ((serial) >> 24) #define SERIAL_DIRTY(serial) ((serial) & 1) @@ -84,11 +79,6 @@ struct prop_msg ** 1. pi->serial = pi->serial | 1 ** 2. memcpy(pi->value, local_value, value_len) ** 3. pi->serial = (value_len << 24) | ((pi->serial + 1) & 0xffffff) -** -** Improvements: -** - maintain the toc sorted by pi->name to allow lookup -** by binary search -** */ #define PROP_PATH_RAMDISK_DEFAULT "/default.prop" -- 2.11.0