Sometimes getting assertion failures using Lua Lanes

[ewmailing]

I started using Lua Lanes with Pallene. I sometimes hit assertion failures in Pallene, such as:

"wrong type for array element, expected float but found table"
and
"wrong type for array element, expected float but found table"

For my code, these things were created in Pallene, so the types should never change. So it felt almost like a race-condition that somehow code was being run before Pallene finished initializing the type.

This case is really hard to reproduce. If I re-run exactly as before, often I will not see the problem. And I never get this problem if I try to do a non-Lanes run. But I am trying to do some big runs that take many hours (hence why I am using Lanes), so after a long enough time, this assertion failure can pop up and completely ruin a run.

I've been banging my head on this for a week now. I've tried to make a simple isolated reproducible test, but I have been unable to trigger it with that so far.

So I tried to think what in Pallene could cause Lanes (multiple threads or multiple VMs) to break. Searching through the code, one thing that caught my eye is the use of static int, e.g.

        static int cache = -1;
        TValue *slot = pallene_getstr(9, x9, tsvalue(&K->uv[16].uv), &cache);

Thinking out loud, I'm wondering if the multiple Lanes VMs are fighting over this same static int in C, which is causing the race-condition-like behavior I'm experiencing.

If you think think this is a legit problem, can we try to fix this so it can become multiple VM and Lanes friendly?
If not, any other ideas on what might be the root of my problem?

Thanks

[hugomg]

Hmm... good question. My gut feeling is that this particular cache is not the culprit, but it should be easy to test. Since the cache is only used as an optimization, you could rewrite pallene_getstr so that it always ignores the cache.

One thing that I haven't done yet, but might help to debug these nasty bugs, would be to run Lua in debug mode with assertions turned on. See the LUAI_ASSERT define and the lua_assert macro that's inside some Lua and Pallene C code. If you could figure out the appropriate incantations to turn on these asserts it would be quite helpful for us in the future.

[ewmailing]

1. I temporarily changed the static int cache = -1 to int cache = -1 to effectively disable this code. Unfortunately, it didn't help my problem.
2. I manually defined LUAI_ASSERT in luaconf.h just to see what happens. I can now faithfully reproduce an assertion failure of:

