ANDROID: sdcardfs: switch to full_name_hash and qstr

Use the kernel's string hash function instead of rolling
our own. Additionally, save a bit of calculation by using
the qstr struct in place of strings.

Change-Id: I0bbeb5ec2a9233f40135ad632e6f22c30ffa95c1
Signed-off-by: Daniel Rosenberg <drosen@google.com>

diff --git a/fs/sdcardfs/packagelist.c b/fs/sdcardfs/packagelist.c
index cdab1967317b4bcd608b8c62a653e27fa61ea73c..b02feef08d51f89e31d61a8d98ed7c0ea7296330 100644 (file)
--- a/fs/sdcardfs/packagelist.c
+++ b/fs/sdcardfs/packagelist.c
@@ -22,7 +22,7 @@
 #include <linux/hashtable.h>
 #include <linux/delay.h>
 #include <linux/radix-tree.h>
-
+#include <linux/dcache.h>
 
 #include <linux/init.h>
 #include <linux/module.h>
@@ -33,7 +33,7 @@
 struct hashtable_entry {
        struct hlist_node hlist;
        struct hlist_node dlist; /* for deletion cleanup */
-       const char *key;
+       struct qstr key;
        atomic_t value;
 };
 
@@ -44,27 +44,28 @@ static DEFINE_HASHTABLE(ext_to_groupid, 8);
 
 static struct kmem_cache *hashtable_entry_cachep;
 
