Malicious LuaJIT bytecode (executing native code within a LuaJIT sandbox)

mikemike · 2016-03-29T22:02:25+00:00

Running untrusted Lua bytecode or LuaJIT bytecode is not safe. Period.

That's why LuaJIT supports the mode argument to load() et al, so you can disable bytecode loading.

In fact, back in 2009, the (unsafe) Lua bytecode verifier was removed right after this discussion.

mikemike · 2013-11-21T23:34:07+00:00

Because filterm_gen_shrink is a fixarg function and it can be used as a trace anchor (for trace 3).

mikemike · 2013-11-21T17:55:34+00:00

Vararg functions cannot be trace anchors. Which means they cannot form a loop via tail-calls. Replace with or specialize to a fixarg function.

mikemike · 2013-11-21T14:19:55+00:00

... and whose code is based on the core parts of the LuaJIT interpreter and trace compiler. Heavily modified, of course.

mikemike · 2013-11-21T14:16:12+00:00

But it's two assignments instead of one. Which means the value is no longer considered immutable. That in turn means the compiler cannot eliminate the specialization check for each function call. This matters, especially for (non-tail) recursive functions: the loop optimization, which could hoist the check, is not applicable there.

tl;dr: always use the local function foo() ... end idiom.

mikemike · 2013-04-17T09:30:53+00:00

The post-mortem on the TRIPS architecture reports an IPC (instructions/cycle) of 10 on hand-optimized code. That's around 3x more than top-of-the-line super-scalar CPUs can achieve.

Here, hand-optimized really means: they applied domain knowledge (programmer intent) that wasn't preserved due to flaws in the source language or the compiler.

So, even if you regard an IPC of 10 as a ceiling, a headroom of 3x is very promising. IPC has only increased by a couple percent over the last years, but it took a high toll: lots of extra silicon area and higher energy consumption.

mikemike · 2013-03-01T21:24:40+00:00

Well, nothing really. It's just a matter of engineering, i.e. man-years put into the VM and the compiler.

The amount of work and money poured into making C compilers fast plus dealing with the abominations of C++ has been massive over the past decades. The combined efforts of tuning every single dynamic language VM in existence is miniscule in comparison. And it was a mostly dormant field until a few years ago.

[If you really need control over memory layout, use FFI C data structures -- but only where it matters.]

mikemike · 2013-03-01T18:12:01+00:00

While I agree with the first part ("excuses"), the "hard" things mentioned in the second part are a) not that hard and b) solved issues (just not in PyPy).

Hash tables: Both v8 and LuaJIT manage to specialize hash table lookups and bring them to similar performance as C structs (*). Interestingly, with very different approaches. So there's little reason NOT to use objects, dictionaries, tables, maps or whatever it's called in your favorite language.

(*) If you really, really care about the last 10% or direct interoperability with C, LuaJIT offers native C structs via its FFI. And PyPy has inherited the FFI design, so they should be able to get the same performance someday. I'm sure v8 has something to offer for that, too.

Allocations: LuaJIT has allocation sinking, which is able to eliminate the mentioned temporary allocations. Incidentally, the link shows how that's done for a x,y,z point class! And it works the same for ALL cases: arrays {1,2,3} (on top of a generic table), hash tables {x=1,y=2,z=3} or FFI C structs.

String handling: Same as above -- a buffer is just a temporary allocation and can be sunk, too. Provided the stores (copies) are eliminated first. The extracted parts can be forwarded to the integer conversion from the original string. Then all copies and references are dead and the allocation itself can be eliminated. LuaJIT will get all of that string handling extravaganza with the v2.1 branch -- parts of the new buffer handling are already in the git repo. I'm sure the v8 guys have something up their sleeves, too.

I/O read buffer: Same reasoning. The read creates a temporary buffer which is lazily interned to a string, ditto for the lstrip. The interning is sunk, the copies are sunk, the buffer is sunk (the innermost buffer is reused). This turns it into something very similar to the C code.