lua: lapi.c:1015: lua_callk: Assertion `((nresults) == (-1) || (L->ci->top - L->top >= (nresults) - (nargs))) && "results from function overflow current stack size"' failed.

I removed Lua Lanes, so I can get this with my regular Pallene code.

Unfortunately, I do seem to need a certain threshold of things to do in my program, so the assertion does not appear in the most trivial of cases.

This assertion seems to happen in a rather large set of functions that call lots of helper functions, with lots of for loops inside. And some of these functions ping back and forth between Pallene and Lua. I don't think the crossing between Pallene/Lua is the culprit, but just the size of the functions and how many sub-functions are called.

To experiment further, first I removed the Pallene .so and used the --emit-lua to test my program. It avoided triggering any LUAI_ASSERT. So I'm pretty confident this is indeed a Pallene bug.

Second, I removed the emitted Lua and went back to Pallene. I isolated a smaller subroutine where the assertion was failing. The actual function it was dying at was a very simple Pallene function that I had used all over the program and was called probably thousands of times before this point, so I doubt this function is the actual problem. But the function does return 7 integers, which makes me think it exasperated this "stack size" assertion problem.

So next, I converted this subroutine (the whole function which includes all the stuff leading up to the simple 7 integer return value function) to pure Lua and transplanted it to Lua. I changed my Pallene callers so this subroutine would now go through Lua for this case.

This got me past the this particular subroutine, but a little further down the line, I hit the same assertion failure. As I said, this is overall inside a pretty big function.

Any thoughts on what to do next?

[hugomg]

Thanks!!! Could you please open a PR documenting how to do the assertion thing? We should probably start testing Pallene with these assertions from now on, to avoid similar trouble in the future.

By the way, do you know if the existing test suite can trigger these assertions?

Unfortunately, I do seem to need a certain threshold of things to do in my program, so the assertion does not appear in the most trivial of cases.

Since this is a stack overflow, perhaps we could try a Pallene program that's a single recursive function, called recursively many times? Possiblily with 7+ return values, if that helps.

I don't think the crossing between Pallene/Lua is the culprit, but just the size of the functions and how many sub-functions are called.

Would it be possible to find out how big the stack was when the crash happened? Total number of Lua and C calls?

If it's a smallish number (less than 100), I think that would narrow the possibilities for the bug.

Any thoughts on what to do next?

Next step we need to find this bug and squash it >:)

I wouldn't be surprised if it's some embarassing bug in the Pallene generated code for function calls. That code needs to carefully ensure that it grows the stack when it enter the function and that it updates the various stack pointers whenever Lua realocates the stack (due to the stack growing large enough). This is tricky and has been a source of bugs before.

If we could find a small reproducible example it would sure help. (I'd try a recursive function)

[ewmailing]

By the way, do you know if the existing test suite can trigger these assertions?

The test suite does not trigger these assertions.

Thanks!!! Could you please open a PR documenting how to do the assertion thing?

What do you mean by opening a PR? Do you want me to commit something to the code base? Or is this some kind of document I push somewhere?

All I did was add this line somewhere in luaconf.h

#define LUAI_ASSERT	1

I put it just before

#define LUAI_IS32INT	((UINT_MAX >> 30) >= 3)

because it seemed like a reasonable place.

Then make clean and rebuild everything.

I'm terrible with Makefiles, but it looks like the existing Makefiles have left an opening for $(MYCFLAGS)
In vm/src/Makefile, I think you could explicitly add to the MYCFLAGS= line, e.g.

MYCFLAGS=-DLUAI_ASSERT=1

As I said, I suck with Makefiles, but I think it is also possible to pass the flags from the command line. Something like (untested):

cd vm
make clean
make MYCFLAGS=-DLUAI_ASSERT=1 linux-readline -j

(Ultimately, the day I start needing to build for Windows and Mac, I'm going to have to write a CMake build script. Hence why I don't spend much time in Makefiles.)

Since this is a stack overflow, perhaps we could try a Pallene program that's a single recursive function, called recursively many times? Possiblily with 7+ return values, if that helps.

So I tried a quick and dirty recursive program, but it didn't work as hoped. I think it brings up some different issues...

1. When I run my quick and dirty recursive program (compiled with Pallene) with a large number, it segfaults without hitting any assertion
2. When I run this program as Lua, prints
   stack overflow
   and with a stack traceback:
3. I vaguely remember reading discussions that Lua actually has a different mechanism that controls/limits the call stack (for recursion) which I think is a separate mechanism from the lua stack.
4. The problem in my real program with the big function is not recursive (or at least mostly not recursive).

So I think Pallene also has a call stack recursion problem it maybe could try to handle more gracefully (can it provide a message and maybe terminate instead of segfault?). But I think the original problem may need to be reproduced without recursion since they might be different mechanisms.

If you are interested, I could provide you a copy of my bigger program (with the things I have stripped out so far to try to narrow down the space). But I know it is a far cry from a minimal test program.

[ewmailing]

I have one more piece of data to add.
I tried printing out the values passed to LUAI_ASSERT to see what's going on. This has actually led me to a whole bunch of confusion about what I'm looking at and C casting and truncation rules. But before I dive into that, I'm trying to look at the values of:

• L->ci->top
• L->top
• nargs
• nresults

I am using this printf to see things, which I placed in lapi.c, inside lua_callk right before check_results (which is connected to the LUAI_ASSERT).

  ptrdiff_t ci_top = L->ci->top;
  ptrdiff_t top = L->top;
  ptrdiff_t p_diff = ci_top - top;
  int n_diff = nresults - nargs;
  printf("B: L->ci->top=%ld\tL->top=%ld\tnargs=%d\tnresults=%d\tci_top-top=%ld\tnr-na=%d\n", ci_top, top, nargs, nresults, p_diff, n_diff);

For some context, the last good value printed out before I hit the assertion failure was:

B: L->ci->top=93992129505008	L->top=93992129504816	nargs=1	nresults=7	ci_top-top=192	nr-na=6

The next time this gets called with an assertion failure, the values looks like:

B: L->ci->top=93992129505008	L->top=93992129504928	nargs=1	nresults=7	ci_top-top=80	nr-na=6

So in this case, 80 >= 6, so it should pass the assertion test, and I have been banging my head on why this failed. So this is where I start struggling with C rules for converting types and also trying to figure out what exactly the fundamental type/value of L->ci->top and L->top are.

For reference, this is the definition of LUAI_ASSERT:

#define checkresults(L,na,nr) \
     api_check(L, (nr) == LUA_MULTRET || (L->ci->top - L->top >= (nr) - (na)), \
	"results from function overflow current stack size")

To cut to the chase, I think the C conversion rules are truncating 'top' at a specific time, which is making the value smaller than what my printf shows.
If I do:

  int c_diff2 = cast_int(L->ci->top - L->top);

That yields the number 5, and not 80, which is sufficient to cause the assert to fail.

So this brings up a deeper question for me of what is the type and size of 'top'? I see it is a typedef to a pointer to a Union called StackValue. I'm not used to seeing simple +/- operations on pointers to unions. If I do so, I'm usually doing directly pointer value math with ptrdiff_t. But I don't think that's what Lua is actually doing. So I'm not sure how to interpret what's going on here.

• But one speculation I have is that Pallene may have adjusted the 'tops' in such a way that it is also confused about the real size of the underlying type and may have overflowed it in its adjustment.
• Another speculation is maybe the LUAI_ASSERT macro definition is subtly wrong and maybe didn't expect values to get this big (64-bit system). But I'm skeptical of this idea.

So just to try it, I altered the defintion of the LUAI_ASSERT macro to try to avoid truncation by casting:

#define checkresults(L,na,nr) \
    api_check(L, (nr) == LUA_MULTRET || ((ptrdiff_t)L->ci->top - (ptrdiff_t)L->top >= (nr) - (na)), \
	"results from function overflow current stack size")

My program seems to just get past the previous run and then halts at the next Pallene function call.
The previous passing output was:

B: L->ci->top=94341797684976	L->top=94341797684896	nargs=1	nresults=7	ci_top-top=80	nr-na=6

And the output at the failure was:

B: L->ci->top=94341797684976	L->top=94341797685008	nargs=8	nresults=1	ci_top-top=-32	nr-na=-7

So I found it interesting that in this case, both sides of the inequality are negative.
The function in question does indeed have 8 arguments and returns 1 result.
This function was called successfully earlier in the program multiple times and did not trigger an assert. In those cases, the left-side was always positive (96 in my run).
This also reaffirms that 'top' can't just be an arbitrary pointer/memory address because this assert statement implies there must be an order in order for a subtraction to be a useful operation.

So at the moment, I'm not sure what to try next, but I'm hoping maybe this might trigger some ideas in you.

[hugomg]

The test suite does not trigger these assertions

Hmm. Once we figure out that reproducible test case we should add it to the suite. Maybe it's something that the test suite isn't testing well right now... For example, back and forth Lua<->Pallene calls or functions with large number of return values

What do you mean by opening a PR? Do you want me to commit something to the code base?

Currently the Pallene documentation is inside our git repository. I was thinking about adding those debugging tips to the CONTRIBUTING.md file.

MYCFLAGS=-DLUAI_ASSERT=1
(untested)

This sounds about right! Just test it to double check it, before opening the PR.

When I run my quick and dirty recursive program (compiled with Pallene) with a large number, it segfaults without hitting any assertion

What operating system are you running it on?

When I run this program as Lua, prints stack overflow

That's ok.

I vaguely remember reading discussions that Lua actually has a different mechanism that controls/limits the call stack

It does. There is also a mechanism for limiting the number of Lua->C calls, which may or may not be related to our bug here. (LUAI_MAXCCALLS)

The problem in my real program with the big function is not recursive

Sure. The idea of using a recursive program is to make a smaller test case that also has many function calls and grows the call stack.

So I think Pallene also has a call stack recursion problem it maybe could try to handle more gracefully (can it provide a message and maybe terminate instead of segfault?)

Perhaps... Could you please provide your minimal test case that segfaults so I can test it here? When I tried I couldn't get my programs to segfault on my Fedora laptop. What OSare you using now?

So this brings up a deeper question for me of what is the type and size of 'top'? I see it is a typedef to a pointer to a Union called StackValue.

Yes, IIRC they are pointers. I believe you can printf them with %p, which might avoid those type-conersion issues.

I'm not used to seeing simple +/- operations on pointers to unions

The pointer arithmetic for pointers to unions works the same as pointers to non-unions.

For our purposes, you can sort of pretend that the StackValue is the same thing as a TValue. The other case in the union is for the to-be-closed variables which were added in 5.4 but Pallene doesn't implement those yet.

This also reaffirms that 'top' can't just be an arbitrary pointer/memory address because this assert statement implies there must be an order in order for a subtraction to be a useful operation.

Indeed, they are not arbitrary, they have to point to the same Lua stack. IMO the best documentation of what the top, ci-top, etc are is Dibyendu's bytecode reference, found here: https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst

But one speculation I have is that Pallene may have adjusted the 'tops' in such a way that it is also confused about the real size of the underlying type and may have overflowed it in its adjustment.

My gut feeling is that an integer overflow bug doesn't sound likely. My first expectation would be a bug that's an out-of-bounds pointer access. One kind of bug that has happened before is if we don't grow the stack enough at the start of the function, perhaps because we told it to grow by less than it needed. Another thing that has happened before is if Lua reallocates the stack in response to the stack growing but we don't update the corresponding the base pointer that we also keep as a local variable in the generated C code.

[ewmailing]

For anybody else following along this thread, I have since:

• Submitted a PR documenting how to enable LUAI_ASSERT
• Submitted a new issue containing a simple test program that can crash with deep recursion.

Following up on the remaining points in this thread:

Yes, IIRC they are pointers. I believe you can printf them with %p, which might avoid those type-conersion issues.

The %ld vs %p will only change the format of what is displayed in the console output. It won't affect the logic of the assert.
But here is a repeat of the second run using %p.

B: L->ci->top=0x564801d6b6f0	L->top=0x564801d6b6a0	nargs=1	nresults=7	ci_top-top=0x50	nr-na=6`
B: L->ci->top=0x564801d6b6f0	L->top=0x564801d6b710	nargs=8	nresults=1	ci_top-top=0xffffffffffffffe0	nr-na=-7

