revision-id: d74880690cb5c52593eb65c276a1d4a7f6a6105a (mariadb-10.2.31-551-gd74880690cb) parent(s): 65e26bc1ba7b81d8477d51534d30f072f38913a1 author: Varun Gupta committer: Varun Gupta timestamp: 2020-11-02 20:23:00 +0530 message: MDEV-17783: AddressSanitizer: stack-buffer-overflow in table_cond_selectivity with optimizer_use_condition_selectivity > 1, join_cache_level >2 The reason for the overflow was that the code inside the function table_cond_selectivity made an assumption that a key cannot have keyparts more than MAX_REF_PARTS. This is generally true for all the BTREE indexes but not for the hash key. So using a dynamic array instead of a static one to fix this issue --- mysql-test/r/join_cache.result | 31 +++++++++++++++++++++++++++++++ mysql-test/t/join_cache.test | 35 +++++++++++++++++++++++++++++++++++ sql/sql_select.cc | 35 +++++++++++++++++++++++++---------- sql/sql_select.h | 5 +++++ 4 files changed, 96 insertions(+), 10 deletions(-) diff --git a/mysql-test/r/join_cache.result b/mysql-test/r/join_cache.result index e41c79a59f9..7adec6089bf 100644 --- a/mysql-test/r/join_cache.result +++ b/mysql-test/r/join_cache.result @@ -6054,4 +6054,35 @@ select f2 from t2,t1 where f2 = 0; f2 drop table t1, t2; set join_buffer_size=@save_join_buffer_size; +# +# MDEV-17783: AddressSanitizer: stack-buffer-overflow in table_cond_selectivity +# with optimizer_use_condition_selectivity > 1, join_cache_level >2 +# +SET @save_optimizer_use_condition_selectivity=@@optimizer_use_condition_selectivity; +SET @save_join_cache_level= @@join_cache_level; +set join_cache_level=3; +set optimizer_use_condition_selectivity=2; +CREATE TABLE t1 ( +c1 int, c2 int, c3 int, c4 int, c5 int, +c6 int, c7 int, c8 int, c9 int, c10 int, +c11 int, c12 int, c13 int, c14 int, c15 int, +c16 int, c17 int, c18 int, c19 int, c20 int, +c21 int, c22 int, c23 int, c24 int, c25 int, +c26 int, c27 int, c28 int, c29 int, c30 int, +c31 int, c32 int, c33 int, c34 int); +insert into t1 values +(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33), +(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34); +EXPLAIN SELECT t1.c1 FROM t1, t1 t where t1.c1 = t.c1 and t1.c2 = t.c2 and t1.c3 = t.c3 and t1.c4 = t.c4 and t1.c5 = t.c5 and t1.c6 = t.c6 and t1.c7 = t.c7 and t1.c8 = t.c8 and t1.c9 = t.c9 and t1.c10 = t.c10 and t1.c11 = t.c11 and t1.c12 = t.c12 and t1.c13 = t.c13 and t1.c14 = t.c14 and t1.c15 = t.c15 and t1.c16 = t.c16 and t1.c17 = t.c17 and t1.c18 = t.c18 and t1.c19 = t.c19 and t1.c20 = t.c20 and t1.c21 = t.c21 and t1.c22 = t.c22 and t1.c23 = t.c23 and t1.c24 = t.c24 and t1.c25 = t.c25 and t1.c26 = t.c26 and t1.c27 = t.c27 and t1.c28 = t.c28 and t1.c29 = t.c29 and t1.c30 = t.c30 and t1.c31 = t.c31 and t1.c32 = t.c32 and t1.c33 = t.c33 and t1.c34 = t.c34; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where +1 SIMPLE t hash_ALL NULL #hash#$hj 170 test.t1.c1,test.t1.c2,test.t1.c3,test.t1.c4,test.t1.c5,test.t1.c6,test.t1.c7,test.t1.c8,test.t1.c9,test.t1.c10,test.t1.c11,test.t1.c12,test.t1.c13,test.t1.c14,test.t1.c15,test.t1.c16,test.t1.c17,test.t1.c18,test.t1.c19,test.t1.c20,test.t1.c21,test.t1.c22,test.t1.c23,test.t1.c24,test.t1.c25,test.t1.c26,test.t1.c27,test.t1.c28,test.t1.c29,test.t1.c30,test.t1.c31,test.t1.c32,test.t1.c33,test.t1.c34 2 Using where; Using join buffer (flat, BNLH join) +SELECT t1.c1 FROM t1, t1 t where t1.c1 = t.c1 and t1.c2 = t.c2 and t1.c3 = t.c3 and t1.c4 = t.c4 and t1.c5 = t.c5 and t1.c6 = t.c6 and t1.c7 = t.c7 and t1.c8 = t.c8 and t1.c9 = t.c9 and t1.c10 = t.c10 and t1.c11 = t.c11 and t1.c12 = t.c12 and t1.c13 = t.c13 and t1.c14 = t.c14 and t1.c15 = t.c15 and t1.c16 = t.c16 and t1.c17 = t.c17 and t1.c18 = t.c18 and t1.c19 = t.c19 and t1.c20 = t.c20 and t1.c21 = t.c21 and t1.c22 = t.c22 and t1.c23 = t.c23 and t1.c24 = t.c24 and t1.c25 = t.c25 and t1.c26 = t.c26 and t1.c27 = t.c27 and t1.c28 = t.c28 and t1.c29 = t.c29 and t1.c30 = t.c30 and t1.c31 = t.c31 and t1.c32 = t.c32 and t1.c33 = t.c33 and t1.c34 = t.c34; +c1 +0 +1 +DROP TABLE t1; +SET optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +SET join_cache_level= @save_join_cache_level; set @@optimizer_switch=@save_optimizer_switch; +# End of 10.2 tests diff --git a/mysql-test/t/join_cache.test b/mysql-test/t/join_cache.test index 9576d598125..21a4b3e8cb3 100644 --- a/mysql-test/t/join_cache.test +++ b/mysql-test/t/join_cache.test @@ -4014,5 +4014,40 @@ select f2 from t2,t1 where f2 = 0; drop table t1, t2; set join_buffer_size=@save_join_buffer_size; +--echo # +--echo # MDEV-17783: AddressSanitizer: stack-buffer-overflow in table_cond_selectivity +--echo # with optimizer_use_condition_selectivity > 1, join_cache_level >2 +--echo # + +SET @save_optimizer_use_condition_selectivity=@@optimizer_use_condition_selectivity; +SET @save_join_cache_level= @@join_cache_level; +set join_cache_level=3; +set optimizer_use_condition_selectivity=2; + +CREATE TABLE t1 ( +c1 int, c2 int, c3 int, c4 int, c5 int, +c6 int, c7 int, c8 int, c9 int, c10 int, +c11 int, c12 int, c13 int, c14 int, c15 int, +c16 int, c17 int, c18 int, c19 int, c20 int, +c21 int, c22 int, c23 int, c24 int, c25 int, +c26 int, c27 int, c28 int, c29 int, c30 int, +c31 int, c32 int, c33 int, c34 int); + +insert into t1 values +(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33), +(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34); + +let $query= +SELECT t1.c1 FROM t1, t1 t where t1.c1 = t.c1 and t1.c2 = t.c2 and t1.c3 = t.c3 and t1.c4 = t.c4 and t1.c5 = t.c5 and t1.c6 = t.c6 and t1.c7 = t.c7 and t1.c8 = t.c8 and t1.c9 = t.c9 and t1.c10 = t.c10 and t1.c11 = t.c11 and t1.c12 = t.c12 and t1.c13 = t.c13 and t1.c14 = t.c14 and t1.c15 = t.c15 and t1.c16 = t.c16 and t1.c17 = t.c17 and t1.c18 = t.c18 and t1.c19 = t.c19 and t1.c20 = t.c20 and t1.c21 = t.c21 and t1.c22 = t.c22 and t1.c23 = t.c23 and t1.c24 = t.c24 and t1.c25 = t.c25 and t1.c26 = t.c26 and t1.c27 = t.c27 and t1.c28 = t.c28 and t1.c29 = t.c29 and t1.c30 = t.c30 and t1.c31 = t.c31 and t1.c32 = t.c32 and t1.c33 = t.c33 and t1.c34 = t.c34; + +eval EXPLAIN $query; +eval $query; + +DROP TABLE t1; +SET optimizer_use_condition_selectivity=@save_optimizer_use_condition_selectivity; +SET join_cache_level= @save_join_cache_level; + # The following command must be the last one in the file set @@optimizer_switch=@save_optimizer_switch; + +--echo # End of 10.2 tests diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 3b090093060..b8cbe02afcd 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -3687,7 +3687,8 @@ JOIN::destroy() cleanup_item_list(tmp_all_fields1); cleanup_item_list(tmp_all_fields3); destroy_sj_tmp_tables(this); - delete_dynamic(&keyuse); + delete_dynamic(&keyuse); + delete_dynamic(&ref_keyuse_steps); delete procedure; DBUG_RETURN(error); } @@ -7064,6 +7065,14 @@ choose_plan(JOIN *join, table_map join_tables) reset_nj_counters(join, join->join_list); qsort2_cmp jtab_sort_func; + if (!join->ref_keyuse_steps.buffer && + my_init_dynamic_array2(&join->ref_keyuse_steps, sizeof(uint16), + join->thd->alloc(sizeof(uint16) * MAX_REF_PARTS), + MAX_REF_PARTS, 64, + MYF(MY_THREAD_SPECIFIC))) + DBUG_RETURN(TRUE); + + if (join->emb_sjm_nest) { /* We're optimizing semi-join materialization nest, so put the @@ -7793,16 +7802,15 @@ double JOIN::get_examined_rows() @param s The table to be joined for evaluation @param rem_tables The bitmap of tables to be joined later @param keyparts The number of key parts to used when joining s - @param ref_keyuse_steps Array of references to keyuses employed to join s */ static double table_multi_eq_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, - table_map rem_tables, uint keyparts, - uint16 *ref_keyuse_steps) + table_map rem_tables, uint keyparts) { double sel= 1.0; COND_EQUAL *cond_equal= join->cond_equal; + DYNAMIC_ARRAY *ref_keyuse_steps= &join->ref_keyuse_steps; if (!cond_equal || !cond_equal->current_level.elements) return sel; @@ -7846,7 +7854,10 @@ double table_multi_eq_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, for (i= 0; i < keyparts; i++) { if (i > 0) - keyuse+= ref_keyuse_steps[i-1]; + { + uint16 *diff= dynamic_element(ref_keyuse_steps, i-1, uint16*); + keyuse+= (*diff); + } uint fldno; if (is_hash_join_key_no(key)) fldno= keyuse->keypart; @@ -7870,7 +7881,10 @@ double table_multi_eq_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, for (uint j= 0; j < keyparts && adjust_sel; j++) { if (j > 0) - keyuse+= ref_keyuse_steps[j-1]; + { + uint16 *diff= dynamic_element(ref_keyuse_steps, j-1, uint16*); + keyuse+= (*diff); + } Item *ref_item= keyuse->val; if (ref_item->real_item()->type() == Item::FIELD_ITEM) { @@ -7936,7 +7950,8 @@ static double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, table_map rem_tables) { - uint16 ref_keyuse_steps[MAX_REF_PARTS - 1]; + DYNAMIC_ARRAY *ref_keyuse_steps= &join->ref_keyuse_steps; + reset_dynamic(ref_keyuse_steps); Field *field; TABLE *table= s->table; MY_BITMAP *read_set= table->read_set; @@ -8083,7 +8098,8 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, } if (keyparts > 1) { - ref_keyuse_steps[keyparts-2]= (uint16)(keyuse - prev_ref_keyuse); + uint16 diff= (uint16)(keyuse - prev_ref_keyuse); + insert_dynamic(ref_keyuse_steps, &diff); prev_ref_keyuse= keyuse; } } @@ -8135,8 +8151,7 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, } } - sel*= table_multi_eq_cond_selectivity(join, idx, s, rem_tables, - keyparts, ref_keyuse_steps); + sel*= table_multi_eq_cond_selectivity(join, idx, s, rem_tables, keyparts); return sel; } diff --git a/sql/sql_select.h b/sql/sql_select.h index 4584460ca3f..da4a5d6abab 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1408,6 +1408,10 @@ class JOIN :public Sql_alloc bool group_sent; JOIN_TAB *sort_and_group_aggr_tab; + /* + Array of references to keyuses employed to join a table + */ + DYNAMIC_ARRAY ref_keyuse_steps; JOIN(THD *thd_arg, List<Item> &fields_arg, ulonglong select_options_arg, select_result *result_arg) @@ -1497,6 +1501,7 @@ class JOIN :public Sql_alloc emb_sjm_nest= NULL; sjm_lookup_tables= 0; sjm_scan_tables= 0; + bzero((char*) &ref_keyuse_steps, sizeof(ref_keyuse_steps)); } /* True if the plan guarantees that it will be returned zero or one row */