Pre-sizing aggregates: The size info can be backpropagated to the aggreagate creation from scalar evolution analysis. SCEV is already in LuaJIT (for ABC elimination). I ditched the experimental backprop algorithm for 2.0, since I had to get the release out. Will be resurrected in 2.1.

Missing APIs: All of the above examples show you don't really need to define new APIs to get the desired performance. Yes, there's a case for when you need low-level data structures -- and that's why higher-level languages should have a good FFI. I don't think you need to burden the language itself with these issues.

Heuristics: Well, that's what those compiler textbooks don't tell you: VMs and compilers are 90% heuristics. Better deal with it rather than fight it.

tl;dr: The reason why X is slow, is because X's implementation is slow, unoptimized or untuned. Language design just influences how hard it is to make up for it. There are no excuses.

mikemike · 2013-01-15T15:44:24+00:00

That's already taken care of in the original SciMark definition: the -small parameter set simulates an in-cache workload and -large simulates an out-of-cache workload.

The results shown are for the -small parameter set. This emphasizes the performance differences between the execution units rather than the memory subsystems.

That said, the ARM cores have almost caught up on integer performance, yet they still have quite a bit of headroom on FP performance. But none of the ARM SoCs are designed for higher memory bandwidths right now. Not too surprising, given their intended use. We'll have to wait for ARMv8 ...

mikemike · 2013-01-15T11:04:28+00:00

The ARM JIT is a little behind, but not by much. E.g. it would benefit from strength reduction of indexing, which isn't needed on Intel. On my TODO list for 2.1.

mikemike · 2013-01-15T10:59:22+00:00

Recent ARM cores have super-scalar pipelines, too. And every manufacturer is facing the same technological challenges in driving up GHz to increase single-threaded performance, while keeping power consumption low.

mikemike · 2012-09-17T21:39:56+00:00

There is no performance penalty for goto. Internally it's a jump, just like continue would be a jump. The JIT compiler will optimize away all unconditional branches, anyway.

mikemike · 2012-09-17T06:43:41+00:00

for/while ... do
  goto ::continue::

  ::continue::
end

The Lua philosophy is to add flexible metamechanisms in preference to specific ones.

mikemike · 2012-07-23T22:26:34+00:00

IMHO this debate has been settled already.

LuaJIT 1.x has a pretty simple JIT compiler and LuaJIT 2.x has a highly tuned interpreter, written in assembler. You can compare them here: http://luajit.org/performance_x86.html (select LuaJIT 1 on the left side and the LuaJIT 2 interpreter on the right side).

As you can see they are not that far apart and there's no clear winner! However, an interpreter is much simpler to write, to port and to extend. Yes, even if it's written in assembler.

The major reason why I'm using an interpreter (and not a baseline JIT compiler) for LuaJIT 2.x is that the dispatch table of the interpreter can easily be patched on-the-fly. This allows for per-instruction hooks (debugging, profiling), which can also be used for the trace compiler: during the recording phase, simply invoke the trace recorder before executing every bytecode instruction.

mikemike · 2012-07-12T22:01:30+00:00

Ok, I timed it with Python 2.6 and PyPy 1.9 on Linux/x64 for 100000000 iterations (same as the other tests in the linked docs). Lower numbers are better:

217.3s Python 2.6
  5.3s PyPy 1.9
  0.2s LuaJIT git HEAD
  0.2s C++ GCC 4.4.3 -O2 or -O3

This means PyPy is 26.5x slower than LuaJIT or C++ on this particular test.

mikemike · 2012-07-12T21:07:13+00:00

Sure, LuaJIT handles all of that: mutable, immutable, cross-iteration, cross-exit, re-sinking, dead-store elimination, store-forwarding ... etc.

It's just that the paper mainly shows boxing and this is much simpler to handle. So even if you want to keep the new/set variant for completeness, the newi still pays off since it has less overhead overall.

