From 03486e08be152e2960d78d6ea59129a342519304 Mon Sep 17 00:00:00 2001 From: Vladislav Vaintroub Date: Mon, 26 Nov 2018 21:24:05 +0100 Subject: MDEV-15649 Speedup search in acl_users and acl_dbs array, sorting them by usernames first, and then by get_sort() value. Search functions now use binary search to find the the first entry with given name. Then, linear search is done, until the first match. --- mysql-test/main/failed_auth_3909.result | 12 +- mysql-test/main/failed_auth_3909.test | 12 +- .../r/hostcache_ipv4_nameinfo_again_allow.result | 4 +- .../r/hostcache_ipv6_nameinfo_again_allow.result | 4 +- sql/sql_acl.cc | 319 ++++++++++++++------- 5 files changed, 239 insertions(+), 112 deletions(-) diff --git a/mysql-test/main/failed_auth_3909.result b/mysql-test/main/failed_auth_3909.result index 4c3c0aba9df..bc82492c9ed 100644 --- a/mysql-test/main/failed_auth_3909.result +++ b/mysql-test/main/failed_auth_3909.result @@ -10,15 +10,15 @@ Warning 1364 Field 'authentication_string' doesn't have a default value flush privileges; connect(localhost,u1,,test,MASTER_PORT,MASTER_SOCKET); connect fail,localhost,u1; -ERROR HY000: Server is running in --secure-auth mode, but 'u1'@'localhost' has a password in the old format; please change the password to the new format +ERROR 28000: Access denied for user 'u1'@'localhost' (using password: NO) connect(localhost,u2,,test,MASTER_PORT,MASTER_SOCKET); connect fail,localhost,u2; -ERROR 28000: Access denied for user 'u2'@'localhost' (using password: NO) +ERROR HY000: Server is running in --secure-auth mode, but 'u2'@'localhost' has a password in the old format; please change the password to the new format connect(localhost,u2,password,test,MASTER_PORT,MASTER_SOCKET); connect fail,localhost,u2,password; -ERROR 28000: Access denied for user 'u2'@'localhost' (using password: YES) -ERROR HY000: Server is running in --secure-auth mode, but 'u1'@'localhost' has a password in the old format; please change the password to the new format -ERROR 28000: Access denied for user 'u2'@'localhost' (using password: NO) -ERROR 28000: Access denied for user 'u2'@'localhost' (using password: YES) +ERROR HY000: Server is running in --secure-auth mode, but 'u2'@'localhost' has a password in the old format; please change the password to the new format +ERROR 28000: Access denied for user 'u1'@'localhost' (using password: NO) +ERROR HY000: Server is running in --secure-auth mode, but 'u2'@'localhost' has a password in the old format; please change the password to the new format +ERROR HY000: Server is running in --secure-auth mode, but 'u2'@'localhost' has a password in the old format; please change the password to the new format delete from mysql.user where plugin = 'mysql_old_password'; flush privileges; diff --git a/mysql-test/main/failed_auth_3909.test b/mysql-test/main/failed_auth_3909.test index fb104cf4b81..45267d628b2 100644 --- a/mysql-test/main/failed_auth_3909.test +++ b/mysql-test/main/failed_auth_3909.test @@ -11,24 +11,24 @@ insert ignore mysql.user (user,plugin) values ('foo','mysql_old_password'),('bar flush privileges; --replace_result $MASTER_MYSOCK MASTER_SOCKET $MASTER_MYPORT MASTER_PORT ---error ER_SERVER_IS_IN_SECURE_AUTH_MODE +--error ER_ACCESS_DENIED_ERROR connect (fail,localhost,u1); --replace_result $MASTER_MYSOCK MASTER_SOCKET $MASTER_MYPORT MASTER_PORT ---error ER_ACCESS_DENIED_ERROR +--error ER_SERVER_IS_IN_SECURE_AUTH_MODE connect (fail,localhost,u2); --replace_result $MASTER_MYSOCK MASTER_SOCKET $MASTER_MYPORT MASTER_PORT ---error ER_ACCESS_DENIED_ERROR +--error ER_SERVER_IS_IN_SECURE_AUTH_MODE connect (fail,localhost,u2,password); ---error ER_SERVER_IS_IN_SECURE_AUTH_MODE +--error ER_ACCESS_DENIED_ERROR change_user u1; ---error ER_ACCESS_DENIED_ERROR +--error ER_SERVER_IS_IN_SECURE_AUTH_MODE change_user u2; ---error ER_ACCESS_DENIED_ERROR +--error ER_SERVER_IS_IN_SECURE_AUTH_MODE change_user u2,password; delete from mysql.user where plugin = 'mysql_old_password'; diff --git a/mysql-test/suite/perfschema/r/hostcache_ipv4_nameinfo_again_allow.result b/mysql-test/suite/perfschema/r/hostcache_ipv4_nameinfo_again_allow.result index a172dff7935..7963bed8213 100644 --- a/mysql-test/suite/perfschema/r/hostcache_ipv4_nameinfo_again_allow.result +++ b/mysql-test/suite/perfschema/r/hostcache_ipv4_nameinfo_again_allow.result @@ -118,7 +118,7 @@ Con4 is alive Con4 is alive select current_user(); current_user() -root@192.0.2.4 +root@santa.claus.ipv4.example.com disconnect con4; connection default; "Dumping performance_schema.host_cache" @@ -155,7 +155,7 @@ Con5 is alive Con5 is alive select current_user(); current_user() -root@192.0.2.4 +root@santa.claus.ipv4.example.com disconnect con5; connection default; "Dumping performance_schema.host_cache" diff --git a/mysql-test/suite/perfschema/r/hostcache_ipv6_nameinfo_again_allow.result b/mysql-test/suite/perfschema/r/hostcache_ipv6_nameinfo_again_allow.result index 4fdc6ef1b4c..baddc88b116 100644 --- a/mysql-test/suite/perfschema/r/hostcache_ipv6_nameinfo_again_allow.result +++ b/mysql-test/suite/perfschema/r/hostcache_ipv6_nameinfo_again_allow.result @@ -118,7 +118,7 @@ Con4 is alive Con4 is alive select current_user(); current_user() -root@2001:db8::6:6 +root@santa.claus.ipv6.example.com disconnect con4; connection default; "Dumping performance_schema.host_cache" @@ -155,7 +155,7 @@ Con5 is alive Con5 is alive select current_user(); current_user() -root@2001:db8::6:6 +root@santa.claus.ipv6.example.com disconnect con5; connection default; "Dumping performance_schema.host_cache" diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc index 052c5ada3a2..c43f4024862 100644 --- a/sql/sql_acl.cc +++ b/sql/sql_acl.cc @@ -187,6 +187,8 @@ public: bool eq(const char *user2, const char *host2) { return !cmp(user2, host2); } + const char *get_username(){ return user.str; } + bool wild_eq(const char *user2, const char *host2, const char *ip2) { if (strcmp(user.str, user2)) @@ -228,6 +230,8 @@ public: acl_host_and_ip host; const char *user,*db; ulong initial_access; /* access bits present in the table */ + + const char *get_username() { return user; } }; #ifndef DBUG_OFF @@ -610,7 +614,11 @@ static DYNAMIC_ARRAY acl_wild_hosts; static Hash_filo *acl_cache; static uint grant_version=0; /* Version of priv tables. incremented by acl_load */ static ulong get_access(TABLE *form,uint fieldnr, uint *next_field=0); -static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b); +static int acl_compare(const ACL_ACCESS *a, const ACL_ACCESS *b); +static int acl_user_compare(const ACL_USER *a, const ACL_USER *b); +static void rebuild_acl_users(); +static int acl_db_compare(const ACL_DB *a, const ACL_DB *b); +static void rebuild_acl_dbs(); static ulong get_sort(uint count,...); static void init_check_host(void); static void rebuild_check_host(void); @@ -1973,8 +1981,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables) DBUG_PRINT("info", ("Found user %s", user.user.str)); push_new_user(user); } - my_qsort((uchar*) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements, - sizeof(ACL_USER),(qsort_cmp) acl_compare); + rebuild_acl_users(); end_read_record(&read_record_info); freeze_size(&acl_users); @@ -2038,8 +2045,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables) #endif (void) push_dynamic(&acl_dbs,(uchar*) &db); } - my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements, - sizeof(ACL_DB),(qsort_cmp) acl_compare); + rebuild_acl_dbs(); end_read_record(&read_record_info); freeze_size(&acl_dbs); @@ -2317,7 +2323,7 @@ static ulong get_sort(uint count,...) } -static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b) +static int acl_compare(const ACL_ACCESS *a, const ACL_ACCESS *b) { if (a->sort > b->sort) return -1; @@ -2326,6 +2332,156 @@ static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b) return 0; } +static int acl_user_compare(const ACL_USER *a, const ACL_USER *b) +{ + int res= strcmp(a->user.str, b->user.str); + if (res) + return res; + + res= acl_compare(a, b); + if (res) + return res; + + /* + For more deterministic results, resolve ambiguity between + "localhost" and "127.0.0.1"/"::1" by sorting "localhost" before + loopback addresses. + Test suite (on Windows) expects "root@localhost", even if + root@::1 would also match. + */ + return -strcmp(a->host.hostname, b->host.hostname); +} + +static int acl_db_compare(const ACL_DB *a, const ACL_DB *b) +{ + int res= strcmp(a->user, b->user); + if (res) + return res; + + return acl_compare(a, b); +} + +static void rebuild_acl_users() +{ + my_qsort((uchar*)dynamic_element(&acl_users, 0, ACL_USER*), acl_users.elements, + sizeof(ACL_USER), (qsort_cmp)acl_user_compare); +} + +static void rebuild_acl_dbs() +{ + my_qsort((uchar*)dynamic_element(&acl_dbs, 0, ACL_DB*), acl_dbs.elements, + sizeof(ACL_DB), (qsort_cmp)acl_db_compare); +} + + +/* + Return index of the first entry with given user in the array, + or UINT_MAX if not found. + + Assumes the array is sorted by get_username +*/ +template uint find_first_user(T* arr, uint len, const char *user) +{ + uint low= 0; + uint high= len; + uint mid; + + bool found= false; + if(!len) + return UINT_MAX; + +#ifndef DBUG_OFF + for (uint i = 0; i < len - 1; i++) + DBUG_ASSERT(strcmp(arr[i].get_username(), arr[i + 1].get_username()) <= 0); +#endif + while (low < high) + { + mid= low + (high - low) / 2; + int cmp= strcmp(arr[mid].get_username(),user); + if (cmp == 0) + found= true; + + if (cmp >= 0 ) + high= mid; + else + low= mid + 1; + } + return (!found || low == len || strcmp(arr[low].get_username(), user)!=0 )?UINT_MAX:low; +} + +static uint acl_find_user_by_name(const char *user) +{ + return find_first_user((ACL_USER *)acl_users.buffer,acl_users.elements,user); +} + +static uint acl_find_db_by_username(const char *user) +{ + return find_first_user((ACL_DB *)acl_dbs.buffer, acl_dbs.elements, user); +} + +static bool match_db(ACL_DB *acl_db, const char *db, my_bool db_is_pattern) +{ + return !acl_db->db || (db && !wild_compare(db, acl_db->db, db_is_pattern)); +} + + +/* + Lookup in the acl_users or acl_dbs for the best matching entry corresponding to + given user, host and ip parameters (also db, in case of ACL_DB) + + Historical note: + + In the past, both arrays were sorted just by ACL_ENTRY::sort field and were + searched linearly, until the first match of (username,host) pair was found. + + This function uses optimizations (binary search by username), yet preserves the + historical behavior, i.e the returns a match with highest ACL_ENTRY::sort. +*/ +template T* find_by_username_or_anon(DYNAMIC_ARRAY *dynarray, const char *user, + const char *host, const char *ip, + const char *db, my_bool db_is_pattern, bool (*match_db_func)(T*,const char *,my_bool)) +{ + uint i; + T *ret = NULL; + T* arr= (T*)dynarray->buffer; + uint len= dynarray->elements; + + // Check entries matching user name. + uint start = find_first_user(arr, len, user); + for (i= start; i < len; i++) + { + T *entry= &arr[i]; + if (i > start && strcmp(user, entry->get_username())) + break; + + if (compare_hostname(&entry->host, host, ip) && (!match_db_func || match_db_func(entry, db, db_is_pattern))) + { + ret= entry; + break; + } + } + + // Look also for anonymous user (username is empty string) + // Due to sort by name, entries for anonymous user start at the start of array. + for (i= 0; i < len; i++) + { + T *entry = &arr[i]; + if (*entry->get_username() || (ret && acl_compare(entry, ret) >= 0)) + break; + if (compare_hostname(&entry->host, host, ip) && (!match_db_func || match_db_func(entry, db, db_is_pattern))) + { + ret= entry; + break; + } + } + return ret; +} + +static ACL_DB *acl_db_find(const char *db, const char *user, const char *host, const char *ip, my_bool db_is_pattern) +{ + return find_by_username_or_anon(&acl_dbs, user, host, ip, db, db_is_pattern, match_db); +} + /* Gets user credentials without authentication and resource limit checks. @@ -2347,7 +2503,6 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host, const char *ip, const char *db) { int res= 1; - uint i; ACL_USER *acl_user= 0; DBUG_ENTER("acl_getroot"); @@ -2380,21 +2535,10 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host, if (acl_user) { res= 0; - for (i=0 ; i < acl_dbs.elements ; i++) - { - ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*); - if (!*acl_db->user || !strcmp(user, acl_db->user)) - { - if (compare_hostname(&acl_db->host, host, ip)) - { - if (!acl_db->db || (db && !wild_compare(db, acl_db->db, 0))) - { - sctx->db_access= acl_db->access; - break; - } - } - } - } + ACL_DB *acl_db= acl_db_find(db, user, host, ip, FALSE); + if(acl_db) + sctx->db_access = acl_db->access; + sctx->master_access= acl_user->access; strmake_buf(sctx->priv_user, user); @@ -2409,21 +2553,10 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host, if (acl_role) { res= 0; - for (i=0 ; i < acl_dbs.elements ; i++) - { - ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*); - if (!*acl_db->user || !strcmp(user, acl_db->user)) - { - if (compare_hostname(&acl_db->host, "", "")) - { - if (!acl_db->db || (db && !wild_compare(db, acl_db->db, 0))) - { - sctx->db_access= acl_db->access; - break; - } - } - } - } + ACL_DB *acl_db = acl_db_find(db, user, "", "", FALSE); + if (acl_db) + sctx->db_access = acl_db->access; + sctx->master_access= acl_role->access; strmake_buf(sctx->priv_role, user); @@ -2622,7 +2755,7 @@ static bool acl_update_db(const char *user, const char *host, const char *db, bool updated= false; - for (uint i=0 ; i < acl_dbs.elements ; i++) + for (uint i=acl_find_db_by_username(user) ; i < acl_dbs.elements ; i++) { ACL_DB *acl_db=dynamic_element(&acl_dbs,i,ACL_DB*); if (!strcmp(user, acl_db->user)) @@ -2645,6 +2778,8 @@ static bool acl_update_db(const char *user, const char *host, const char *db, } } } + else + break; } return updated; @@ -2676,8 +2811,7 @@ static void acl_insert_db(const char *user, const char *host, const char *db, acl_db.initial_access= acl_db.access= privileges; acl_db.sort=get_sort(3,acl_db.host.hostname,acl_db.db,acl_db.user); (void) push_dynamic(&acl_dbs,(uchar*) &acl_db); - my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements, - sizeof(ACL_DB),(qsort_cmp) acl_compare); + rebuild_acl_dbs(); } @@ -2723,26 +2857,18 @@ ulong acl_get(const char *host, const char *ip, /* Check if there are some access rights for database and user */ - for (i=0 ; i < acl_dbs.elements ; i++) + ACL_DB *acl_db = acl_db_find(db,user, host, ip, db_is_pattern); + + if (acl_db) { - ACL_DB *acl_db=dynamic_element(&acl_dbs,i,ACL_DB*); - if (!*acl_db->user || !strcmp(user, acl_db->user)) - { - if (compare_hostname(&acl_db->host,host,ip)) - { - if (!acl_db->db || !wild_compare(db,acl_db->db,db_is_pattern)) - { - db_access=acl_db->access; - if (acl_db->host.hostname) - goto exit; // Fully specified. Take it - /* the host table is not used for roles */ - if ((!host || !host[0]) && !acl_db->host.hostname && find_acl_role(user)) - goto exit; - break; /* purecov: tested */ - } - } - } + db_access= acl_db->access; + if (acl_db->host.hostname) + goto exit; // Fully specified. Take it + /* the host table is not used for roles */ + if ((!host || !host[0]) && !acl_db->host.hostname && find_acl_role(user)) + goto exit; } + if (!db_access) goto exit; // Can't be better @@ -3397,20 +3523,7 @@ bool is_acl_user(const char *host, const char *user) */ static ACL_USER *find_user_or_anon(const char *host, const char *user, const char *ip) { - ACL_USER *result= NULL; - mysql_mutex_assert_owner(&acl_cache->lock); - for (uint i=0; i < acl_users.elements; i++) - { - ACL_USER *acl_user_tmp= dynamic_element(&acl_users, i, ACL_USER*); - if ((!acl_user_tmp->user.length || - !strcmp(user, acl_user_tmp->user.str)) && - compare_hostname(&acl_user_tmp->host, host, ip)) - { - result= acl_user_tmp; - break; - } - } - return result; + return find_by_username_or_anon(&acl_users,user,host, ip, 0, false, 0); } @@ -3420,11 +3533,15 @@ static ACL_USER *find_user_or_anon(const char *host, const char *user, const cha static ACL_USER *find_user_exact(const char *host, const char *user) { mysql_mutex_assert_owner(&acl_cache->lock); + uint start= acl_find_user_by_name(user); - for (uint i=0 ; i < acl_users.elements ; i++) + for (uint i= start; i < acl_users.elements; i++) { - ACL_USER *acl_user=dynamic_element(&acl_users, i, ACL_USER*); - if (acl_user->eq(user, host)) + ACL_USER *acl_user= dynamic_element(&acl_users, i, ACL_USER*); + if (i > start && strcmp(acl_user->user.str, user)) + return 0; + + if (!my_strcasecmp(system_charset_info, acl_user->host.hostname, host)) return acl_user; } return 0; @@ -3437,10 +3554,14 @@ static ACL_USER * find_user_wild(const char *host, const char *user, const char { mysql_mutex_assert_owner(&acl_cache->lock); - for (uint i=0 ; i < acl_users.elements ; i++) + uint start = acl_find_user_by_name(user); + + for (uint i= start; i < acl_users.elements; i++) { ACL_USER *acl_user=dynamic_element(&acl_users,i,ACL_USER*); - if (acl_user->wild_eq(user, host, ip)) + if (i > start && strcmp(acl_user->user.str, user)) + break; + if (compare_hostname(&acl_user->host, host, ip ? ip : host)) return acl_user; } return 0; @@ -3970,8 +4091,7 @@ end: else { push_new_user(new_acl_user); - my_qsort(dynamic_element(&acl_users, 0, ACL_USER*), acl_users.elements, - sizeof(ACL_USER),(qsort_cmp) acl_compare); + rebuild_acl_users(); /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */ rebuild_check_host(); @@ -5615,7 +5735,7 @@ static int update_role_db(ACL_DB *merged, ACL_DB **first, ulong access, 2. it's O(N) operation, and we may need many of them so we only mark elements deleted and will delete later. */ - merged->sort= 0; // lower than any valid ACL_DB sort value, will be sorted last + merged->sort= 0; // mark for deletion return 4; } else if (merged->access != access) @@ -5681,24 +5801,29 @@ static bool merge_role_db_privileges(ACL_ROLE *grantee, const char *dbname, } update_flags|= update_role_db(merged, first, access, grantee->user.str); - /* - to make this code a bit simpler, we sort on deletes, to move - deleted elements to the end of the array. strictly speaking it's - unnecessary, it'd be faster to remove them in one O(N) array scan. - - on the other hand, qsort on almost sorted array is pretty fast anyway... - */ - if (update_flags & (2|4)) - { // inserted or deleted, need to sort - my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements, - sizeof(ACL_DB),(qsort_cmp) acl_compare); - } if (update_flags & 4) - { // deleted, trim the end - while (acl_dbs.elements && - dynamic_element(&acl_dbs, acl_dbs.elements-1, ACL_DB*)->sort == 0) - acl_dbs.elements--; + { + // Remove elements marked for deletion. + uint count= 0; + for(uint i= 0; i < acl_dbs.elements; i++) + { + ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*); + if (acl_db->sort) + { + if (i > count) + set_dynamic(&acl_dbs, acl_db, count); + count++; + } + } + acl_dbs.elements= count; + } + + + if (update_flags & 2) + { // inserted, need to sort + rebuild_acl_dbs(); } + return update_flags; } @@ -10245,6 +10370,8 @@ bool mysql_rename_user(THD *thd, List &list) some_users_renamed= TRUE; } + rebuild_acl_users(); + /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */ rebuild_check_host(); -- cgit v1.2.1