-static unsigned int str_hash(const char *key) {
-       int i;
-       unsigned int h = strlen(key);
-       char *data = (char *)key;
+static void inline qstr_init(struct qstr *q, const char *name) {
+       q->name = name;
+       q->len = strlen(q->name);
+       q->hash = full_name_hash(q->name, q->len);
+}
 
-       for (i = 0; i < strlen(key); i++) {
-               h = h * 31 + *data;
-               data++;
-       }
-       return h;
+static inline int qstr_copy(const struct qstr *src, struct qstr *dest) {
+       dest->name = kstrdup(src->name, GFP_KERNEL);
+       dest->hash_len = src->hash_len;
+       return !!dest->name;
 }
 
-appid_t get_appid(const char *key)
+
+static appid_t __get_appid(const struct qstr *key)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
        appid_t ret_id;
 
        rcu_read_lock();
        hash_for_each_possible_rcu(package_to_appid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key)) {
+               if (!strcasecmp(key->name, hash_cur->key.name)) {
                        ret_id = atomic_read(&hash_cur->value);
                        rcu_read_unlock();
                        return ret_id;
@@ -74,15 +75,22 @@ appid_t get_appid(const char *key)
        return 0;
 }
 
-appid_t get_ext_gid(const char *key)
+appid_t get_appid(const char *key)
+{
+       struct qstr q;
+       qstr_init(&q, key);
+       return __get_appid(&q);
+}
+
+static appid_t __get_ext_gid(const struct qstr *key)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
        appid_t ret_id;
 
        rcu_read_lock();
        hash_for_each_possible_rcu(ext_to_groupid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key)) {
+               if (!strcasecmp(key->name, hash_cur->key.name)) {
                        ret_id = atomic_read(&hash_cur->value);
                        rcu_read_unlock();
                        return ret_id;
@@ -92,14 +100,22 @@ appid_t get_ext_gid(const char *key)
        return 0;
 }
 
-appid_t is_excluded(const char *app_name, userid_t user)
+appid_t get_ext_gid(const char *key)
+{
+       struct qstr q;
+       qstr_init(&q, key);
+       return __get_ext_gid(&q);
+}
+
+static appid_t __is_excluded(const struct qstr *app_name, userid_t user)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(app_name);
+       unsigned int hash = app_name->hash;
 
        rcu_read_lock();
        hash_for_each_possible_rcu(package_to_userid, hash_cur, hlist, hash) {
-               if (atomic_read(&hash_cur->value) == user && !strcasecmp(app_name, hash_cur->key)) {
+               if (atomic_read(&hash_cur->value) == user &&
+                               !strcasecmp(app_name->name, hash_cur->key.name)) {
                        rcu_read_unlock();
                        return 1;
                }
@@ -108,6 +124,14 @@ appid_t is_excluded(const char *app_name, userid_t user)
        return 0;
 }
 
+appid_t is_excluded(const char *app_name, userid_t user)
+{
+       struct qstr q;
+       qstr_init(&q, app_name);
+       return __is_excluded(&q, user);
+}
+
+
 /* Kernel has already enforced everything we returned through
  * derive_permissions_locked(), so this is used to lock down access
  * even further, such as enforcing that apps hold sdcard_rw. */
@@ -145,7 +169,7 @@ int open_flags_to_access_mode(int open_flags) {
        }
 }
 
-static struct hashtable_entry *alloc_hashtable_entry(const char *key,
+static struct hashtable_entry *alloc_hashtable_entry(const struct qstr *key,
                appid_t value)
 {
        struct hashtable_entry *ret = kmem_cache_alloc(hashtable_entry_cachep,
@@ -153,8 +177,7 @@ static struct hashtable_entry *alloc_hashtable_entry(const char *key,
        if (!ret)
                return NULL;
 
-       ret->key = kstrdup(key, GFP_KERNEL);
-       if (!ret->key) {
+       if (!qstr_copy(key, &ret->key)) {
                kmem_cache_free(hashtable_entry_cachep, ret);
                return NULL;
        }
@@ -163,14 +186,14 @@ static struct hashtable_entry *alloc_hashtable_entry(const char *key,
        return ret;
 }
 
-static int insert_packagelist_appid_entry_locked(const char *key, appid_t value)
+static int insert_packagelist_appid_entry_locked(const struct qstr *key, appid_t value)
 {
        struct hashtable_entry *hash_cur;
        struct hashtable_entry *new_entry;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
 
        hash_for_each_possible_rcu(package_to_appid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key)) {
+               if (!strcasecmp(key->name, hash_cur->key.name)) {
                        atomic_set(&hash_cur->value, value);
                        return 0;
                }
@@ -182,15 +205,15 @@ static int insert_packagelist_appid_entry_locked(const char *key, appid_t value)
        return 0;
 }
 
-static int insert_ext_gid_entry_locked(const char *key, appid_t value)
+static int insert_ext_gid_entry_locked(const struct qstr *key, appid_t value)
 {
        struct hashtable_entry *hash_cur;
        struct hashtable_entry *new_entry;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
 
        /* An extension can only belong to one gid */
        hash_for_each_possible_rcu(ext_to_groupid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key))
+               if (!strcasecmp(key->name, hash_cur->key.name))
                        return -EINVAL;
        }
        new_entry = alloc_hashtable_entry(key, value);
@@ -200,15 +223,16 @@ static int insert_ext_gid_entry_locked(const char *key, appid_t value)
        return 0;
 }
 
-static int insert_userid_exclude_entry_locked(const char *key, userid_t value)
+static int insert_userid_exclude_entry_locked(const struct qstr *key, userid_t value)
 {
        struct hashtable_entry *hash_cur;
        struct hashtable_entry *new_entry;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
 
        /* Only insert if not already present */
        hash_for_each_possible_rcu(package_to_userid, hash_cur, hlist, hash) {
-               if (atomic_read(&hash_cur->value) == value && !strcasecmp(key, hash_cur->key))
+               if (atomic_read(&hash_cur->value) == value &&
+                               !strcasecmp(key->name, hash_cur->key.name))
                        return 0;
        }
        new_entry = alloc_hashtable_entry(key, value);
@@ -218,13 +242,13 @@ static int insert_userid_exclude_entry_locked(const char *key, userid_t value)
        return 0;
 }
 
-static void fixup_all_perms_name(const char *key)
+static void fixup_all_perms_name(const struct qstr *key)
 {
        struct sdcardfs_sb_info *sbinfo;
        struct limit_search limit = {
                .flags = BY_NAME,
-               .name = key,
-               .length = strlen(key),
+               .name = key->name,
+               .length = key->len,
        };
        list_for_each_entry(sbinfo, &sdcardfs_super_list, list) {
                if (sbinfo_has_sdcard_magic(sbinfo))
@@ -232,13 +256,13 @@ static void fixup_all_perms_name(const char *key)
        }
 }
 
-static void fixup_all_perms_name_userid(const char *key, userid_t userid)
+static void fixup_all_perms_name_userid(const struct qstr *key, userid_t userid)
 {
        struct sdcardfs_sb_info *sbinfo;
        struct limit_search limit = {
                .flags = BY_NAME | BY_USERID,
-               .name = key,
-               .length = strlen(key),
+               .name = key->name,
+               .length = key->len,
                .userid = userid,
        };
        list_for_each_entry(sbinfo, &sdcardfs_super_list, list) {
@@ -260,7 +284,7 @@ static void fixup_all_perms_userid(userid_t userid)
        }
 }
 
-static int insert_packagelist_entry(const char *key, appid_t value)
+static int insert_packagelist_entry(const struct qstr *key, appid_t value)
 {
        int err;
 
@@ -273,7 +297,7 @@ static int insert_packagelist_entry(const char *key, appid_t value)
        return err;
 }
 
-static int insert_ext_gid_entry(const char *key, appid_t value)
+static int insert_ext_gid_entry(const struct qstr *key, appid_t value)
 {
        int err;
 
@@ -284,7 +308,7 @@ static int insert_ext_gid_entry(const char *key, appid_t value)
        return err;
 }
 
-static int insert_userid_exclude_entry(const char *key, userid_t value)
+static int insert_userid_exclude_entry(const struct qstr *key, userid_t value)
 {
        int err;
 
@@ -299,26 +323,26 @@ static int insert_userid_exclude_entry(const char *key, userid_t value)
 
 static void free_hashtable_entry(struct hashtable_entry *entry)
 {
-       kfree(entry->key);
+       kfree(entry->key.name);
        hash_del_rcu(&entry->dlist);
        kmem_cache_free(hashtable_entry_cachep, entry);
 }
 
-static void remove_packagelist_entry_locked(const char *key)
+static void remove_packagelist_entry_locked(const struct qstr *key)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
        struct hlist_node *h_t;
        HLIST_HEAD(free_list);
 
        hash_for_each_possible_rcu(package_to_userid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key)) {
+               if (!strcasecmp(key->name, hash_cur->key.name)) {
                        hash_del_rcu(&hash_cur->hlist);
                        hlist_add_head(&hash_cur->dlist, &free_list);
                }
        }
        hash_for_each_possible_rcu(package_to_appid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key)) {
+               if (!strcasecmp(key->name, hash_cur->key.name)) {
                        hash_del_rcu(&hash_cur->hlist);
                        hlist_add_head(&hash_cur->dlist, &free_list);
                        break;
@@ -329,7 +353,7 @@ static void remove_packagelist_entry_locked(const char *key)
                free_hashtable_entry(hash_cur);
 }
 
-static void remove_packagelist_entry(const char *key)
+static void remove_packagelist_entry(const struct qstr *key)
 {
        mutex_lock(&sdcardfs_super_list_lock);
        remove_packagelist_entry_locked(key);
@@ -338,13 +362,13 @@ static void remove_packagelist_entry(const char *key)
        return;
 }
 
-static void remove_ext_gid_entry_locked(const char *key, gid_t group)
+static void remove_ext_gid_entry_locked(const struct qstr *key, gid_t group)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
 
        hash_for_each_possible_rcu(ext_to_groupid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key) && atomic_read(&hash_cur->value) == group) {
+               if (!strcasecmp(key->name, hash_cur->key.name) && atomic_read(&hash_cur->value) == group) {
                        hash_del_rcu(&hash_cur->hlist);
                        synchronize_rcu();
                        free_hashtable_entry(hash_cur);
@@ -353,7 +377,7 @@ static void remove_ext_gid_entry_locked(const char *key, gid_t group)
        }
 }
 
-static void remove_ext_gid_entry(const char *key, gid_t group)
+static void remove_ext_gid_entry(const struct qstr *key, gid_t group)
 {
        mutex_lock(&sdcardfs_super_list_lock);
        remove_ext_gid_entry_locked(key, group);
@@ -389,13 +413,14 @@ static void remove_userid_all_entry(userid_t userid)
        return;
 }
 
-static void remove_userid_exclude_entry_locked(const char *key, userid_t userid)
+static void remove_userid_exclude_entry_locked(const struct qstr *key, userid_t userid)
 {
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(key);
+       unsigned int hash = key->hash;
 
        hash_for_each_possible_rcu(package_to_userid, hash_cur, hlist, hash) {
-               if (!strcasecmp(key, hash_cur->key) && atomic_read(&hash_cur->value) == userid) {
+               if (!strcasecmp(key->name, hash_cur->key.name) &&
+                               atomic_read(&hash_cur->value) == userid) {
                        hash_del_rcu(&hash_cur->hlist);
                        synchronize_rcu();
                        free_hashtable_entry(hash_cur);
@@ -404,7 +429,7 @@ static void remove_userid_exclude_entry_locked(const char *key, userid_t userid)
        }
 }
 
-static void remove_userid_exclude_entry(const char *key, userid_t userid)
+static void remove_userid_exclude_entry(const struct qstr *key, userid_t userid)
 {
        mutex_lock(&sdcardfs_super_list_lock);
        remove_userid_exclude_entry_locked(key, userid);
@@ -462,7 +487,7 @@ static struct configfs_attribute _pfx##attr_##_name = {     \
 
 struct package_details {
        struct config_item item;
-       const char *name;
+       struct qstr name;
 };
 
 static inline struct package_details *to_package_details(struct config_item *item)
@@ -472,7 +497,7 @@ static inline struct package_details *to_package_details(struct config_item *ite
 
 static ssize_t package_details_appid_show(struct config_item *item, char *page)
 {
-       return scnprintf(page, PAGE_SIZE, "%u\n", get_appid(to_package_details(item)->name));
+       return scnprintf(page, PAGE_SIZE, "%u\n", __get_appid(&to_package_details(item)->name));
 }
 
 static ssize_t package_details_appid_store(struct config_item *item,
@@ -485,7 +510,7 @@ static ssize_t package_details_appid_store(struct config_item *item,
        if (ret)
                return ret;
 
-       ret = insert_packagelist_entry(to_package_details(item)->name, tmp);
+       ret = insert_packagelist_entry(&to_package_details(item)->name, tmp);
 
        if (ret)
                return ret;
@@ -498,12 +523,12 @@ static ssize_t package_details_excluded_userids_show(struct config_item *item,
 {
        struct package_details *package_details = to_package_details(item);
        struct hashtable_entry *hash_cur;
-       unsigned int hash = str_hash(package_details->name);
+       unsigned int hash = package_details->name.hash;
        int count = 0;
 
        rcu_read_lock();
        hash_for_each_possible_rcu(package_to_userid, hash_cur, hlist, hash) {
-               if (!strcasecmp(package_details->name, hash_cur->key))
+               if (!strcasecmp(package_details->name.name, hash_cur->key.name))
                        count += scnprintf(page + count, PAGE_SIZE - count,
                                        "%d ", atomic_read(&hash_cur->value));
        }
@@ -524,7 +549,7 @@ static ssize_t package_details_excluded_userids_store(struct config_item *item,
        if (ret)
                return ret;
 
-       ret = insert_userid_exclude_entry(to_package_details(item)->name, tmp);
+       ret = insert_userid_exclude_entry(&to_package_details(item)->name, tmp);
 
        if (ret)
                return ret;
@@ -541,16 +566,16 @@ static ssize_t package_details_clear_userid_store(struct config_item *item,
        ret = kstrtouint(page, 10, &tmp);
        if (ret)
                return ret;
-       remove_userid_exclude_entry(to_package_details(item)->name, tmp);
+       remove_userid_exclude_entry(&to_package_details(item)->name, tmp);
        return count;
 }
 
 static void package_details_release(struct config_item *item)
 {
        struct package_details *package_details = to_package_details(item);
-       printk(KERN_INFO "sdcardfs: removing %s\n", package_details->name);
-       remove_packagelist_entry(package_details->name);
-       kfree(package_details->name);
+       printk(KERN_INFO "sdcardfs: removing %s\n", package_details->name.name);
+       remove_packagelist_entry(&package_details->name);
+       kfree(package_details->name.name);
        kfree(package_details);
 }
 
@@ -582,7 +607,7 @@ struct extensions_value {
 
 struct extension_details {
        struct config_item item;
-       const char* name;
+       struct qstr name;
        unsigned int num;
 };
 
@@ -601,9 +626,9 @@ static void extension_details_release(struct config_item *item)
        struct extension_details *extension_details = to_extension_details(item);
 
        printk(KERN_INFO "sdcardfs: No longer mapping %s files to gid %d\n",
-                       extension_details->name, extension_details->num);
-       remove_ext_gid_entry(extension_details->name, extension_details->num);
-       kfree(extension_details->name);
+                       extension_details->name.name, extension_details->num);
+       remove_ext_gid_entry(&extension_details->name, extension_details->num);
+       kfree(extension_details->name.name);
        kfree(extension_details);
 }
 
@@ -620,20 +645,21 @@ static struct config_item *extension_details_make_item(struct config_group *grou
 {
        struct extensions_value *extensions_value = to_extensions_value(&group->cg_item);
        struct extension_details *extension_details = kzalloc(sizeof(struct extension_details), GFP_KERNEL);
+       const char *tmp;
        int ret;
        if (!extension_details)
                return ERR_PTR(-ENOMEM);
 
-       extension_details->name = kstrdup(name, GFP_KERNEL);
-       if (!extension_details->name) {
+       tmp = kstrdup(name, GFP_KERNEL);
+       if (!tmp) {
                kfree(extension_details);
                return ERR_PTR(-ENOMEM);
        }
-       extension_details->num = extensions_value->num;
-       ret = insert_ext_gid_entry(name, extensions_value->num);
+       qstr_init(&extension_details->name, tmp);
+       ret = insert_ext_gid_entry(&extension_details->name, extensions_value->num);
 
        if (ret) {
-               kfree(extension_details->name);
+               kfree(extension_details->name.name);
                kfree(extension_details);
                return ERR_PTR(ret);
        }
@@ -699,16 +725,17 @@ struct config_group extension_group = {
 static struct config_item *packages_make_item(struct config_group *group, const char *name)
 {
        struct package_details *package_details;
+       const char *tmp;
 
        package_details = kzalloc(sizeof(struct package_details), GFP_KERNEL);
        if (!package_details)
                return ERR_PTR(-ENOMEM);
-       package_details->name = kstrdup(name, GFP_KERNEL);
-       if (!package_details->name) {
+       tmp = kstrdup(name, GFP_KERNEL);
+       if (!tmp) {
                kfree(package_details);
                return ERR_PTR(-ENOMEM);
        }
-
+       qstr_init(&package_details->name, tmp);
        config_item_init_type_name(&package_details->item, name,
                                                &package_appid_type);
 
@@ -727,13 +754,13 @@ static ssize_t packages_list_show(struct config_item *item, char *page)
        rcu_read_lock();
        hash_for_each_rcu(package_to_appid, i, hash_cur_app, hlist) {
                written = scnprintf(page + count, PAGE_SIZE - sizeof(errormsg) - count, "%s %d\n",
-                                       hash_cur_app->key, atomic_read(&hash_cur_app->value));
-               hash = str_hash(hash_cur_app->key);
+                                       hash_cur_app->key.name, atomic_read(&hash_cur_app->value));
+               hash = hash_cur_app->key.hash;
                hash_for_each_possible_rcu(package_to_userid, hash_cur_user, hlist, hash) {
-                       if (!strcasecmp(hash_cur_app->key, hash_cur_user->key)) {
+                       if (!strcasecmp(hash_cur_app->key.name, hash_cur_user->key.name)) {
                                written += scnprintf(page + count + written - 1,
                                        PAGE_SIZE - sizeof(errormsg) - count - written + 1,
-                                       " %d\n",        atomic_read(&hash_cur_user->value)) - 1;
+                                       " %d\n", atomic_read(&hash_cur_user->value)) - 1;
                        }
                }
                if (count + written == PAGE_SIZE - sizeof(errormsg) - 1) {