Re: [Maria-developers] 2397c00086c: MDEV-15649 Speedup search in acl_users and acl_dbs array,

Hi, Vladislav! Okay. Frankly, that's not how I'd done it, but it'll work. Only a few minor comments below, then ok to push. On Dec 03, Vladislav Vaintroub wrote:

revision-id: 2397c00086c4d9df5e2bbad70803e293f5a47984 (mariadb-10.4.0-37-g2397c00086c) parent(s): 46a411088c5abbacda4e52e89f4dbcf52a451f7a author: Vladislav Vaintroub committer: Vladislav Vaintroub timestamp: 2018-11-30 18:14:00 +0100 message:

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.

diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc index 052c5ada3a2..932c4189e3f 100644 --- a/sql/sql_acl.cc +++ b/sql/sql_acl.cc @@ -2326,6 +2328,156 @@ static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b) + + +static inline const char *get_username(const ACL_DB& acl_db) +{ + return acl_db.user; +} + + +static inline const char *get_username(const ACL_USER& acl_user) +{ + return acl_user.user.str; +}

I'd do them as methods in ACL_DB and ACL_USER

+ +/* + 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<typename T> uint find_first_user(T* arr, uint len, const char *user) +{ + uint low= 0; + uint high= len - 1; + uint mid; + if(!len) + return UINT_MAX; + +#ifndef DBUG_OFF + for (uint i = 0; i < len - 1; i++) + DBUG_ASSERT(strcmp(get_username(arr[i]), get_username(arr[i + 1])) <= 0); +#endif + while (low <= high) + { + mid = low + (high - low) / 2; + int cmp = strcmp(get_username(arr[mid]), user); + if (cmp == 0) + { + /* + We are looking for the left-most element in the array with the given value. + Thus, even if value is found, we still have to check the left neighbor, + and if it has the same value, continue the search. + */ + if (mid > 0 && !strcmp(get_username(arr[mid - 1]), user)) + cmp = 1;

hmm, I thought, normally it's done not by checking the left neighbor, but by `if (cmp <=0 )` and continuing the search until low>high

+ } + + if (cmp > 0) + { + if (mid == 0) + break; + high= mid - 1; + } + else if (cmp < 0) + low= mid + 1; + else + return mid; + } + return UINT_MAX; +} + +static ACL_DB *acl_db_find(const char *db, const char *user, const char *host, const char *ip, my_bool db_is_pattern) +{ + uint i; + ACL_DB *ret = NULL; + + // Check databases with matching user name. + uint start= acl_find_db_by_username(user); + for (i= start; i < acl_dbs.elements; i++) + { + ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*); + if (i > start && strcmp(user, acl_db->user)) + break; + + if(acl_db_matches(acl_db, db, host, ip,db_is_pattern)) + { + ret= acl_db; + break; + } + } + + // Look also for anonymous user (at the start of array due to sort by name). + for (i = 0; i < acl_dbs.elements; i++) + { + ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*); + if (*acl_db->user || (ret && acl_compare(acl_db, ret) >= 0)) + break; + if (acl_db_matches(acl_db, db, host, ip, db_is_pattern)) + { + ret= acl_db; + break; + } + } + return ret; +}

that's the same logic as in find_user_or_anon(). May be you could template that out too? Another thought - this is a pretty weird-looking search logic. Please add a comment that its goal is to emulate historical behavior, where entries were found by a linear search in an array sorted by the get_sort() value.

@@ -3437,10 +3579,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))

This makes wild_eq method kind of pointless. Remove it?

+ 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;

Regards, Sergei Chief Architect MariaDB and security@mariadb.org