Indeed, they are not arbitrary, they have to point to the same Lua stack. IMO the best documentation of what the top, ci-top, etc are is Dibyendu's bytecode reference, found here: https://github.com/dibyendumajumdar/ravi/blob/master/readthedocs/lua_bytecode_reference.rst

So for ordering to work with memory addresses, I think that means they must be elements in the same array. That diagram seems to confirm they are supposed to be in the same array. So if ordering breaks, it means they were placed in the wrong place in the array, or something was placed outside the array (e.g. wrong array, random memory address).

Circling back to my code that triggers the assert, it is a long function that calls many little helper functions both from Pallene and Lua, but the function calls don't go very deep...usually 1 level, maybe 2 levels deep. This function contains many for-loops and many string concatenations. There is also a lot of data copying, copying Records that contain lots of arrays into corresponding Tables so the data can be returned to be later processed by regular Lua functions. As such, I don't think the problem is necessarily because there are a function calls going down deep, but merely that there is a lot of work going on, which may be causing lots of memory allocations and probably work done by Pallene to manage the stack.

(And incidentally, I think this section of code may have been part of the code that originally uncovered the slow string performance in Pallene that I reported almost a year ago.)

[ewmailing]

I just filed bug #551 which includes a stripped down reproducible test case for this problem.

[ewmailing]

