From 5c0a1a6cb17f27ff85ba08fe473e313180203a8c 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 | 126 ++++++++++++++++++++++++++++++++++++----- sql/auth/sql_auth_cache.h | 30 ++++++++++ sql/auth/sql_authentication.cc | 16 ++++-- sql/auth/sql_user.cc | 4 ++ 4 files changed, 157 insertions(+), 19 deletions(-) diff --git a/sql/auth/sql_auth_cache.cc b/sql/auth/sql_auth_cache.cc index fd6c157cbca..dd6d247269d 100644 --- a/sql/auth/sql_auth_cache.cc +++ b/sql/auth/sql_auth_cache.cc @@ -85,6 +85,7 @@ #include #include +#include #include #include @@ -140,6 +141,14 @@ malloc_unordered_map> db_cache{ key_memory_acl_cache}; 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; @@ -798,6 +807,88 @@ 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 */ @@ -809,8 +900,13 @@ ACL_USER *find_acl_user(const char *host, const char *user, bool exact) { DBUG_ASSERT(assert_acl_cache_read_lock(current_thd)); 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, @@ -1211,17 +1307,6 @@ bool acl_getroot(THD *thd, Security_context *sctx, char *user, char *host, DBUG_RETURN(res); } -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. @@ -1477,6 +1562,7 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) { 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 @@ -1840,12 +1926,14 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) { allow_all_hosts = 1; // Anyone can connect } } // 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) goto end; 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) { LogErr(WARNING_LEVEL, ER_NO_SUPER_WITHOUT_USER_PLUGIN); @@ -1957,8 +2045,17 @@ static bool acl_load(THD *thd, TABLE_LIST *tables) { DBUG_RETURN(return_val); } +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 /*= false*/) { free_root(&global_acl_memory, MYF(0)); + free_name_to_userlist(); delete acl_users; acl_users = NULL; delete acl_dbs; @@ -2260,6 +2357,7 @@ bool acl_reload(THD *thd, bool locked) { // Delete the old role caches delete_old_role_cache(); } + rebuild_cached_acl_users_for_name(); end: commit_and_close_mysql_tables(thd); @@ -2788,6 +2886,7 @@ void acl_update_user(const char *user, const char *host, enum SSL_type ssl_type, } } } + rebuild_cached_acl_users_for_name(); DBUG_VOID_RETURN; } @@ -2868,6 +2967,7 @@ void acl_insert_user(THD *thd MY_ATTRIBUTE((unused)), const char *user, 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 9ceb46f1a22..6c6889a8e46 100644 --- a/sql/auth/sql_auth_cache.h +++ b/sql/auth/sql_auth_cache.h @@ -281,6 +281,36 @@ 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 */ extern MEM_ROOT global_acl_memory; diff --git a/sql/auth/sql_authentication.cc b/sql/auth/sql_authentication.cc index 488ff8b213b..c094a6df404 100644 --- a/sql/auth/sql_authentication.cc +++ b/sql/auth/sql_authentication.cc @@ -1685,17 +1685,21 @@ static bool find_mpvio_user(THD *thd, MPVIO_EXT *mpvio) { DBUG_PRINT("info", ("entry: %s", mpvio->auth_info.user_name)); DBUG_ASSERT(mpvio->acl_user == 0); + Acl_cache_lock_guard acl_cache_lock(thd, Acl_cache_lock_mode::READ_MODE); + if (!acl_cache_lock.lock(false)) DBUG_RETURN(true); + + Acl_user_ptr_list *list = nullptr; if (likely(acl_users)) { - Acl_cache_lock_guard acl_cache_lock(thd, Acl_cache_lock_mode::READ_MODE); - if (!acl_cache_lock.lock(false)) DBUG_RETURN(true); + 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); - for (ACL_USER *acl_user_tmp = acl_users->begin(); - acl_user_tmp != acl_users->end(); ++acl_user_tmp) { 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)) { mpvio->acl_user = acl_user_tmp->copy(mpvio->mem_root); - /* When setting mpvio->acl_user_plugin we can save memory allocation if this is a built in plugin. @@ -1709,8 +1713,8 @@ static bool find_mpvio_user(THD *thd, MPVIO_EXT *mpvio) { break; } } - acl_cache_lock.unlock(); } + acl_cache_lock.unlock(); if (!mpvio->acl_user) { /* diff --git a/sql/auth/sql_user.cc b/sql/auth/sql_user.cc index c91a413c373..ded40665f1a 100644 --- a/sql/auth/sql_user.cc +++ b/sql/auth/sql_user.cc @@ -1329,6 +1329,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. @@ -1341,6 +1342,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 { /* If search is requested, we do not need to search further. */ break; @@ -1931,6 +1933,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()) { String operation_str; @@ -2077,6 +2080,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());