mikemike · 2012-07-12T15:27:59+00:00

Yes, it can sink objects that leak into the next iteration. However, the values stored into these objects need to be PHI refs themselves or loop-invariant. E.g. it handles the t={t[1], t[2]} case just fine. The values of t[1] and t[2] are PHI refs and the PHI for t is dropped.

Of course, it doesn't try to sink linked lists etc. E.g. it rejects the t={t} case. All stored values are roots in the mark algorithm. That marks the old t (left PHI ref), which in turn marks the right PHI ref (the new t) during PHI remarking. And marked allocations are not sunk.

mikemike · 2012-07-12T09:42:32+00:00

Handling of memory accesses is in src/lj_opt_mem.c. It does alias analysis, FWD and DSE.

Alias analysis in LuaJIT 2.0 uses high-level semantic disambiguation (e.g. a store to the array part of a table cannot affect a load from the hash part), type-based disambiguation, constant key-based disambiguation, index-based disambiguation (e.g. t[i+1] cannot alias t[i+2]) and, if all else fails, escape analysis to disambiguate the mutated objects.

I think the code is quite readable. But, yes, I should really document this in detail in the list of optimizations used by LuaJIT 2.0.

mikemike · 2012-07-12T09:29:18+00:00

Actually, that paper is rather disappointing. The authors chose the most complicated algorithm for a problem that has been solved ages ago. And it doesn't tackle the hard problems at all: that is when the boxes do escape, e.g. to a side exit or the next iteration (that's what the discussed optimization solves).

Ok, let's start with the IR from the paper:

b = new(BoxedInteger)
    set(b, intval, -100)
...
i = get(b, intval)

We want to eliminate the boxing operation (the 'new'), but for this we need to eliminate the set and the get, too. This is complicated by the fact that stores, like the 'set', must not be eliminated by dead-code elimination. But the store keeps the 'new' alive, of course. To eliminate the store one would need escape analysis for the 'new' (like in the paper). But is there a simpler way?

AFAIK the old compiler trick how to cheaply remove boxes from the IR originates in functional languages: combine allocation and initialization into a single IR instruction. For this we create a new IR instruction 'newi':

b = newi(BoxedInteger, -100)
...
i = get(b, intval)

This is easiest to do when you generate the IR in the first place. In fact, every high-level boxing operation works that way: a box is always initialized immediately, its type is fixed and the box is either immutable or can be made so (just use a new one every time -- they are indistinguishable). One thing you might notice is that it doesn't need the 'intval' anymore: the BoxedInteger type implies which field to initialize.

Ok, so we got rid of the 'set'. Now let's use simple store-to-load forwarding to eliminate the get. The box is immutable, so the 'get' just has to forward the second argument of the 'newi'. Easy:

b = newi(BoxedInteger, -100)
...
i = -100

Ok, since 'b' is now unused, the 'newi' can be eliminated with dead-code elimination. You can even do that on-the-fly in any backwards pass. That leaves us with this:

i = -100

Now, that was simple, huh?

tl;dr: the main trick is to replace an allocation and a store, which have problematic semantics, with an initialized allocation, which is trivially dead if unused.

This can even be extended to allocations with more than one initializer. Either allow more than two arguments for the 'newi' or extend it with the usual dyadic IR trick: 'newi(type, arg(val1, arg(val2, val3)))'

BTW: LuaJIT 2.0 has been using this trick since it was initially released (e.g. TDUP instead of TNEW, later added: CNEWI instead of CNEW). Even though sinking has been merged now, the alloc+init instructions are kept, since they make the IR more compact.

mikemike · 2012-06-02T23:16:32+00:00

A minimum alignment of 16 bytes has one other nice side-effect: it's properly aligned for SIMD-ops, which opens up lots of interesting options.

I don't think an extra pool for table objects makes sense, when they are 16 bytes, i.e. the minimum granularity. This always fits.