Hello, I was just wondering if you've made any progress on this bug.

A slight tangent, but I decided to try using LuaJIT as a temporary workaround. I just did a benchmark of a small/medium size run comparing LuaJIT and Pallene, no Lua Lanes in this run...

Pallene was almost twice as fast as LuaJIT for my program (ignoring runs where Pallene fails due to this bug). (And I disabled the LUAI_ASSERT for this benchmark.)

LuaJIT 2.1.0-beta3:
real 20m13.698s
user 17m9.879s
sys 0m43.243s

Pallene:
real 11m33.475s
user 9m11.986s
sys 0m0.511s

Lua 5.4
real 37m43.191s
user 35m22.021s
sys 0m0.568s

I think that's pretty impressive. I don't really know the reasons for this. The program is not optimized...just written to try to solve my problem. The program does a lot of simple math in nested for-loops. But the program as a whole also has a lot of control flow stuff. If I had to guess as to the reason, the program is complicated enough that it is probably hard to unroll and vectorize a lot of things, and probably a the majority of the time is dealing with the control flow. And out of habit and training, in general my development style tends to try to avoid lots of memory allocations and deallocations, so I'm skeptical the timing differences are related to the garbage collector differences.

Anyway, I think this performance is pretty promising for Pallene. I think my program is more representative of what real world programs look like as opposed to micro-benchmarks, so hopefully Pallene will be able to bring substantial performance gains like these to more real world programs.

[hugomg]

Unfortunately I haven't had a chance to look into it yet. I'm wrtiting a paper and there's a close deadline coming up...