maria-developers team mailing list archive

[Sergei Golubchik <serg@xxxxxxxxxxx>]

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 <wlad@xxxxxxxxxxx>
> committer: Vladislav Vaintroub <wlad@xxxxxxxxxxx>
> 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@xxxxxxxxxxx