MySQL Bugs: #37943: Reproducible mysqld crash/sigsegv in sel_trees_can_be

Bug #37943	Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
Submitted:	7 Jul 2008 18:39	Modified:	18 Oct 2008 15:22
Reporter:	Erik Smit	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S1 (Critical)
Version:	5.0.51, 5.0.62	OS:	Any
Assigned to:	Georgi Kodinov	CPU Architecture:	Any
Tags:	regression

Description:
Building this table and running this query crashes the mysqld.

gdb says:

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 1945418672 (LWP 4326)]
0x082579ff in sel_trees_can_be_ored ()
(gdb) bt
#0  0x082579ff in sel_trees_can_be_ored ()
#1  0x082600cd in SEL_IMERGE::or_sel_tree_with_checks ()
#2  0x0826014f in imerge_list_or_tree ()
#3  0x0825fdb8 in SEL_ARG::clone_tree ()
#4  0x08261407 in imerge_list_or_list ()
#5  0x08262c02 in SQL_SELECT::test_quick_select ()
#6  0x0821a016 in st_table_list::print ()
#7  0x0821aea8 in JOIN::optimize ()
#8  0x08222129 in mysql_select ()
#9  0x08222913 in mysql_explain_union ()
#10 0x081da0d9 in mysql_execute_command ()
#11 0x081dbbd7 in mysql_parse ()
#12 0x081dc090 in dispatch_command ()
#13 0x081dd358 in do_command ()
#14 0x081ddd64 in handle_one_connection ()
#15 0x77ef60bd in start_thread () from /lib/tls/libpthread.so.0
#16 0x77d3101e in clone () from /lib/tls/libc.so.6
(gdb)

mysql says:
Version: '5.0.51a-community'  socket: '/var/lib/mysql/mysql.sock'  port: 3306  MySQL Community Edition (GPL)
080707 20:35:37 - mysqld got signal 11;
This could be because you hit a bug. It is also possible that this binary
or one of the libraries it was linked against is corrupt, improperly built,
or misconfigured. This error can also be caused by malfunctioning hardware.
We will try our best to scrape up some info that will hopefully help diagnose
the problem, but since we have already crashed, something is definitely wrong
and this may fail.

key_buffer_size=8388600
read_buffer_size=131072
max_used_connections=1
max_connections=100
threads_connected=1
It is possible that mysqld could use up to
key_buffer_size + (read_buffer_size + sort_buffer_size)*max_connections = 225791 K
bytes of memory
Hope that's ok; if not, decrease some variables in the equation.

