diff options
-rw-r--r-- | mysql-test/main/grant5.result | 25 | ||||
-rw-r--r-- | mysql-test/main/grant5.test | 38 | ||||
-rw-r--r-- | sql/sql_acl.cc | 73 | ||||
-rw-r--r-- | sql/sql_acl_getsort.ic | 205 |
4 files changed, 286 insertions, 55 deletions
diff --git a/mysql-test/main/grant5.result b/mysql-test/main/grant5.result index c35e8201582..086ae7011e4 100644 --- a/mysql-test/main/grant5.result +++ b/mysql-test/main/grant5.result @@ -102,3 +102,28 @@ u6 Y mysql_old_password 78a302dd267f6044 u7 Y mysql_old_password 78a302dd267f6044 u8 Y nonexistent 78a302dd267f6044 drop user u1@h, u2@h, u3@h, u4@h, u5@h, u6@h, u7@h, u8@h; +create database mysqltest_1; +create user twg@'%' identified by 'test'; +create table mysqltest_1.t1(id int); +grant create, drop on `mysqltest_1%`.* to twg@'%'; +grant all privileges on `mysqltest_1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; +revoke all privileges, grant option from twg@'%'; +grant create, drop on `mysqlt%`.* to twg@'%'; +grant all privileges on `mysqlt%1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; +revoke all privileges, grant option from twg@'%'; +grant create, drop on `mysqlt%`.* to twg@'%'; +grant all privileges on `%mysqltest_1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; +drop database mysqltest_1; +drop user twg@'%'; diff --git a/mysql-test/main/grant5.test b/mysql-test/main/grant5.test index cc673754461..4db262c25c1 100644 --- a/mysql-test/main/grant5.test +++ b/mysql-test/main/grant5.test @@ -86,3 +86,41 @@ select user,select_priv,plugin,authentication_string from mysql.user where user # but they still can be dropped drop user u1@h, u2@h, u3@h, u4@h, u5@h, u6@h, u7@h, u8@h; + +# +# MDEV-14735 better matching order for grants +# MDEV-14732 mysql.db privileges evaluated on order of grants rather than hierarchically +# MDEV-8269 Correct fix for Bug #20181776 :- ACCESS CONTROL DOESN'T MATCH MOST SPECIFIC HOST WHEN IT CONTAINS WILDCARD +# +create database mysqltest_1; +create user twg@'%' identified by 'test'; +create table mysqltest_1.t1(id int); + +# MDEV-14732 test case +grant create, drop on `mysqltest_1%`.* to twg@'%'; +grant all privileges on `mysqltest_1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; + +# prefix%suffix +revoke all privileges, grant option from twg@'%'; +grant create, drop on `mysqlt%`.* to twg@'%'; +grant all privileges on `mysqlt%1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; + +# more specific can even have a shorter prefix +revoke all privileges, grant option from twg@'%'; +grant create, drop on `mysqlt%`.* to twg@'%'; +grant all privileges on `%mysqltest_1`.* to twg@'%'; +connect conn1,localhost,twg,test,mysqltest_1; +insert into t1 values(1); +disconnect conn1; +connection default; + +drop database mysqltest_1; +drop user twg@'%'; diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc index f549d295a50..17ae6dc036a 100644 --- a/sql/sql_acl.cc +++ b/sql/sql_acl.cc @@ -62,6 +62,12 @@ bool mysql_user_table_is_in_short_password_format= false; bool using_global_priv_table= true; +// set that from field length in acl_load? +const uint max_hostname_length= 60; +const uint max_dbname_length= 64; + +#include "sql_acl_getsort.ic" + static LEX_CSTRING native_password_plugin_name= { STRING_WITH_LEN("mysql_native_password") }; @@ -117,7 +123,7 @@ static bool compare_hostname(const acl_host_and_ip *, const char *, const char * class ACL_ACCESS { public: - ulong sort; + ulonglong sort; ulong access; ACL_ACCESS() :sort(0), access(0) @@ -284,7 +290,6 @@ ulong role_global_merges= 0, role_db_merges= 0, role_table_merges= 0, #ifndef NO_EMBEDDED_ACCESS_CHECKS static void update_hostname(acl_host_and_ip *host, const char *hostname); -static ulong get_sort(uint count,...); static bool show_proxy_grants (THD *, const char *, const char *, char *, size_t); static bool show_role_grants(THD *, const char *, const char *, @@ -332,7 +337,8 @@ public: (proxied_host_arg && *proxied_host_arg) ? proxied_host_arg : NULL); with_grant= with_grant_arg; - sort= get_sort(4, host.hostname, user, proxied_host.hostname, proxied_user); + sort= get_magic_sort("huhu", host.hostname, user, proxied_host.hostname, + proxied_user); } void init(MEM_ROOT *mem, const char *host_arg, const char *user_arg, @@ -2344,7 +2350,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables) } host.access= host_table.get_access(); host.access= fix_rights_for_db(host.access); - host.sort= get_sort(2, host.host.hostname, host.db); + host.sort= get_magic_sort("hd", host.host.hostname, host.db); if (check_no_resolve && hostname_requires_resolving(host.host.hostname)) { sql_print_warning("'host' entry '%s|%s' " @@ -2386,7 +2392,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables) user.access= user_table.get_access(); - user.sort= get_sort(2, user.host.hostname, user.user.str); + user.sort= get_magic_sort("hu", user.host.hostname, user.user.str); user.hostname_length= safe_strlen(user.host.hostname); my_init_dynamic_array(&user.role_grants, sizeof(ACL_ROLE *), 0, 8, MYF(0)); @@ -2505,7 +2511,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables) db.db, db.user, safe_str(db.host.hostname)); } } - db.sort=get_sort(3,db.host.hostname,db.db,db.user); + db.sort=get_magic_sort("hdu", db.host.hostname, db.db, db.user); #ifndef TO_BE_REMOVED if (db_table.num_fields() <= 9) { // Without grant @@ -2753,49 +2759,6 @@ static ulong get_access(TABLE *form, uint fieldnr, uint *next_field) } -/* - Return a number which, if sorted 'desc', puts strings in this order: - no wildcards - wildcards - empty string -*/ - -static ulong get_sort(uint count,...) -{ - va_list args; - va_start(args,count); - ulong sort=0; - - /* Should not use this function with more than 4 arguments for compare. */ - DBUG_ASSERT(count <= 4); - - while (count--) - { - char *start, *str= va_arg(args,char*); - uint chars= 0; - uint wild_pos= 0; /* first wildcard position */ - - if ((start= str)) - { - for (; *str ; str++) - { - if (*str == wild_prefix && str[1]) - str++; - else if (*str == wild_many || *str == wild_one) - { - wild_pos= (uint) (str - start) + 1; - break; - } - chars= 128; // Marker that chars existed - } - } - sort= (sort << 8) + (wild_pos ? MY_MIN(wild_pos, 127U) : chars); - } - va_end(args); - return sort; -} - - static int acl_compare(const ACL_ACCESS *a, const ACL_ACCESS *b) { if (a->sort > b->sort) @@ -3157,7 +3120,7 @@ ACL_USER::ACL_USER(THD *thd, const LEX_USER &combo, user= safe_lexcstrdup_root(&acl_memroot, combo.user); update_hostname(&host, safe_strdup_root(&acl_memroot, combo.host.str)); hostname_length= combo.host.length; - sort= get_sort(2, host.hostname, user.str); + sort= get_magic_sort("hu", host.hostname, user.str); password_last_changed= thd->query_start(); password_lifetime= -1; my_init_dynamic_array(&role_grants, sizeof(ACL_USER *), 0, 8, MYF(0)); @@ -3314,7 +3277,7 @@ static void acl_insert_db(const char *user, const char *host, const char *db, update_hostname(&acl_db.host, safe_strdup_root(&acl_memroot, host)); acl_db.db=strdup_root(&acl_memroot,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); + acl_db.sort=get_magic_sort("hdu", acl_db.host.hostname, acl_db.db, acl_db.user); acl_dbs.push(acl_db); rebuild_acl_dbs(); } @@ -5033,7 +4996,7 @@ public: char *db, *user, *tname, *hash_key; ulong privs; ulong init_privs; /* privileges found in physical table */ - ulong sort; + ulonglong sort; size_t key_length; GRANT_NAME(const char *h, const char *d,const char *u, const char *t, ulong p, bool is_routine); @@ -5079,7 +5042,7 @@ void GRANT_NAME::set_user_details(const char *h, const char *d, my_casedn_str(files_charset_info, db); } user = strdup_root(&grant_memroot,u); - sort= get_sort(3,host.hostname,db,user); + sort= get_magic_sort("hdu", host.hostname, db, user); if (tname != t) { tname= strdup_root(&grant_memroot, t); @@ -5121,7 +5084,7 @@ GRANT_NAME::GRANT_NAME(TABLE *form, bool is_routine) update_hostname(&host, hostname); db= get_field(&grant_memroot,form->field[1]); - sort= get_sort(3, host.hostname, db, user); + sort= get_magic_sort("hdu", host.hostname, db, user); tname= get_field(&grant_memroot,form->field[3]); if (!db || !tname) { @@ -6214,7 +6177,7 @@ static int update_role_db(int merged, int first, ulong access, acl_db.db= acl_dbs.at(first).db; acl_db.access= access; acl_db.initial_access= 0; - acl_db.sort=get_sort(3, "", acl_db.db, role); + acl_db.sort= get_magic_sort("hdu", "", acl_db.db, role); acl_dbs.push(acl_db); return 2; } diff --git a/sql/sql_acl_getsort.ic b/sql/sql_acl_getsort.ic new file mode 100644 index 00000000000..df55c7c5f1e --- /dev/null +++ b/sql/sql_acl_getsort.ic @@ -0,0 +1,205 @@ +/* Copyright (c) 2019, MariaDB Corporation. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */ + +#ifndef NO_EMBEDDED_ACCESS_CHECKS +/* + Returns a number which, if sorted in descending order, magically puts + patterns in the order from most specific (e.g. no wildcards) to most generic + (e.g. "%"). That is, the larger the number, the more specific the pattern is. + + Takes a template that lists types of following patterns (by the first letter + of _h_ostname, _d_bname, _u_sername) and up to four patterns. + No more than two can be of 'h' or 'd' type (because one magic value takes 26 + bits, see below). + + ======================================================================== + + Here's how the magic is created: + + Let's look at one iteration of the for() loop. That's one pattern. With + wildcards (usernames aren't interesting). + + By definition a pattern A is "more specific" than pattern B if the set of + strings that match the pattern A is smaller than the set of strings that + match the pattern B. Strings are taken from the big superset of all valid + utf8 strings up to the maxlen. + + Strings are matched character by character. For every non-wildcard + character there can be only one matching character in the matched string. + + For a wild_one character ('_') any valid utf8 character will do. Below + numchars would mean a total number of vaid utf8 characters. It's a huge + number. A number of matching strings for wild_one will be numchars. + + For a wild_many character ('%') any number of valid utf8 characters will do. + How many string will match it depends on the amount of non-wild_many + characters. Say, if a number of non-wildcard characters is N, and a number + of wild_one characters is M, and the number of wild_many characters is K, + then for K=1 its wild_many character will match any number of valid utf8 + characters from 0 to L=maxlen-N-M. The number of matching strings will be + + 1 + numchars + numchars^2 + numchars^3 + ... + numchars^L + + Intermediate result: if M=K=0, the pattern will match only one string, + if M>0, K=0, the pattern will match numchars^M strings, if K=1, the + pattern will match + + numchars^M + 1 + numchars + numchars^2 + ... + numchars^L + + For a more visual notation, let's write these huge numbers not as + decimal or binary, but base numchars. Then the last number will be + a sum of two numbers: the first is one followed by M zeros, the second + constists of L+1 ones: + + 1000{...M...}000 + 111{...L+1...}1111 + + This could produce any of the following + + 111...112111...1111 if L > M, K = 1 + 100...001111...1111 if M > L, K = 1 + 2111111...111111111 if M = L, K = 1 + 1111111...111111111 if M = 0, K = 1 + 1000000...000000000 if K = 0, M > 0 + + There are two complications caused by multiple wild_many characters. + For, say, two wild_many characters, either can accept any number of utf8 + characters, as long the the total amount of them is less then or equal to L. + Same logic applies to any number of non-consequent wild_many characters + (consequent wild_many characters count as one). This gives the number of + matching strings of + + 1 + F(K,1)*numchars + F(K,2)*numchars^2 + ... + F(K,L)*numchars^L + + where F(K,R) is the "number of ways one can put R balls into K boxes", + that is C^{K-1}_{R+K-1}. + + In the "base numchars" notation, it means that besides 0, 1, and 2, + an R-th digit can be F(K,R). For the purpose of comparison, we only need + to know the most significant digit, F(K, L). + While it can be huge, we don't need the exact value, it's a + a monotonously increasing function of K, so if K1>K2, F(K1,L) > F(K2,L) + and we can simply compare values of K instead of complex F(K,L). + + The second complication: F(K,R) gives only an upper boundary, the + actual number of matched strings can be smaller. + Example: pattern "a%b%c" can match "abbc" as a(b)b()c, and as a()b(b)c. + F(2,1) = 2, but it's only one string "abbc". + We'll ignore it here under assumption that it almost never happens + in practice and this simplification won't noticeably disrupt the ordering. + + The last detail: old get_sort function sorted by the non-wildcard prefix + length, so in "abc_" and "a_bc" the former one was sorted first. Strictly + speaking they're both equally specific, but to preserve the backward + compatible sorting we'll use the P "prefix length or 0 if no wildcards" + to break ties. + + Now, let's compare two long numbers. Numbers are easy to compare, + the longer number is larger. If they both have the same lengths, + the one with the larger first digit is larger, and so on. + + But there is no need to actually calculate these numbers. + Three numbers L, K, M (and P to break ties) are enough to describe a pattern + for a purpose of comparison. L/K/M triplets can be compared like this: + + * case 1: if for both patterns L>M: compare L, K, M, in that order + because: + - if L1 > L2, the first number is longer + - If L1 == L2, then the first digit is a monotonously increasing function + of K, so the first digit is larger when K is larger + - if K1 == K2, then all other digits in these numbers would be the + same too, with the exception of one digit in the middle that + got +1 because of +1000{...M...}000. So, whatever number has a + larger M will get this +1 first. + * case 2: if for both patterns L<M: compare M, L, K, in that order + * case 3: if for both patterns L=M: compare L (or M), K + * case 4: if one L1>M1, other L2=M2: compare L, K, M + * case 5: if one L1<M1, other L2=M2: compare M, L, K + * case 6: if one pattern L1>M1, the other M2>L2: first is more generic + unless (case 6a) K1=K2=1,M1=0,M2=L2+1 (in that case - equal) + + note that in case 3 one can use a rule from the case either 1 or 2, + in the case 4 one can use the rule from the case 1, + in the case 5 one can use the rule from the case 2. + + for the case 6 and ignoring the special case 6a, to compare patterns by a + magic number as a function z(a,b,c), we must ensure that z(L1,K1,M1) is + greater than z(M2,L2,K2) when L1=M2. This can be done by an extra bit, + which is 1 for K and 0 for L. Thus, the magic number could be + + case 1: (((L*2 + 1)*(maxlen+1) + K)*(maxlen+1) + M)*(maxlen+1) + P + case 2: ((M*2*(maxlen+1) + L)*(maxlen+1) + K)*(maxlen+1) + P + + upper bound: L<=maxlen, M<=maxlen, K<=maxlen/2, P<maxlen + for a current maxlen=64, the magic number needs 26 bits. +*/ + +static ulonglong get_magic_sort(const char *templ, ...) +{ + ulonglong sort=0; + va_list args; + va_start(args, templ); + + IF_DBUG(uint bits_used= 0,); + + for (; *templ; templ++) + { + char *pat= va_arg(args, char*); + + if (*templ == 'u') + { + /* Username. Can be empty (= anybody) or a literal. Encoded in one bit */ + sort= (sort << 1) + !*pat; + IF_DBUG(bits_used++,); + continue; + } + + /* A wildcard pattern. Encoded in 26 bits. */ + uint maxlen= *templ == 'd' ? max_dbname_length : max_hostname_length; + DBUG_ASSERT(maxlen <= 64); + DBUG_ASSERT(*templ == 'd' || *templ == 'h'); + + uint N= 0, M= 0, K= 0, P= 0; + for (uint i=0; pat[i]; i++) + { + if (pat[i] == wild_many) + { + if (!K && !M) P= N; + K++; + while (pat[i+1] == wild_many) i++; + continue; + } + if (pat[i] == wild_one) + { + if (!K && !M) P= N; + M++; + continue; + } + if (pat[i] == wild_prefix && pat[i+1]) i++; + N++; + } + uint L= K ? maxlen - N - M : 0, d= maxlen + 1, magic; + if (L > M) + magic= (((L * 2 + 1) * d + K) * d + M) * d + P; + else + magic= (((M * 2 + 0) * d + L) * d + K) * d + P; + DBUG_ASSERT(magic < 1<<26); + sort= (sort << 26) + magic; + IF_DBUG(bits_used+= 26,); + } + DBUG_ASSERT(bits_used < 8*sizeof(sort)); + va_end(args); + return ~sort; +} +#endif |