Bug 32835 - [glsl] recursive #define results in infinite stack recursion
[glsl] recursive #define results in infinite stack recursion
Product: Mesa
Classification: Unclassified
Component: glsl-compiler
All All
: medium critical
Assigned To: Ian Romanick
Depends on:
  Show dependency treegraph
Reported: 2011-01-04 16:47 UTC by Vinson Lee
Modified: 2011-04-21 17:52 UTC (History)
3 users (show)

See Also:
i915 platform:
i915 features:


Note You need to log in before you can comment on or make changes to this bug.
Description Vinson Lee 2011-01-04 16:47:13 UTC
mesa: 5a3f31575bf0657661c3e66a4c95c3298c78e441 (master)

Some forms of recursive #define result in infinite stack recursion in the preprocessor.

     1	#define A(a, b) B(a, b)
     2	#define C A(0, C)
     3	C

$ ../glcpp 095-recursive-define.c

#0  _int_free (av=<value optimized out>, p=0x893fb50) at malloc.c:4765
#1  0x00180e5d in __libc_free (mem=0x893fb58) at malloc.c:3738
#2  0x00676b60 in ?? () from /usr/lib/libtalloc.so.2
#3  0x00675851 in _talloc_free () from /usr/lib/libtalloc.so.2
#4  0x080514ce in _active_list_pop (list=0xfde2448) at glcpp/glcpp-parse.y:1506
#5  0x080516f5 in _glcpp_parser_expand_token_list (parser=0x892e0e0, list=0xfde2828) at glcpp/glcpp-parse.y:1595
#6  0x08051135 in _glcpp_parser_expand_function (parser=0x892e0e0, node=0x893ecf0, last=0xbf1ac214) at glcpp/glcpp-parse.y:1335
#7  0x08051421 in _glcpp_parser_expand_node (parser=0x892e0e0, node=0xfde2090, last=0xbf1ac214) at glcpp/glcpp-parse.y:1472
#8  0x080515b5 in _glcpp_parser_expand_token_list (parser=0x892e0e0, list=0xfde1f88) at glcpp/glcpp-parse.y:1554
#9  0x08051135 in _glcpp_parser_expand_function (parser=0x892e0e0, node=0x893eef0, last=0xbf1ac2f4) at glcpp/glcpp-parse.y:1335
#10 0x08051421 in _glcpp_parser_expand_node (parser=0x892e0e0, node=0xfde1658, last=0xbf1ac2f4) at glcpp/glcpp-parse.y:1472
#11 0x080515b5 in _glcpp_parser_expand_token_list (parser=0x892e0e0, list=0xfde1550) at glcpp/glcpp-parse.y:1554
#12 0x08051135 in _glcpp_parser_expand_function (parser=0x892e0e0, node=0x893eef0, last=0xbf1ac3d4) at glcpp/glcpp-parse.y:1335
#13 0x08051421 in _glcpp_parser_expand_node (parser=0x892e0e0, node=0xfde0c20, last=0xbf1ac3d4) at glcpp/glcpp-parse.y:1472
#14 0x080515b5 in _glcpp_parser_expand_token_list (parser=0x892e0e0, list=0xfde0b18) at glcpp/glcpp-parse.y:1554
Comment 1 Ian Romanick 2011-01-10 13:25:51 UTC
My guess is that glcpp is adding C to the symbol table while C is being defined.  This cause it to try to expand the occurrence of C inside the definition of C.  If this is the case, it should be possible to move the addition of a macro name to the symbol table until later.

Ken, can you take a look at this?
Comment 2 Kenneth Graunke 2011-02-09 14:23:51 UTC
Carl, would you mind taking a look at this?
Comment 3 Ian Romanick 2011-03-25 16:10:32 UTC
I spent a lot of time looking at this today, and I think I have an idea of what's going on.  I also think it will be a big hassle to fix.

glcpp already has code in it to prevent certain kinds of macro expansion recursion.  For example, the following code

#define A B
#define B C A

will produce


This is the desired result.

Recursion is prevented by keeping a stack of macros being expanded.  If an expansion produces a macro that is already on the stack, it is not expanded again.  However, management of this stack is tricky because the following code

#define foo(a) 5+a

should produce


As far as I can tell, this is handled by clearing the stack at certain points.

I believe the code needs to differentiate between new tokens resulting from macro expansion and new tokens resulting from parameter replacement.  Tokens resulting from parameter replacement (as in the `foo' example above) are always replaced, and tokens resulting from macro expansion are only replaced if the named macro isn't already in the replacement stack.

This groks with GCC's behavior.  The following code

#define bar(x) bar(x) + bar(x)


bar(2) + bar(2)
Comment 4 Kenneth Graunke 2011-04-17 01:05:39 UTC
Fixed in master.  Retargeting to 7.10.

Sorry, Ian, I forgot to mark this as a candidate for stable release branches.

commit 9dacbe222641443af000a82161922a5ade206340
Author: Carl Worth <cworth@cworth.org>
Date:   Fri Apr 15 12:03:25 2011 -0700

    glcpp: Fix attempts to expand recursive macros infinitely (bug #32835).
    The 095-recursive-define test case was triggering infinite recursion
    with the following test case:
        #define A(a, b) B(a, b)
        #define C A(0, C)
    Here's what was happening:
      1. "C" was pushed onto the active list to expand the C node
      2. While expanding the "0" argument, the active list would be
         emptied by the code at the end of _glcpp_parser_expand_token_list
      3. When expanding the "C" argument, the active list was now empty,
         so lather, rinse, repeat.
    We fix this by adjusting the final popping at the end of
    _glcpp_parser_expand_token_list to never pop more nodes then this
    particular invocation had pushed itself. This is as simple as saving
    the original state of the active list, and then interrupting the
    popping when we reach this same state.
    With this fix, all of the glcpp-test tests now pass.
    Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=32835
    Signed-off-by: Carl Worth <cworth@cworth.org>
    Reviewed-by: Ian Romanick <ian.d.romanick@intel.com>
    Reviewed-and-tested-by: Kenneth Graunke <kenneth@whitecape.org>
Comment 5 Ian Romanick 2011-04-21 12:54:27 UTC
This should be fixed on 7.10 as of 6d35d0bda67d528dfca4897d57ec61f6839c9a6b.
Comment 6 Vinson Lee 2011-04-21 17:52:41 UTC
mesa: d439491a77cf9f25ea7a7f9c2309d2542d87f83e (master)

Verified fixed.