MySQL Bugs: #38296: low memory crash with many conditions in a query

Bug #38296	low memory crash with many conditions in a query
Submitted:	22 Jul 2008 19:43	Modified:	22 Aug 2008 20:32
Reporter:	Shane Bester (Platinum Quality Contributor)	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Parser	Severity:	S2 (Serious)
Version:	4.1.22, 5.0.68, 5.1.28	OS:	Any
Assigned to:	Marc ALFF	CPU Architecture:	Any

Description:
for queries such as select .. from .. where ..or (.. or (.. or ..( or .. )))
with hundreds or thousands of (nested) terms, the parser crashes:

mysqld-nt.exe!is_cond_or(Item * item=0x00000000) 
mysqld-nt.exe!MYSQLparse
mysqld-nt.exe!mysql_parse
mysqld-nt.exe!dispatch_command
mysqld-nt.exe!do_command
mysqld-nt.exe!handle_one_connection
mysqld-nt.exe!pthread_start
mysqld-nt.exe!_threadstart
kernel32.dll!FlsSetValue

and another similar crash;

#3930  Item_cond::neg_arguments ()
#3931  Item_cond_or::neg_transformer ()
#3932  Item_cond::neg_arguments ()
#3933  Item_cond_or::neg_transformer ()
#3934  negate_expression ()
#3935  yyparse ()
#3936  mysql_parse ()
#3937  dispatch_command ()
#3938  do_command ()
#3939  handle_one_connection ()
#3940  start_thread () from /lib64/tls/libpthread.so.0
#3941  getsockopt () from /lib64/tls/libc.so.6
#3942  ?? ()

How to repeat:
for the first crash, run 32-bit mysqld server with --thread_stack=2M then run output of this php script in the mysql client:
NOTE: this testcase consumes 1.9GB of ram before crashing!

--------------

drop table if exists `t1`,`t2`;
create table `t1`(`a` int) engine=myisam;
create table `t2`(`b` int) engine=myisam;
insert into `t1` values (1),(2),(3),(4),(5),(6),(7);
insert into `t2` values (1),(2),(3),(4),(5),(6),(7);

select count(*) from `t1` left join `t2` on `a`=`b` where

<?php

$num=4600;
for($i=0;$i<$num;$i++)
{
        print "`t1`.`a` like '$i%'";
        if($i<$num-1)
                print " or not (\n";
}

for($i=0;$i<$num-1;$i++)
{
        print ")";       
}
?>;

--------------

Suggested fix:
o) don't crash
o) try consume less memory

run server --thread-stack=2M and import this into client.

Attachment: bug38296_testcase.sql (application/unknown, text), 142.93 KiB.

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

2743 Marc Alff	2008-07-30
      Bug#38296 (low memory crash with many conditions in a query)
      
      The parser code in sql/sql_yacc.yy needs to be more robust to out of
      memory conditions, so that when parsing a query fails due to OOM,
      the thread gracefully returns an error.
      
      Before this fix, a new/alloc returning NULL could:
      - cause a crash, if dereferencing the NULL pointer,
      - produce a corrupted parsed tree, containing NULL nodes,
      - alter the semantic of a query, by silently dropping token values or nodes
      
      With this fix:
      - calls to new/alloc are tested for a NULL result,
      - OOM conditions cause the parser to stop immediately (MYSQL_YYABORT)

Previous patch withdrawn: the code was correct, but the patch incomplete.
Currently testing a new patch, to be posted very soon.

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

2743 Marc Alff	2008-08-01
      Bug#38296 (low memory crash with many conditions in a query)
      
      The parser code in sql/sql_yacc.yy needs to be more robust to out of
      memory conditions, so that when parsing a query fails due to OOM,
      the thread gracefully returns an error.
      
      Before this fix, a new/alloc returning NULL could:
      - cause a crash, if dereferencing the NULL pointer,
      - produce a corrupted parsed tree, containing NULL nodes,
      - alter the semantic of a query, by silently dropping token values or nodes
      
      With this fix:
      - C++ constructors are *not* executed with a NULL "this" pointer
      when operator new fails.
      This is achieved by declaring "operator new" with a "throw ()" clause,
      so that a failed new gracefully returns NULL on OOM conditions.
      
      - calls to new/alloc are tested for a NULL result,
      
      - The thread diagnostic area is set to an error status when OOM occurs.
      This ensures that a request failing in the server properly returns an
      ER_OUT_OF_RESOURCES error to the client.
      
      - OOM conditions cause the parser to stop immediately (MYSQL_YYABORT).
      This prevents causing further crashes when using a partially built parsed
      tree in further rules in the parser.
      
      No test scripts are provided, since automating OOM failures is not
      instrumented in the server.
      Tested under the debugger, to verify that an error in alloc_root cause the
      thread to returns gracefully all the way to the client application, with
      an ER_OUT_OF_RESOURCES error.

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

