From 59ec621a0bf1b94c3fced06cac0a64d707118b43 Mon Sep 17 00:00:00 2001 From: Eric Herman Date: Mon, 22 Jan 2018 15:46:37 +0100 Subject: [PATCH] Mirror acl_users Array with Map MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The acl_users Prealloced_array is used widely, this commit does not replace it, rather this commit creates a table of usernames to lists of matching ACL_USER objects so that the find_mpvio_user and find_acl_user functions can return more quickly when there are many tens of thousands of users. To test the setup, a script was created which creates many users: https://github.com/ericherman/code-snips/blob/master/shell/create-many-mysql-users For this testing, 32768 user names were created, each user has six hosts. While there is a small amount of jitter, the following was typical for the "before" case: $ time { for i in {0..10000}; do \ /home/eric/builds/mysql-8.0/bin/mysql --port=13306 \ --ssl-mode=DISABLED --host=127.0.0.1 --user=user0032768 -pnone \ -e "SELECT 1;" >/dev/null 2>&1 || echo "DARN $?"; done; } real 0m40.236s user 0m25.599s sys 0m6.986s With the patch, the following was typical of the "after" case: $ time { for i in {0..10000}; do \ /home/eric/builds/mysql-8.0/bin/mysql --port=23306 \ --ssl-mode=DISABLED --host=127.0.0.1 --user=user0032768 -pnone \ -e "SELECT 1;" >/dev/null 2>&1 || echo "DARN $?"; done; } real 0m33.984s user 0m22.060s sys 0m9.205s Examining with "perf" shows us where time is spent originally: perf record -F 20000 -a \ -p $(cat /data/mysql-8.0-data/mysqld.pid) & sleep 0.3; \ /home/eric/builds/mysql-8.0/bin/mysql --user=root \ --host=127.0.0.1 --port=13306 --ssl-mode=DISABLED <<<"SELECT 1"; \ killall perf; perf report -i ./perf.data # Overhead Command Shared Object Symbol 44.63% mysqld libc-2.26.so [.] __strcmp_sse2_unaligned 3.48% mysqld mysqld [.] setup_fields 2.05% mysqld mysqld [.] vio_io_wait 1.90% mysqld [vdso] [.] 0x0000000000000c1e 1.88% mysqld mysqld [.] find_mpvio_user 1.87% mysqld libc-2.26.so [.] __tzstring 1.85% mysqld mysqld [.] alloc_and_copy_thd_dynamic_variables 1.82% mysqld mysqld [.] pfs_get_thread_statement_locker_v1 1.79% mysqld mysqld [.] dd::cache::Object_registry::Object_registry 1.79% mysqld mysqld [.] Protocol_classic::parse_packet 1.77% mysqld mysqld [.] thd_increment_bytes_received 1.77% mysqld mysqld [.] TaoCrypt::SHA256::Transform 1.72% mysqld mysqld [.] Item_int::init 1.71% mysqld mysqld [.] dispatch_command With the change we see different results: perf record -F 20000 -a \ -p $(cat /data/mysql-8.0-acl_user-data/mysqld.pid) & sleep 0.3; \ /home/eric/builds/mysql-8.0/bin/mysql --user=root \ --host=127.0.0.1 --port=23306 --ssl-mode=DISABLED <<<"SELECT 1"; \ killall perf; perf report -i ./perf.data # Overhead Command Shared Object Symbol 9.91% mysqld libc-2.26.so [.] _int_malloc 7.19% mysqld mysqld [.] thd_increment_bytes_received 7.13% mysqld mysqld [.] net_write_command 6.93% mysqld mysqld [.] get_thread_attributes 6.73% mysqld mysqld [.] Protocol_classic::net_store_data 6.68% mysqld mysqld [.] Item::charset_for_protocol 6.57% mysqld mysqld [.] pfs_unlock_rwlock_v1 6.37% mysqld mysqld [.] plugin_foreach_with_mask 6.34% mysqld mysqld [.] MYSQLparse 6.34% mysqld mysqld [.] lex_start 6.32% mysqld mysqld [.] TaoCrypt::Transform256 6.10% mysqld mysqld [.] pfs_memory_free_v1 5.58% mysqld mysqld [.] my_hash_sort_uca_900_tmpl 4.53% mysqld mysqld [.] THD::THD From the differences in perf output, we see that the changed code is no longer spending an over-whelming amount of its time comparing strings or in find_mpvio_user. I would like to thank Mattias Jonsson, as he was a great help in this work: in an earlier version, he figured out my bug where the map would have no-longer-valid pointers (because of the sorting of acl_users). Also, he found my NULL vs. empty-string bug. I would like to thank Gonzalo Diethelm for being willing and able to act as a sounding board during my discussions, and helping me write more idiomatic C++ code and giving me some good debugging ideas. I would like to thank Dmitry Lenev for helping me think-through the ACL_compare logic, Philippe Bruhat for patiently debugging with me, Kendrick Shaw for helping me with allocators, and Daniël van Eeden for pointing out the issue in the first place and encouraging me to hack on it. --- sql/auth/sql_auth_cache.cc | 152 ++++++++++++++++++++++++++++++++++++----- sql/auth/sql_auth_cache.h | 27 ++++++++ sql/auth/sql_authentication.cc | 7 +- sql/auth/sql_user.cc | 4 ++ 4 files changed, 171 insertions(+), 19 deletions(-) diff --git a/sql/auth/sql_auth_cache.cc b/sql/auth/sql_auth_cache.cc index 0300ee9abce..94efb6ce401 100644 --- a/sql/auth/sql_auth_cache.cc +++ b/sql/auth/sql_auth_cache.cc @@ -85,6 +85,7 @@ #include #include +#include #include #include @@ -139,6 +140,14 @@ malloc_unordered_map> collation_unordered_map *acl_check_hosts= nullptr; +typedef Acl_cache_allocator> + Name_to_userlist_pair_allocator; +typedef std::unordered_map, std::equal_to, + Name_to_userlist_pair_allocator> + Name_to_userlist; +Name_to_userlist *name_to_userlist= nullptr; + bool initialized=0; bool acl_cache_initialized= false; bool allow_all_hosts=1; @@ -928,6 +937,106 @@ bool GRANT_TABLE::init(TABLE *col_privs) return false; } + +namespace { + +class ACL_compare : + public std::binary_function +{ +public: + bool operator()(const ACL_ACCESS &a, const ACL_ACCESS &b) + { + return a.sort > b.sort; + } + bool operator()(const ACL_ACCESS *a, const ACL_ACCESS *b) + { + return a->sort > b->sort; + } +}; + +} // namespace + + +/* + Build the lists of ACL_USERs which share name or have no name +*/ + +void +rebuild_cached_acl_users_for_name(void) +{ + DBUG_ENTER("rebuild_cached_acl_users_for_name"); + DBUG_PRINT("enter", ("acl_users size: %lu", acl_users->size())); + + DBUG_ASSERT(!current_thd || assert_acl_cache_read_lock(current_thd)); + + if (name_to_userlist) { + name_to_userlist->clear(); + } else { + size_t size= sizeof(Name_to_userlist); + myf_t flags= MYF(MY_WME | ME_FATALERROR); + void *bytes= my_malloc(key_memory_acl_cache, size, flags); + name_to_userlist= new(bytes)Name_to_userlist(); + } + + std::list anons; + + /* first build each named list */ + for (ACL_USER *acl_user= acl_users->begin(); + acl_user != acl_users->end(); ++acl_user) + { + std::string name= acl_user->user ? acl_user->user : ""; + (*name_to_userlist)[name].push_back(acl_user); + + /* keep track of anonymous acl_users */ + if (!name.compare("")) + anons.push_back(acl_user); + } + + /* add the anonymous acl_users to each non-anon list */ + for (auto it= name_to_userlist->begin(); it != name_to_userlist->end(); ++it) + { + std::string name= it->first; + if (!name.compare("")) + continue; + + auto *list= &it->second; + for (auto it2= anons.begin(); it2 != anons.end(); ++it2) + { + list->push_back(*it2); + } + + list->sort(ACL_compare()); + } + DBUG_VOID_RETURN; +} + + +/* + Fetch the list of ACL_USERs which share name or have no name +*/ + +Acl_user_ptr_list * +cached_acl_users_for_name(const char *name) +{ + DBUG_ENTER("cached_acl_users_for_name"); + DBUG_PRINT("enter", ("name: '%s'", name)); + + DBUG_ASSERT(!current_thd || assert_acl_cache_read_lock(current_thd)); + + std::string user_name= name ? name : ""; + + auto it= name_to_userlist->find(user_name); + if (it != name_to_userlist->end()) + DBUG_RETURN(&it->second); + + it= name_to_userlist->find(""); + if (it != name_to_userlist->end()) + DBUG_RETURN(&it->second); + + DBUG_RETURN(NULL); +} + + /* Find first entry that matches the current user */ @@ -942,9 +1051,14 @@ find_acl_user(const char *host, const char *user, bool exact) if (likely(acl_users)) { - for (ACL_USER *acl_user= acl_users->begin(); - acl_user != acl_users->end(); ++acl_user) + Acl_user_ptr_list *list= cached_acl_users_for_name(user); + if (!list) { + DBUG_RETURN(0); + } + + for (auto it= list->begin(); it != list->end(); ++it) { + ACL_USER *acl_user= (*it); DBUG_PRINT("info",("strcmp('%s','%s'), compare_hostname('%s','%s'),", user, acl_user->user ? acl_user->user : "", host, @@ -1415,21 +1529,6 @@ bool acl_getroot(THD *thd, Security_context *sctx, char *user, char *host, } -namespace { - -class ACL_compare : - public std::binary_function -{ -public: - bool operator()(const ACL_ACCESS &a, const ACL_ACCESS &b) - { - return a.sort > b.sort; - } -}; - -} // namespace - - /** Convert scrambled password to binary form, according to scramble type, Binary form is stored in user.salt. @@ -1722,6 +1821,8 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) NULL, 1, 1, FALSE)) goto end; table->use_all_columns(); + if (name_to_userlist) + name_to_userlist->clear(); acl_users->clear(); /* We need to check whether we are working with old database layout. This @@ -2129,6 +2230,7 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) } } // END while reading records from the mysql.user table + rebuild_cached_acl_users_for_name(); end_read_record(&read_record_info); if (read_rec_errcode > 0) @@ -2136,6 +2238,7 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) std::sort(acl_users->begin(), acl_users->end(), ACL_compare()); acl_users->shrink_to_fit(); + rebuild_cached_acl_users_for_name(); if (super_users_with_empty_plugin) { @@ -2272,9 +2375,21 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) +void free_name_to_userlist() +{ + if (!name_to_userlist) + return; + + name_to_userlist->~unordered_map(); + my_free(name_to_userlist); + name_to_userlist= nullptr; +} + + void acl_free(bool end) { free_root(&global_acl_memory,MYF(0)); + free_name_to_userlist(); delete acl_users; acl_users= NULL; delete acl_dbs; @@ -2520,6 +2635,7 @@ bool acl_reload(THD *thd) delete old_acl_proxy_users; delete old_dyn_priv_map; } + rebuild_cached_acl_users_for_name(); end: commit_and_close_mysql_tables(thd); @@ -3129,6 +3245,7 @@ void acl_update_user(const char *user, const char *host, } } } + rebuild_cached_acl_users_for_name(); DBUG_VOID_RETURN; } @@ -3217,6 +3334,7 @@ void acl_insert_user(THD *thd, const char *user, const char *host, if (acl_user.host.check_allow_all_hosts()) allow_all_hosts=1; // Anyone can connect /* purecov: tested */ std::sort(acl_users->begin(), acl_users->end(), ACL_compare()); + rebuild_cached_acl_users_for_name(); /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */ rebuild_check_host(); diff --git a/sql/auth/sql_auth_cache.h b/sql/auth/sql_auth_cache.h index dbf0ab7cf94..e196eb71810 100644 --- a/sql/auth/sql_auth_cache.h +++ b/sql/auth/sql_auth_cache.h @@ -322,6 +322,33 @@ class GRANT_TABLE :public GRANT_NAME bool ok() { return privs != 0 || cols != 0; } }; +/* + * A default/no-arg constructor is useful with containers-of-containers + * situations in which a two-allocator scoped_allocator_adapter is not enough. + * This custom allocator provides a Malloc_allocator with a no-arg constructor + * by hard-coding the key_memory_acl_cache constructor argument. + * This "solution" lacks beauty, yet is pragmatic. + */ +template +class Acl_cache_allocator : public Malloc_allocator { + public: + Acl_cache_allocator() : Malloc_allocator(key_memory_acl_cache) {} + template struct rebind { typedef Acl_cache_allocator other; }; + + template Acl_cache_allocator + (const Acl_cache_allocator &other __attribute__((unused))) + : Malloc_allocator(key_memory_acl_cache) + {} + + template Acl_cache_allocator & operator= + (const Acl_cache_allocator &other __attribute__((unused))) + {} + +}; +typedef Acl_cache_allocator Acl_user_ptr_allocator; +typedef std::list Acl_user_ptr_list; +Acl_user_ptr_list *cached_acl_users_for_name(const char *name); +void rebuild_cached_acl_users_for_name(void); /* Data Structures */ diff --git a/sql/auth/sql_authentication.cc b/sql/auth/sql_authentication.cc index c9dcf279a46..4597b6cb118 100644 --- a/sql/auth/sql_authentication.cc +++ b/sql/auth/sql_authentication.cc @@ -962,9 +962,12 @@ static bool find_mpvio_user(THD *thd, MPVIO_EXT *mpvio) if (!acl_cache_lock.lock(false)) DBUG_RETURN(true); - for (ACL_USER *acl_user_tmp= acl_users->begin(); - acl_user_tmp != acl_users->end(); ++acl_user_tmp) + Acl_user_ptr_list *list; + list= cached_acl_users_for_name(mpvio->auth_info.user_name); + if (list) + for (auto it= list->begin(); it != list->end(); ++it) { + ACL_USER *acl_user_tmp= (*it); if ((!acl_user_tmp->user || !strcmp(mpvio->auth_info.user_name, acl_user_tmp->user)) && acl_user_tmp->host.compare_hostname(mpvio->host, mpvio->ip)) diff --git a/sql/auth/sql_user.cc b/sql/auth/sql_user.cc index e8e9a59433a..6bf9d63e645 100644 --- a/sql/auth/sql_user.cc +++ b/sql/auth/sql_user.cc @@ -1592,6 +1592,7 @@ static int handle_grant_struct(enum enum_acl_lists struct_no, bool drop, if (drop) { acl_users->erase(idx); + rebuild_cached_acl_users_for_name(); /* - If we are iterating through an array then we just have moved all elements after the current element one position closer to its head. @@ -1605,6 +1606,7 @@ static int handle_grant_struct(enum enum_acl_lists struct_no, bool drop, { acl_user->user= strdup_root(&global_acl_memory, user_to->user.str); acl_user->host.update_hostname(strdup_root(&global_acl_memory, user_to->host.str)); + rebuild_cached_acl_users_for_name(); } else { @@ -2273,6 +2275,7 @@ bool mysql_drop_user(THD *thd, List &list, bool if_exists) /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */ rebuild_check_host(); + rebuild_cached_acl_users_for_name(); if (result && !thd->is_error()) { @@ -2449,6 +2452,7 @@ bool mysql_rename_user(THD *thd, List &list) /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */ rebuild_check_host(); + rebuild_cached_acl_users_for_name(); if (result && !thd->is_error()) my_error(ER_CANNOT_USER, MYF(0), "RENAME USER", wrong_users.c_ptr_safe());