Developer blog - otto@: New Otto malloc helps spot ancient bugs

As some of you know I have been working on a new implementation of malloc, the general purpose memory allocator that's used by userland programs. See this link for more details about it.

My malloc has been tested by many and has been in snapshots for a while now. Some time ago I received a bit of a puzzling report from Nikolay Sturm (sturm@) that on sparc64 compiling big C++ projects would sometimes fail with an Internal Compiler Error (ICE). For a start, it was not clear if my new malloc was involved, but I setup my sparc64 machine for testing. It soon turned out I could reproduce the problem. Switching to the in-tree malloc made the problem go away. So I was facing a malloc bug or a gcc bug, I thought.

Otto continues below...

My new malloc has some features not found in the current malloc: it moves allocations smaller than a page but bigger than half a page to the end of the page, to have a greater chance of catching buffer overflows. Even without guard pages, this works most of the time, since we have a randomized mmap(2): there's a pretty big chance that there is a hole after a page allocated. Accessing that hole leads to a segmentation fault.

So I put my malloc back in, and started investigating. The first thing I tried was to switch off the code that moves small allocations: and yes, that made the bug go away. Using an unstripped version of the compiler, I could interpret the backtrace in gdb, and it soon turned out that the compiler was dying in yyparse(). yyparse() is the main function generated by the parser generator yacc(1). After compiling obj/cp/parse.c with debug options and some fighting with wrong line numbers reported by gdb, I saw the offending statement was the second statement below;

yym = yylen[yyn];
yyval = yyvsp[1-yym];

It turned out yym was 0, so yyvsp[1] was accessed: one stack entry above the current stack pointer.

Yacc has an implicit action that does:

$$ = $1;

before the action of a rule is done. $$ refers to the result of the rule, and $1 refers to the first item on the right hand side of the parse rule, yym says how many right hand side values of the current rule there are on the stack. The two statement above implement the implicit action.

But if the actions are part of a rule that has no right hand side:

A: /* empty */ { foo(); };

the implicit action will access via $1 a value beyond the top of stack: yym will be 0 in that case. Normally, that isn't a big problem: you're just accessing garbage, and assigning it to $$.

But if the stack is at maximum size, this will overflow if an entry on the stack is larger than the 16 bytes leeway my malloc allows. In the case of of C++ it is 24 bytes, so a SEGV occured.

Funny thing is that I traced this back to Sixth Edition UNIX, released in 1975. A very similar problem can be spotted here. The lines:

yypv =- yyr2[n];
yyval=yypv[1];

access an item above the stack pointer. If yyr2[n] is zero, this is a potential access outside the stack. Note the archaic use of =-, we write -= these days.

The bug was only triggered on sparc64, since it uses 8k pages. The default yacc stack size for C++ is 24 * 200 = 4800 bytes, which is larger than a page on most platforms. In this case malloc returns a page aligned object, no moving of the allocation inside a page occurs.

I'm really happy this turned out to be a yacc bug, and not a malloc bug. It's actually a malloc feature in action. ;-)

The commit that fixes this can be found here.

-Otto