2750 Chad MILLER	2008-08-07 [merge]
      Merge from 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/51209

2656 Marc Alff	2008-08-08
      Bug#38296 (low memory crash with many conditions in a query)
      
      This fix is for 5.0/5.1 only
      
      Before this fix, a query using many an arbitrary number of conditions in a
      query could consume arbitrary amount of memory in the server, and cause
      a crash in the parser on Out Of Memory condition, due to an optimization
      implemented for OR / XOR / AND operators.
      
      With this fix, the parser now gracefully returns an ER_OUT_OF_RESOURCES
      error to the client when OOM occurs when parsing OR / XOR / AND.
      
      No test scripts are provided, since automating OOM failures is not
      instrumented in the server.
      Tested under the debugger, to verify that an error in alloc_root cause the
      thread to returns gracefully all the way to the client application, with
      an ER_OUT_OF_RESOURCES error.

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

2656 Marc Alff	2008-08-08
      Bug#38296 (low memory crash with many conditions in a query)
      
      This fix is for 5.0 only : back porting the 6.0 patch manually
      
      The parser code in sql/sql_yacc.yy needs to be more robust to out of
      memory conditions, so that when parsing a query fails due to OOM,
      the thread gracefully returns an error.
      
      Before this fix, a new/alloc returning NULL could:
      - cause a crash, if dereferencing the NULL pointer,
      - produce a corrupted parsed tree, containing NULL nodes,
      - alter the semantic of a query, by silently dropping token values or nodes
      
      With this fix:
      - C++ constructors are *not* executed with a NULL "this" pointer
      when operator new fails.
      This is achieved by declaring "operator new" with a "throw ()" clause,
      so that a failed new gracefully returns NULL on OOM conditions.
      
      - calls to new/alloc are tested for a NULL result,
      
      - The thread diagnostic area is set to an error status when OOM occurs.
      This ensures that a request failing in the server properly returns an
      ER_OUT_OF_RESOURCES error to the client.
      
      - OOM conditions cause the parser to stop immediately (MYSQL_YYABORT).
      This prevents causing further crashes when using a partially built parsed
      tree in further rules in the parser.
      
      No test scripts are provided, since automating OOM failures is not
      instrumented in the server.
      Tested under the debugger, to verify that an error in alloc_root cause the
      thread to returns gracefully all the way to the client application, with
      an ER_OUT_OF_RESOURCES error.

