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 <[email protected]> > committer: Vladislav Vaintroub <[email protected]> > 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 [email protected] _______________________________________________ Mailing list: https://launchpad.net/~maria-developers Post to : [email protected] Unsubscribe : https://launchpad.net/~maria-developers More help : https://help.launchpad.net/ListHelp
