MySQL Bugs: #39918: memory (heap) engine crashing with b-tree index and DELETE with seg fault

Bug #39918	memory (heap) engine crashing with b-tree index and DELETE with seg fault
Submitted:	7 Oct 2008 22:59	Modified:	25 Jun 2009 22:28
Reporter:	r b	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Memory storage engine	Severity:	S2 (Serious)
Version:	5.0.67, 5.1.30-bzr	OS:	Any
Assigned to:	Anurag Shekhar	CPU Architecture:	Any
Tags:	memory engine heap delete join crash

Description:
we are seeing a segment fault error when issuing a delete with a join on an in memory table that has a b-tree on it.

Valgrind is indicating that we are referencing memory in the b-tree that has been deallocated. This occurs on both 5.0.33 and 5.0.67

How to repeat:
CREATE TABLE dupe_ids
(
  object_id BIGINT UNSIGNED NOT NULL,
  field_id INT UNSIGNED,
  PRIMARY KEY USING BTREE (object_id, field_id)
) ENGINE = Memory;

CREATE TABLE data
(
  id INT UNSIGNED NOT NULL AUTO_INCREMENT,
  object_id VARBINARY(1024) NOT NULL,
  field_id INT UNSIGNED,
  value VARBINARY(1024),
  PRIMARY KEY USING BTREE (id)
) ENGINE = Memory;

CREATE INDEX data_x1 USING BTREE ON data (object_id, field_id);

delete from data;
delete from dupe_ids;

insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa1");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa2");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa3");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa4");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa5");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa6");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa7");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa8");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa9");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa10");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa11");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa12");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa13");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa14");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa15");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa16");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa17");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa18");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa19");
insert data (object_id, field_id, value) values (1,1,"");
insert data (object_id, field_id, value) values (1,1,"aaa20");

insert dupe_ids(object_id, field_id) select object_id, field_id from data group by object_id, field_id having count(*) > 1;

delete a1 from dupe_ids as t straight_join data as a1 straight_join data as a2 on 
(t.object_id = a1.object_id) and (t.field_id = a1.field_id) and 
(a1.object_id = a2.object_id) and (a1.field_id = a2.field_id) and 
((a1.value = a2.value) OR (a1.value IS NULL AND a2.value IS NULL)) and 
(a1.id > a2.id);
 