Have you changed all calls to overloaded operator new() that will affected by this change? Before this change, when the malloc used by overloaded operator new() failed, mysqld exits as it should per my understanding of the C++ standard. With this change, overloaded operator new() will return NULL and most calls to new() in sql/*.cc do not check for NULL on return from new().

The objects already had a placement new and they did not throw a exception (std::bad_alloc) if allocation failed. A placement new is not required to throw bad_alloc and even if we did so, it could break horribly as we compile without exceptions support.

The change made is to explicitly set a empty exception specification for those placement news so that the compiler will not perform object initialization if the placement new returns NULL.

Also the scope of this bug and fix is the parser bits. For other parts, we happily accept contributions :-)

debug binaries have an option,  --safemalloc-mem-limit so that OOM can be triggered easily. should some tests be done with this ?

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

2656 Marc Alff	2008-08-11
      Bug#38296 (low memory crash with many conditions in a query)
      
      This fix is for 5.0 only : back porting the 6.0 patch manually
      
      The parser code in sql/sql_yacc.yy needs to be more robust to out of
      memory conditions, so that when parsing a query fails due to OOM,
      the thread gracefully returns an error.
      
      Before this fix, a new/alloc returning NULL could:
      - cause a crash, if dereferencing the NULL pointer,
      - produce a corrupted parsed tree, containing NULL nodes,
      - alter the semantic of a query, by silently dropping token values or nodes
      
      With this fix:
      - C++ constructors are *not* executed with a NULL "this" pointer
      when operator new fails.
      This is achieved by declaring "operator new" with a "throw ()" clause,
      so that a failed new gracefully returns NULL on OOM conditions.
      
      - calls to new/alloc are tested for a NULL result,
      
      - The thread diagnostic area is set to an error status when OOM occurs.
      This ensures that a request failing in the server properly returns an
      ER_OUT_OF_RESOURCES error to the client.
      
      - OOM conditions cause the parser to stop immediately (MYSQL_YYABORT).
      This prevents causing further crashes when using a partially built parsed
      tree in further rules in the parser.
      
      No test scripts are provided, since automating OOM failures is not
      instrumented in the server.
      Tested under the debugger, to verify that an error in alloc_root cause the
      thread to returns gracefully all the way to the client application, with
      an ER_OUT_OF_RESOURCES error.

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

2691 Marc Alff	2008-08-11 [merge]
      Manual merge of mysql-5.0-bugteam -> mysql-5.1-bugteam
      
      Note: NULL merge of sql/sql_yacc.yy, the fix for bug#38296 will be provided separately for 5.1

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

2691 Marc Alff	2008-08-11 [merge]
      Manual merge of mysql-5.0-bugteam -> mysql-5.1-bugteam
      
      Note: NULL merge of sql/sql_yacc.yy, the fix for bug#38296 will be provided separately for 5.1

Pushed into 6.0.7-alpha  (revid:marc.alff@sun.com-20080801153805-xqbn0o2y1emnd53f) (version source revid:davi.arnaut@sun.com-20080812141852-8e6knbqclpfd8irn) (pib:3)

Pushed into 5.1.28  (revid:marc.alff@sun.com-20080811161000-qa9xdpx64pf3kj0w) (version source revid:davi.arnaut@sun.com-20080812142843-he05ncsggstbn57z) (pib:3)

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

2647 Davi Arnaut	2008-08-12 [merge]
      Merge mysql-5.0-bugteam into mysql-5.0

Pushed into 5.0.68  (revid:marc.alff@sun.com-20080811161000-qa9xdpx64pf3kj0w) (version source revid:davi.arnaut@sun.com-20080812185100-d47qb8mz2ye6pe6b) (pib:3)

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

2692 Marc Alff	2008-08-12
      Bug#38296 (low memory crash with many conditions in a query)
      
      This fix is for 5.1 only : back porting the 6.0 patch manually
      
      The parser code in sql/sql_yacc.yy needs to be more robust to out of
      memory conditions, so that when parsing a query fails due to OOM,
      the thread gracefully returns an error.
      
      Before this fix, a new/alloc returning NULL could:
      - cause a crash, if dereferencing the NULL pointer,
      - produce a corrupted parsed tree, containing NULL nodes,
      - alter the semantic of a query, by silently dropping token values or nodes
      
      With this fix:
      - C++ constructors are *not* executed with a NULL "this" pointer
      when operator new fails.
      This is achieved by declaring "operator new" with a "throw ()" clause,
      so that a failed new gracefully returns NULL on OOM conditions.
      
      - calls to new/alloc are tested for a NULL result,
      
      - The thread diagnostic area is set to an error status when OOM occurs.
      This ensures that a request failing in the server properly returns an
      ER_OUT_OF_RESOURCES error to the client.
      
      - OOM conditions cause the parser to stop immediately (MYSQL_YYABORT).
      This prevents causing further crashes when using a partially built parsed
      tree in further rules in the parser.
      
      No test scripts are provided, since automating OOM failures is not
      instrumented in the server.
      Tested under the debugger, to verify that an error in alloc_root cause the
      thread to returns gracefully all the way to the client application, with
      an ER_OUT_OF_RESOURCES error.

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

2758 Marc Alff	2008-08-13 [merge]
      Merge 5.1-bugteam -> 6.0-bugteam
      
      Manual merge of sql_yacc.yy

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

2758 Marc Alff	2008-08-13 [merge]
      Merge 5.1-bugteam -> 6.0-bugteam
      
      Manual merge of sql_yacc.yy

@Davi

> The objects already had a placement new and they did not throw a exception
> (std::bad_alloc) if allocation failed. A placement new is not required to 
> throw bad_alloc and even if we did so, it could break horribly as we compile 
> without exceptions support.

My comment was about overloaded operator new(), not placement new(). Where does MySQL use placement new (as in 'new (buf) Item(...)'?

> The change made is to explicitly set a empty exception specification for those > placement news so that the compiler will not perform object initialization if > the placement new returns NULL.

The result of this change is that Sql_alloc::new() will return NULL when sql_alloc() returns NULL. Previously this caused mysqld to immediately exit. Most callers to Sql_alloc::new() don't check for a NULL return value and the result is likely an eventual segfault with odd stuff happening before then. I prefer the immediate exit.

> Also the scope of this bug and fix is the parser bits. For other parts, we
> happily accept contributions :-)

This is not limited to the parser. This changed Sql_alloc from sql/sql_list.h. Many clases in the sql directory extend Sql_alloc, not just code from the parser.

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

2685 He Zhenxing	2008-08-14 [merge]
      Merge 5.1-rpl-testfixes -> 6.0-rpl-testfixes

Noted in 5.0.68, 6.0.7 changelogs.

The server consumed excess memory while parsing statements with
hundreds or thousands of nested boolean conditions (such as OR (OR 
... (OR ... ))). This could lead to a server crash or incorrect 
statement execution, or cause other client statements to fail due to
lack of memory. The latter result constitutes a denial of service.

Setting report to Patch Queued pending push of fix into 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/51688

2769 He Zhenxing	2008-08-15 [merge]
      Merge 6.0-rpl-testfixes -> 6.0

Pushed into 6.0.7-alpha  (revid:marc.alff@sun.com-20080811161000-qa9xdpx64pf3kj0w) (version source revid:sven@mysql.com-20080818175803-c1nutd5773r6b4gd) (pib:3)

Setting report to Patch Queued pending push of fix into 5.1.x.

Noted in 5.1.28 changelog.

Pushed into 6.0.7-alpha  (revid:cbell@mysql.com-20080822132131-uveo6wiuecy6m2b8) (version source revid:cbell@mysql.com-20080822132131-uveo6wiuecy6m2b8) (pib:3)

Pushed into 6.0.6-alpha  (revid:marc.alff@sun.com-20080801153805-xqbn0o2y1emnd53f) (version source revid:hakan@mysql.com-20080716160034-sdexuyp3qow7zlc6) (pib:3)

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

2641 Jonathan Perkin	2008-10-23
      Merge fix for bug#38296 into 5.0.66sp1

Noted in 5.0.66sp1 changelog.

Pushed into 5.0.77 (revid:joerg@mysql.com-20090115110809-bnb54922hwgrv2hk) (version source revid:joerg@mysql.com-20090115104831-o8sb30ms6qc8s8je) (merge vers: 5.0.77) (pib:6)

Pushed into 5.1.32 (revid:joerg@mysql.com-20090115181125-29qdo615v9vkla0t) (version source revid:joerg@mysql.com-20090115181125-29qdo615v9vkla0t) (merge vers: 5.1.32) (pib:6)

Pushed into 6.0.10-alpha (revid:joro@sun.com-20090119171328-2hemf2ndc1dxl0et) (version source revid:timothy.smith@sun.com-20090116165151-xtp5e4z6qsmxyvy0) (merge vers: 6.0.10-alpha) (pib:6)

Pushed into 5.1.32-ndb-6.3.23 (revid:tomas.ulin@sun.com-20090217131017-6u8qz1edkjfiobef) (version source revid:tomas.ulin@sun.com-20090203133556-9rclp06ol19bmzs4) (merge vers: 5.1.32-ndb-6.3.22) (pib:6)

Pushed into 5.1.32-ndb-6.4.3 (revid:tomas.ulin@sun.com-20090217134419-5ha6xg4dpedrbmau) (version source revid:tomas.ulin@sun.com-20090203133556-9rclp06ol19bmzs4) (merge vers: 5.1.32-ndb-6.3.22) (pib:6)

Pushed into 5.1.32-ndb-6.2.17 (revid:tomas.ulin@sun.com-20090217134216-5699eq74ws4oxa0j) (version source revid:tomas.ulin@sun.com-20090201210519-vehobc4sy3g9s38e) (merge vers: 5.1.32-ndb-6.2.17) (pib:6)