thd=0xfe57e70
Attempting backtrace. You can use the following information to find out
where mysqld died. If you see no messages after this, something went
terribly wrong...
Cannot determine thread, fp=0x45088fc0, backtrace may not be correct.
Stack range sanity check OK, backtrace follows:
(nil)
New value of fp=0xfe57e70 failed sanity check, terminating stack trace!
Please read http://dev.mysql.com/doc/mysql/en/using-stack-trace.html and follow instructions on how to resolve the stack trace. Resolved
stack trace is much more helpful in diagnosing the problem, so please do
resolve it
Trying to get some variables.
Some pointers may be invalid and cause the dump to abort...
thd->query at 0xfe95b60 = describe SELECT see,circleCode from ftopic WHERE ((ftopic.see!='group' && ftopic.see!='igroup' && ftopic.see!='szg') || (ftopic.circleCode='pure-S') || (ftopic.see='icircl
e') || (ftopic.circleCode='DE80337a') || (ftopic.circleCode='DE80799'))
thd->thread_id=5
The manual page at http://www.mysql.com/doc/en/Crashing.html contains
information that should help you find out what is causing the crash.

I've tested it with 5.0.32-Debian_7etch5 on i386 and various versions of 5.0.51a-community on amd64.

It does not crash with 4.1.11.

How to repeat:
[root@testdoos ~]# cat ftopic.sql
CREATE TABLE `ftopic` (
  `circleCode` varchar(8) NOT NULL default '',
  `see` set('circle','cadmin','group','gadmin','icircle','igroup','szadmin','szg') NOT NULL default '',
  KEY `see` (`see`),
  KEY `circleCode` (`circleCode`)
);
INSERT INTO `ftopic` VALUES ('','');
INSERT INTO `ftopic` VALUES ('','');
[root@testdoos ~]# cat crash.sql
describe SELECT see,circleCode from ftopic WHERE ((ftopic.see!='group' && ftopic.see!='igroup' && ftopic.see!='szg') || (ftopic.circleCode='pure-S') || (ftopic.see='icircle') || (ftopic.circleCode='DE80337a') || (ftopic.circleCode='DE80799'));
[root@testdoos ~]# mysqladmin create foo
[root@testdoos ~]# mysql foo < ftopic.sql
[root@testdoos ~]# mysql foo < crash.sql
ERROR 2013 (HY000) at line 1: Lost connection to MySQL server during query
[root@testdoos ~]#

This is reproducable in Ubuntu en Gentoo as well with the default package/ebuild.

Ubuntu:
Server version: 5.0.51a-3ubuntu5.1 (Ubuntu)

Gentoo:
Server version: 5.0.54-log Gentoo Linux mysql-5.0.54

Thank you for a bug report. Verified just as described also with 5.0.62 on Windows. Stack trace is:

 	mysqld-nt.exe!sel_trees_can_be_ored(SEL_TREE * tree1=0xfd5c0cf8, SEL_TREE * tree2=0x00000002, st_qsel_param * param=0x054acc88)  Line 4733 + 0x3f bytes	C++
 	mysqld-nt.exe!SEL_IMERGE::or_sel_tree_with_checks(st_qsel_param * param=0x054acc88, SEL_TREE * new_tree=0x0450e660)  Line 726 + 0xe bytes	C++
 	mysqld-nt.exe!imerge_list_or_tree(st_qsel_param * param=0x054acc88, List<SEL_IMERGE> * im1=0x01aceb20, SEL_TREE * tree=0x0450e660)  Line 828 + 0xb bytes	C++
 	mysqld-nt.exe!tree_or(st_qsel_param * param=0x054acc88, SEL_TREE * tree1=0x01acea10, SEL_TREE * tree2=0x0450e660)  Line 4804 + 0xe bytes	C++
 	mysqld-nt.exe!get_mm_tree(st_qsel_param * param=0x054acc88, Item * cond=0x01ac7a28)  Line 4063 + 0x8 bytes	C++
 	mysqld-nt.exe!SQL_SELECT::test_quick_select(THD * thd=0x01aa99b8, Bitmap<64> keys_to_use={...}, unsigned __int64 prev_tables=0, unsigned __int64 limit=18446744073709551615, bool force_quick_range=false)  Line 2075 + 0xb bytes	C++
 	mysqld-nt.exe!get_quick_record_count(THD * thd=0x01aa99b8, SQL_SELECT * select=0x00000000, st_table * table=0x00000000, const Bitmap<64> * keys=0x054aee78, unsigned __int64 limit=18446744073709551615)  Line 2322 + 0x2e bytes	C++
 	mysqld-nt.exe!make_join_statistics(JOIN * join=0x04508000, TABLE_LIST * tables=0x00000000, Item * conds=0x01ac7a28, st_dynamic_array * keyuse_array=0x04508d2c)  Line 2719	C++
 	mysqld-nt.exe!JOIN::optimize()  Line 903 + 0x21 bytes	C++
 	mysqld-nt.exe!mysql_select(THD * thd=0x01aa99b8, Item * * * rref_pointer_array=0x01aaa978, TABLE_LIST * tables=0x01ac6fc0, unsigned int wild_num=0, List<Item> & fields={...}, Item * conds=0x01ac7a28, unsigned int og_num=0, st_order * order=0x00000000, st_order * group=0x00000000, Item * having=0x00000000, st_order * proc_param=0x00000000, unsigned __int64 select_options=2156153348, select_result * result=0x01ac8150, st_select_lex_unit * unit=0x01aaa608, st_select_lex * select_lex=0x01aaa850)  Line 2259 + 0x7 bytes	C++
 	mysqld-nt.exe!mysql_explain_union(THD * thd=0x01aa99b8, st_select_lex_unit * unit=0x01aaa608, select_result * result=0x01ac8150)  Line 15526 + 0x70 bytes	C++
 	mysqld-nt.exe!mysql_execute_command(THD * thd=0x01aa99b8)  Line 2702 + 0xe bytes	C++
 	mysqld-nt.exe!mysql_parse(THD * thd=0x01aa99b8, const char * inBuf=0x01ac6d10, unsigned int length=242, const char * * found_semicolon=0x054afb64)  Line 6174	C++
 	mysqld-nt.exe!dispatch_command(enum_server_command command=COM_QUERY, THD * thd=0x01aa99b8, char * packet=0x045145c9, unsigned int packet_length=243)  Line 1877	C++
 	mysqld-nt.exe!do_command(THD * thd=0x00000000)  Line 1581 + 0xe bytes	C++
 	mysqld-nt.exe!handle_one_connection(void * arg=0x01aa99b8)  Line 1187 + 0x9 bytes	C++
 	mysqld-nt.exe!pthread_start(void * param=0x01aa96d8)  Line 85 + 0x3 bytes	C
>	mysqld-nt.exe!_threadstart(void * ptd=0x01aaaf08)  Line 196 + 0x6 bytes	C

Does not crash on 5.1.25-rc:

C:\Program Files\MySQL\MySQL Server 5.0\bin>mysql -uroot -proot -P3310 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 4
Server version: 5.1.25-rc-community MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> CREATE TABLE `ftopic` (
    ->   `circleCode` varchar(8) NOT NULL default '',
    ->   `see` set('circle','cadmin','group','gadmin','icircle','igroup','szadmi
n','szg') NOT
    -> NULL default '',
    ->   KEY `see` (`see`),
    ->   KEY `circleCode` (`circleCode`)
    -> );
Query OK, 0 rows affected (0.22 sec)

mysql> INSERT INTO `ftopic` VALUES ('','');
Query OK, 1 row affected (0.05 sec)

mysql> INSERT INTO `ftopic` VALUES ('','');
Query OK, 1 row affected (0.03 sec)

mysql> describe SELECT see,circleCode from ftopic WHERE ((ftopic.see!='group' &&

    -> ftopic.see!='igroup' && ftopic.see!='szg') || (ftopic.circleCode='pure-S'
) ||
    -> (ftopic.see='icircle') || (ftopic.circleCode='DE80337a') ||
    -> (ftopic.circleCode='DE80799'));
+----+-------------+--------+------+----------------+------+---------+------+---
---+-------------+
| id | select_type | table  | type | possible_keys  | key  | key_len | ref  | ro
ws | Extra       |
+----+-------------+--------+------+----------------+------+---------+------+---
---+-------------+
|  1 | SIMPLE      | ftopic | ALL  | see,circleCode | NULL | NULL    | NULL |
 2 | Using where |
+----+-------------+--------+------+----------------+------+---------+------+---
---+-------------+
1 row in set (0.44 sec)

Does no crash on 4.1.22, so this is a regression in 5.0.x, fixed in current 5.1.x.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/49758

2648 Georgi Kodinov	2008-07-15
      Bug#37943 : Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
      
      A tree can mention a key and have no key test (e.g. it's an OR tree).
      So we need to check if there's a key test before using it in 
      sel_tree_can_be_ored.

Here're the mechanics of the problem:

1. Data:
- The condition is  (b!='c' AND b!='f' AND b!='h') OR (a='pure-S') OR (a='DE80337a') OR (a='DE80799')
- note that b is an enum column.

2. Steps and structures built:
a) b!='c' : this makes is converted by get_ne_mm_tree() to :
    b < 'c' OR b > 'c'
   But because b is an enum column and Field_enum::optimize_range() returns 0, the get_mm_leaf() function returns 0 and this causes an empty KEY tree (no SEL_TREE::merges and no SEL_TREE::keys) to be created by get_mm_parts().
   Then the two empty trees from the above OR get merged by get_ne_mm_tree() call to tree_or() and as a result we have a SEL_TREE with 1 merge and 2 empty trees in it.

b) for the other two parts of the AND (AND b!='f' AND b!='h') it makes two more SEL_IMERGEs containing 2 empty KEY trees each and adds these to the master SEL_TREE created in a).
So for the first part of the top-most OR (b!='c' AND b!='f' AND b!='h') we have :
   SEL_TREE1
    keys = { 0, 0, ...})
    merges
      |---SEL_IMERGE1
      |     |---SEL_TREE2(empty)
      |     |---SEL_TREE3(empty)
      |
      |---SEL_IMERGE2
      |     |---SEL_TREE4(empty)
      |     |---SEL_TREE5(empty)
      |
      |---SEL_IMERGE3
            |---SEL_TREE6(empty)
            |---SEL_TREE7(empty)

 c) we start adding (a='pure-S') : this results in a TREE (SEL_TREE8) with a SEL_TREE::keys[1] set, a proper bitmask in SEL_TREE::keys_map and no merges.
 d) We call tree_or(SEL_TREE1, SEL_TREE8). This results in a call to imerge_list_or_tree(). As a result we have :

   SEL_TREE1
    keys = { 0, 0, ...})
    merges
      |---SEL_IMERGE1
      |     |---SEL_TREE2(empty)
      |     |---SEL_TREE3(empty)
      |     |---SEL_TREE8(keys[1])
      |
      |---SEL_IMERGE2
      |     |---SEL_TREE4(empty)
      |     |---SEL_TREE5(empty)
      |     |---SEL_TREE8(keys[1])
      |
      |---SEL_IMERGE3
            |---SEL_TREE6(empty)
            |---SEL_TREE7(empty)
            |---SEL_TREE8(keys[1])

 Note how SEL_TREE8 repeats itself in all the SEL_IMERGEs.

 c) we start adding (a='DE80337a') : this results in a TREE (SEL_TREE9) with a SEL_TREE::keys[1] set, a proper bitmask in SEL_TREE::keys_map and no merges.
 e) We call tree_or(SEL_TREE1, SEL_TREE9). This again results in a call to imerge_list_or_tree(). This effectively results in calling
   SEL_IMERGE1.trees[3] = tree_or(SEL_TREE8, SEL_TREE9)
   This call replaces the keys[1] of SEL_TREE8 with keys[1] of SEL_TREE9.
 f) But then we call SEL_IMERGE2.trees[3] = tree_or(SEL_TREE8, SEL_TREE9)
   But since SEL_TREE8.keys[1] is already updated to point to SEL_TREE9.keys[1] we have identical pointer on both arguments of key_or(). This results in a series of unfortunate events (e.g. SEL_ARG::use_count underflowing etc).