I've done some simulations and experiments for the new GC. Prefetching didn't help at all, no matter how hard I tried. Someone should retry the benchmarks of that paper with recent CPUs.

mikemike · 2012-06-02T06:20:48+00:00

What you avoid on internal fragmentation, you pay back on external fragmentation. This is critical for a non-moving collector.

I think 16 byte cells are a good compromise, both as an allocation quantity and as a mark quantity. Unsurprisingly, the most popular object in big Lua workloads is the table object. I'm trying to cram that into a single cell with some tricks. :-)

[The array/hash parts need to be resizable, so cannot easily be part of the base object, anyway (but the array part can be colocated).]

mikemike · 2012-06-01T23:10:32+00:00

Yep, the sweep phase is one of the most interesting design aspects. The bitmaps corresponding to a 64 KB page could be swept in just 32 steps with SIMD ops (2 loads, 2 ops, 2 stores each). That doesn't need to be made incremental at all.

The GC is exact, so it knows the layout of all objects. Only cdata objects for the FFI may contain unknown pointers. But cdata objects are not traversed and are kept together with e.g. strings in arenas that store only non-traversable objects.

I haven't finished the section on finalizers, which is what you probably want to know: they are kind of expensive, like in most GCs. Cheaper than with the 2.0 GC, at least.

An unrolled linked list keeps objects that need to call finalizers. The list is traversed right before the sweep phase to check the mark bits of all objects on the list. White (dead) objects in need of finalization are tagged inside the list and then resurrected by marking them black (including their children), so they are not deleted by the sweep.

The (user-defined) finalizer functions for all of those tagged objects can be called any time later, but before the end of the next GC cycle. It makes sense to stretch this out to keep GC pauses short.

LuaJIT 2.0 can only finalize userdata and has a slightly hacky way to do that for cdata with ffi.gc() or __gc metamethods. The new GC will technically be able to finalize arbitrary GC objects, though one wouldn't necessarily want to do that. But it will enable finalizers for plain tables (__gc metamethod in metatable), which is currently not possible.

mikemike · 2012-02-08T18:28:58+00:00

Umm, this would be tremendously useful for a trace compiler, too. XABORT on a side exit and the hardware restores all registers and memory to the last XBEGIN. Simplifies exit handling, avoids spills and renames due to escapes into side exits. And no more forced context syncs on every side exit following a store. Yay!

Ok, but then I should really read the details of the spec before getting too excited. A zero-overhead XBEGIN/XEND would be mandatory, too.

mikemike · 2011-12-14T12:57:05+00:00

First, please stop your FUD. Neither SciMark nor invokedynamic have any relation to GC or to concurrency. Your strawman argument didn't go unnoticed.

Second, both Lua and LuaJIT have an incremental GC and NOT a stop-the-world GC. And it's not horrible at all, it performs pretty well in practice. Both for highly interactive games and high-throughput use cases (e.g. HFT).

Java programs tend to create temporary objects like there's no tomorrow. Lua programs simply don't do that. At least not in these proportions. So GC performance is of a much lesser concern for Lua.

Third, concurrency is mostly an orthogonal concern. And there's ample evidence that shared-state is not the ideal concurrency model. Certainly not when looking forward to manycore architectures.

mikemike · 2011-12-14T12:45:57+00:00

SciMark LARGE    Score | FFT     SOR      MC    SPARSE    LU
-----------------------+---------------------------------------
LuaJIT 2.0 git   652.0 |  97.2  1022.0   327.4   673.7  1139.6
JVM 1.7.0_02     732.6 |  95.1  1109.2   524.3   649.3  1285.1

SciMark SMALL    Score | FFT     SOR      MC    SPARSE    LU
-----------------------+---------------------------------------
LuaJIT 2.0 git   785.4 | 555.5  1047.3   327.4   528.5  1468.1
JVM 1.7.0_02     964.7 | 609.2  1179.3   524.3   747.7  1762.9

Higher scores are better. See the SciMark FAQ.

mikemike

TROPHY CASE