Re: Strange memory allocation behavior

[Tom Sutcliffe <tomsci@...>]

> On 17 Sep 2018, at 6:16 pm, Luke Horgan <horgan.l@husky.neu.edu> wrote:
> 
> Hello all,
> 
> Thank you so much for the information you've provided!  Tom, your
> answer in particular has answered many questions I had.
> 
> I have not disabled the garbage collector for performance reasons.
> The issue (or part of it) is that the contract scripts are supposed to
> be strictly deterministic, and I wasn't sure if there was any
> randomness or unpredictability in the way the garbage collector
> chooses when to run, or what to collect.  Every script has to have
> exactly the same output on every peer's machine.  

If the GC step and mul parameters are set the same, then the GC will behave _mostly_ identically on any machine running the exact same Lua binary (in particular 32- and 64-bit builds will be different even when still on x86 - different architectures will have different sizes for data structures which will affect collection logic). You would have to control for anything discernibly different about the environment that scripts can detect - any API that could return a different-sized result on different machines (even down to eg localisation of date formats, if those APIs are exposed). And I'm assuming your subset of the language locks down most things that could have side-effects

I was thinking you might have to change l_randomizePivot to the recommended non-random ~0 implementation, but looking again at the code, it seems to only be used when sorting tables which I don't think is a problem since that doesn't allocate. You may wish to do that anyway to make sorting fully deterministic in time as well as space domains.

> You can imagine a
> scenario where someone deliberately writes a script that creeps up on
> the memory limit.  If the garbage collector isn't totally consistent,
> then maybe it swoops in and frees memory on one user's machine before
> it has a chance to fail, while on another user's machine it doesn't.

Whether this matters or not depends on whether you have a strict requirement on timing being absolutely exact or not (which might be a tricky thing to control for full stop, when running on a preemptive multithreading OS). If the timing doesn't have to be precisely exact, then the situation you describe (there not being quite enough freed by the collector at the point of allocation) will result in Lua initiating a full collection cycle and retrying the allocation (providing your allocator returns NULL when overbudget, rather than say halting the script immediately). Obviously this will affect timing but should be (mostly) invisible to the script. Meaning that assuming there's enough space left in the budget, it shouldn't matter whether or not the GC is fully up to date with its housekeeping or not. I'm assuming also that the memory limit you're imposing is sufficiently small compared the physical capabilities of the machine that fragmentation won't be an issue.

> If I keep a running tally of total allocated memory, will that number
> be consistent on every run, on every machine?  I suppose I could
> experiment a bit to find out, although it would be nice to gain some
> insight into how the collector actually works behind the scenes.

I think that's an interesting question in of itself :-) In theory, assuming you've controlled for everything I've described (and whatever else I failed to think about) then I think the answer would be yes, for a program not relying on undefined behaviour. Tracking that number over time across multiple runs sounds like it would be a useful way to see how things are behaving. But as I mentioned, it may not in fact matter to control the environment this strictly, if you're only concerned about memory budget, given the script will only get an "out of memory" error if there isn't any memory available *even after* collection.

Thinking about it some more, there are two aspects to this:

1) Ensuring the Lua environment uses exactly the same amount of memory when running a given script, regardless of the state of the machine it's running on, so as to guarantee that the memory limit imposed on the script is enforced consistently on all machines. This is all the controlling for external factors stuff, making sure there aren't any APIs exposed to Lua (or called by it internally as a result of anything the scripts can do) which can return different-sized results. Then, there's:

2) Ensuring entirely deterministic program execution in all scenarios, including code which depends on things which Lua says are implementation-defined. Because the GC can only be fully deterministic if the entire program flow is also deterministic. This is a much harder problem, as all the SPECTRE-style side-channel vulnerabilities have shown recently when applied to CPU hidden state. I could write a program involving a custom __gc metamethod which behaves differently depending on exactly when the GC ran. Equally I could write something which produced different output depending on what pointers the underlying allocator returned, because various things are hashed using their pointer value, and what they hash as affects the order that a pairs()-style table iteration would return them in (or, trivially, looking at the value returned by `tostring(function() end)` and doing something different depending on the value). Either of those two things could allow a badly-behaved program to behave differently across different runs, but only by exploiting things which Lua says are implementation-defined and that you shouldn't rely on. Note in particular, disabling the GC entirely doesn't prevent exploitation of the second of those two things. The question then is do you want to try and control for those too, with eg custom allocator trickery to hide the differences of the underlying malloc implementation, or a custom pairs() implementation which sorts all the keys or something.

So if you're only concerned about (1), leaving the GC running and taking precautions to control for everything affecting memory usage, is probably quite tractable. If you want to go the whole hog and try and tackle (2), that might be considerably more work. Obfuscating information leaks (like the pointer value of a function via tostring()), maybe banning custom __gc metamethods, or redefining pairs, or defining a fully custom allocator (rather than just a wrapper that enforces budget then calls through), there are a lot of things you might want to consider.

Regards,

Tom