Valgrind data...
==13291== Invalid read of size 4
==13291==    at 0x8372F00: tree_search_next (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x83669C9: heap_rnext (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8201B27: ha_heap::index_next(char*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x82004FF: handler::index_next_same(char*, char const*, unsigned) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81B3B61: join_read_next_same(st_read_record*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A550E: sub_select(JOIN*, st_join_table*, bool) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81ABBE3: evaluate_join_record(JOIN*, st_join_table*, int, char*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A5519: sub_select(JOIN*, st_join_table*, bool) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81AB8B8: do_select(JOIN*, List<Item>*, st_table*, Procedure*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A15F1: JOIN::exec() (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A2098: mysql_select(THD*, Item***, st_table_list*, unsigned, List<Item>&, Item*, unsigned, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81766D7: mysql_execute_command(THD*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81793B1: mysql_parse(THD*, char*, unsigned) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81712F5: dispatch_command(enum_server_command, THD*, char*, unsigned) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8170E04: do_command(THD*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8170475: handle_one_connection (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x405FDD7: start_thread (in /lib/tls/libpthread-0.60.so)
==13291==    by 0x4267D19: clone (in /lib/tls/libc-2.3.2.so)
==13291==  Address 0x5e76f5c is 4 bytes inside a block of size 23 free'd
==13291==    at 0x401B601: free (vg_replace_malloc.c:323)
==13291==    by 0x837284E: tree_delete (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x83660EF: hp_rb_delete_key (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8365DE5: heap_delete (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x82019D7: ha_heap::delete_row(char const*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81CA4DA: multi_delete::send_data(List<Item>&) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81AC3E6: end_send(JOIN*, st_join_table*, bool) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81ABBE3: evaluate_join_record(JOIN*, st_join_table*, int, char*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A5519: sub_select(JOIN*, st_join_table*, bool) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81ABBE3: evaluate_join_record(JOIN*, st_join_table*, int, char*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A5519: sub_select(JOIN*, st_join_table*, bool) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81AB8B8: do_select(JOIN*, List<Item>*, st_table*, Procedure*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A15F1: JOIN::exec() (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81A2098: mysql_select(THD*, Item***, st_table_list*, unsigned, List<Item>&, Item*, unsigned, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81766D7: mysql_execute_command(THD*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81793B1: mysql_parse(THD*, char*, unsigned) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x81712F5: dispatch_command(enum_server_command, THD*, char*, unsigned) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8170E04: do_command(THD*) (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x8170475: handle_one_connection (in /workplace2/mysql-5.0/libexec/mysqld)
==13291==    by 0x405FDD7: start_thread (in /lib/tls/libpthread-0.60.so)
==13291==    by 0x4267D19: clone (in /lib/tls/libc-2.3.2.so)

NOTE: on 5.0.67 you have to use a tool like Valgrind to see that freed memory is beign accessed in the b-tree index

Thank you for a bug report. The crash is easily repeatable with -debug binaries of recent 5.1.30 from bzr also:

openxs@suse:/home2/openxs/dbs/5.1> bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.30-debug Source distribution

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

mysql> CREATE TABLE dupe_ids
    -> (
    ->   object_id BIGINT UNSIGNED NOT NULL,
    ->   field_id INT UNSIGNED,
    ->   PRIMARY KEY USING BTREE (object_id, field_id)
    -> ) ENGINE = Memory;
Query OK, 0 rows affected (0.04 sec)

mysql> CREATE TABLE data
    -> (
    ->   id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    ->   object_id VARBINARY(1024) NOT NULL,
    ->   field_id INT UNSIGNED,
    ->   value VARBINARY(1024),
    ->   PRIMARY KEY USING BTREE (id)
    -> ) ENGINE = Memory;
Query OK, 0 rows affected (0.02 sec)

mysql> CREATE INDEX data_x1 USING BTREE ON data (object_id, field_id);
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> delete from data;
Query OK, 0 rows affected (0.00 sec)

mysql> delete from dupe_ids;
Query OK, 0 rows affected (0.00 sec)

mysql> insert data (object_id, field_id, value) values (1,1,"");
Query OK, 1 row affected (0.00 sec)

mysql> insert data (object_id, field_id, value) values (1,1,"aaa1");
Query OK, 1 row affected (0.00 sec)

...

mysql> insert data (object_id, field_id, value) values (1,1,"aaa20");
Query OK, 1 row affected (0.00 sec)

mysql> insert dupe_ids(object_id, field_id) select object_id, field_id from data group by
    -> object_id, field_id having count(*) > 1;
Query OK, 1 row affected (0.02 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql> delete a1 from dupe_ids as t straight_join data as a1 straight_join data as a2 on
    -> (t.object_id = a1.object_id) and (t.field_id = a1.field_id) and
    -> (a1.object_id = a2.object_id) and (a1.field_id = a2.field_id) and
    -> ((a1.value = a2.value) OR (a1.value IS NULL AND a2.value IS NULL)) and
    -> (a1.id > a2.id);
ERROR 2013 (HY000): Lost connection to MySQL server during query
mysql> 080911 15:03:09 mysqld_safe Number of processes running now: 0
080911 15:03:09 mysqld_safe mysqld restarted

An easier to debug test case:
CREATE TABLE t1(a INT, KEY USING BTREE (a)) ENGINE=MEMORY;
INSERT INTO t1 VALUES(1),(1);
DELETE a1 FROM t1 AS a1, t1 AS a2 WHERE a1.a=a2.a;
DROP TABLE t1;

The problem seem to be around heap_rnext(), which is attempting to use deleted by another handler instance key.

Fix for BUG#30590 may give some hints.

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/65097

2768 Anurag Shekhar	2009-02-04
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE with seg fault
      
      While evaluating self join with delete server uses two instance of handler 
      (with both holding reference to same file). During query evaluation last_pos 
      is cached in handler to improve search performance. But in the mean while 
      second handler is used to delete the node last_pos is holding. This makes 
      the last_pos an invalid and when accessed results in segmentation fault.
      
      To fix this I have introduced a new variable in HP_INFO structure (deleted) 
      which remembers the number of deleted (initialized while opening the file) 
      nodes since last_pos is updated. If this value differs from the value of 
      deleted nodes in shared structure last_pos is invalidated (set to zero).

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/67523

2818 Anurag Shekhar	2009-02-25
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE with seg fault
            
      While evaluating self join with delete server uses two instance of handler 
      (with both holding reference to same file). During query evaluation last_pos 
      is cached in handler to improve search performance. But in the mean while 
      second handler is used to delete the node last_pos is holding. This makes 
      the last_pos an invalid and when accessed results in segmentation faut.
      
      To fix this problem disabled delete while scanning if the table appears in
      join list.

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/67819

2827 Anurag Shekhar	2009-02-27
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE with seg fault
                  
      While evaluating self join with delete server uses two instance of handler 
      (with both holding reference to same file). During query evaluation last_pos 
      is cached in handler to improve search performance. But in the mean while 
      second handler is used to delete the node last_pos is holding. This makes 
      the last_pos an invalid and when accessed results in segmentation faut.
            
      To fix this problem disabled delete while scanning if the table appears in
      join list.

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/71009

2720 Anurag Shekhar	2009-04-01
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE with seg fault
                
      While evaluating self join with delete server uses two instance of handler 
      (with both holding reference to same file). During query evaluation last_pos 
      is cached in handler to improve search performance. But in the mean while 
      second handler is used to delete the node last_pos is holding. This makes 
      the last_pos an invalid and when accessed results in segmentation faut.
          
      To fix this problem disabled delete while scanning if the table appears in
      join list.
      modified:
        mysql-test/r/heap_btree.result
        mysql-test/t/heap_btree.test
        sql/sql_delete.cc

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/72125

2725 Anurag Shekhar	2009-04-15
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE with seg fault
      
      While evaluating self join with delete server uses two instance of handler 
      (with both holding reference to same file). During query evaluation last_pos 
      is cached in handler to improve search performance. But in the mean while 
      second handler is used to delete the node last_pos is holding. This makes 
      the last_pos an invalid and when accessed results in segmentation fault.
      
      To fix this problem disabled delete while scanning if the table appears in
      join list.
     @ mysql-test/r/heap_btree.result
        Updated test result after adding new test for this bug.
     @ mysql-test/t/heap_btree.test
        Added a new test based on the bug.
     @ sql/sql_delete.cc
        Updated to check if the files in delete list appears in join list and disable 
        delete while scanning, if it appears.

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/72878

2735 Anurag Shekhar	2009-04-28
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE 
                 with seg fault
      
      While evaluating self join with delete, server uses two instances of handler 
      (with both holding reference to same file). One handler is used to scan
      and the other handler to remove the the records. There is no way for the
      handler to know that tree its using is modified and hence needs to be rescaned.
      
      In this particular case this value in last_pos holding a wrong value 
      causing a segmentation fault when accessed. 
      
      Disabling delete and scan in parallel on the same table fixes this problem.
     @ mysql-test/r/heap_btree.result
        Updated test result after adding new test for this bug.
     @ mysql-test/t/heap_btree.test
        Updated test result after adding new test for the bug report.
     @ sql/sql_delete.cc
        Updated to check if the files in delete list appears in join list and disable 
        delete while scanning, if it appears.

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/73459

2734 Anurag Shekhar	2009-05-06
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE 
                 with seg fault
      
      Multiple-table DELETE from a table joined to itself may cause
      server crash. This was originally discovered with MEMORY engine,
      but may affect other engines with different symptoms.
      
      The problem was that the server violated SE API by performing
      parallel table scan in one handler and removing records in
      another (delete on the fly optimization).
      
      Fixed by falling back to slow (safe) delete when we detect a
      table joined to itself.
     @ mysql-test/r/heap_btree.result
        Updated test result after adding new test for this bug.
     @ mysql-test/t/heap_btree.test
        Updated test result after adding new test for the bug report.
     @ sql/sql_delete.cc
        Updated to check if the files in delete list appears in join list and disable 
        delete while scanning, if it appears.

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/73460

2734 Anurag Shekhar	2009-05-06
      Bug #39918 memory (heap) engine crashing with b-tree index and DELETE 
               with seg fault
      
      Multiple-table DELETE from a table joined to itself may cause
      server crash. This was originally discovered with MEMORY engine,
      but may affect other engines with different symptoms.
      
      The problem was that the server violated SE API by performing
      parallel table scan in one handler and removing records in
      another (delete on the fly optimization).
     @ mysql-test/r/heap_btree.result
        Updated test result after adding new test for this bug.
     @ mysql-test/t/heap_btree.test
        Updated test result after adding new test for the bug report.
     @ sql/sql_delete.cc
        Updated to check if the files in delete list appears in join list and disable 
        delete while scanning, if it appears.

Pushed into 5.0.83 (revid:joro@sun.com-20090528073529-q9b8s60vlpu28fny) (version source revid:anurag.shekhar@sun.com-20090506092910-49d3ueosvl8skwtf) (merge vers: 5.0.82) (pib:6)

Pushed into 5.1.36 (revid:joro@sun.com-20090528073639-yohsb4q1jzg7ycws) (version source revid:mats@sun.com-20090511132802-nnkiyb2huih1tklz) (merge vers: 5.1.35) (pib:6)

Noted in 5.0.83, 5.1.36 changelogs.

A multiple-table DELETE involving a table self-join could cause a
server crash. 

Setting report to NDI pending push into 6.0.x.

Pushed into 5.4.4-alpha (revid:alik@sun.com-20090616183122-chjzbaa30qopdra9) (version source revid:bernt.johnsen@sun.com-20090506113734-alfdyz13gh13z717) (merge vers: 6.0.12-alpha) (pib:11)

Noted in 5.4.4 changelog.

Noted in 5.4.2 changelog because next 5.4 version will be 5.4.2 and not 5.4.4.

Ignore previous comment about 5.4.2.

Pushed into 5.1.37-ndb-7.0.8 (revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)

Pushed into 5.1.37-ndb-6.3.27 (revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (version source revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (merge vers: 5.1.37-ndb-6.3.27) (pib:11)

Pushed into 5.1.37-ndb-6.2.19 (revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (version source revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (merge vers: 5.1.37-ndb-6.2.19) (pib:11)

Pushed into 5.1.35-ndb-7.1.0 (revid:magnus.blaudd@sun.com-20090827163030-6o3kk6r2oua159hr) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)

The 5.4 fix has been pushed to 5.4.2.