3. Proposed solution :

 The most natural solution that comes to mind is to code a copy constructor for SEL_TREE and call it in imerge_list_or_tree(). But this would mean creating copy constructor for SEL_IMERGE as well. SEL_ARG already has a copy constructor.

Here's the fix : http://lists.mysql.com/commits/50807

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/52215

2648 Georgi Kodinov	2008-08-21
      Bug#37943: Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
      
      When analyzing the possible index use cases the server was re-using an internal structure.
      This is wrong, as this internal structure gets updated during the analysis.
      Fixed by making a copy of the internal structure for every place it needs to be used.
      Also stopped the generation of empty structures that unnecessary complicate the analysis.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/54745

2648 Georgi Kodinov	2008-09-30
      Bug#37943: Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
            
      When analyzing the possible index use cases the server was re-using an internal structure.
      This is wrong, as this internal structure gets updated during the analysis.
      Fixed by making a copy of the internal structure for every place it needs to be used.
      Also stopped the generation of empty SEL_TREE structures that unnecessary 
      complicate the analysis.

Ok to push after the last portion of review feedback (http://lists.mysql.com/commits/54957) is addressed.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/54963

2692 Georgi Kodinov	2008-10-01
      Bug#37943: Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
                  
      When analyzing the possible index use cases the server was re-using an internal structure.
      This is wrong, as this internal structure gets updated during the analysis.
      Fixed by making a copy of the internal structure for every place it needs to be used.
      Also stopped the generation of empty SEL_TREE structures that unnecessary 
      complicate the analysis.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/54966

2756 Georgi Kodinov	2008-10-01 [merge]
      merge of bug #37943 5.0-bugteam -> 5.1-bugteam

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/54968

2692 Georgi Kodinov	2008-10-01
      Bug#37943: Reproducible mysqld crash/sigsegv in sel_trees_can_be_ored
                  
      When analyzing the possible index use cases the server was re-using an internal structure.
      This is wrong, as this internal structure gets updated during the analysis.
      Fixed by making a copy of the internal structure for every place it needs to be used.
      Also stopped the generation of empty SEL_TREE structures that unnecessary 
      complicate the analysis.

Pushed into 5.0.72  (revid:kgeorge@mysql.com-20081001155055-2tk19u3pk36yb52l) (version source revid:kgeorge@mysql.com-20081001155055-2tk19u3pk36yb52l) (pib:4)

Pushed into 5.1.30  (revid:kgeorge@mysql.com-20081001164959-aw5ehtedauy8nlj4) (version source revid:mats@sun.com-20081008113713-2vxny72m5w1tywoi) (pib:4)

This is actually pushed to 5.1.29, not 5.1.30.

Pushed into 6.0.8-alpha  (revid:kgeorge@mysql.com-20081001164959-aw5ehtedauy8nlj4) (version source revid:sergey.glukhov@sun.com-20081002111648-n45momm93739j51y) (pib:5)

Noted in 5.0.72, 5.1.29, 6.0.8 changelogs.

When analyzing the possible index use cases, the server was
incorrectly reusing an internal structure, leading to a server crash.

Pushed into 5.1.29-ndb-6.2.17  (revid:kgeorge@mysql.com-20081001164959-aw5ehtedauy8nlj4) (version source revid:tomas.ulin@sun.com-20081028140209-u4emkk1xphi5tkfb) (pib:5)

Pushed into 5.1.29-ndb-6.3.19  (revid:kgeorge@mysql.com-20081001164959-aw5ehtedauy8nlj4) (version source revid:tomas.ulin@sun.com-20081028194045-0353yg8cvd2c7dd1) (pib:5)

Pushed into 5.1.29-ndb-6.4.0  (revid:kgeorge@mysql.com-20081001164959-aw5ehtedauy8nlj4) (version source revid:jonas@mysql.com-20081101082305-qx5a1bj0z7i8ueys) (pib:5)