memory allocation determinism and global pollution

[sherief]

I've been playing with Fennel for a while and I'm now trying to integrate it into an existing Lua environment on a resource constrained platform with more stringent requirements. I have run into a couple of issues that I cannot fully understand wrt memory allocation and global namespace pollution that I was hoping to clarify.

I'm applying slight modifications to Fennel so it loads with a minimum of libraries - the modified version (with diffs via git history) is at https://code.sherief.fyi/sherief/fennel-standalone/src/branch/master/fennel.lua

This loads and runs fine, but every time it's loaded it does a variable number of memory allocation, and I don't understand where this variability is coming from. A small bootstrap program with accounting can be found at https://code.sherief.fyi/sherief/fennel-bootstrap - this program can be used to reproduce both issues discussed here.

Running it and loading Fennel multiple times, I get this output indicating a variable number, and size, of allocations:

alloc = 465379, realloc = 23224, bytes = 15049385, bytes-rounded = 1007338
alloc = 464795, realloc = 23224, bytes = 15038740, bytes-rounded = 1006673
alloc = 466546, realloc = 23225, bytes = 15075028, bytes-rounded = 1008941
alloc = 465447, realloc = 23225, bytes = 15058453, bytes-rounded = 1007905
alloc = 464758, realloc = 23224, bytes = 15038692, bytes-rounded = 1006670

What could be causing this non-determinism? Other Lua libraries load with the exact same allocation counts / sizes every time.

The second issue is related to a Lua modification, and I totally understand if you're not interested in supporting it. The environment my code runs in requires strong enforcement of no global pollution, and I modified the VM to add a call to protect globals / upvalues to Lua: https://code.sherief.fyi/sherief/lua-build/commit/39f5ac104019095b0ec6e37ad4752402ef8983cc

when this global protection is enabled, compiles fail since compileStream() calls setReset() where there is this problematic line: root.chunk, root.scope, root.options = chunk, scope, options

(direct link to line: https://code.sherief.fyi/sherief/fennel-standalone/src/branch/master/fennel.lua#L337 )

I've been trying to do some code spelunking but I can't figure out why a global is modified here, and whether it would be possible to compile Fennel to Lua without touching a global. Is that possible?

Thanks for your time, and once again I understand that this is a custom setup and you'd be perfectly fine closing this bug with a "nope, won't support".

[sherief]

I found out the answer to one of my questions - sometimes when you sort in Lua, directly or indirectly, you end up using a different size and count of memory allocations depending on what time it is.

auxsort() calls l_randomizePivot(): https://code.sherief.fyi/sherief/lua-build/src/branch/master/src/ltablib.c#L392

which is implemented using the current time: https://code.sherief.fyi/sherief/lua-build/src/branch/master/src/ltablib.c#L246

there's also a per-state random seed: https://code.sherief.fyi/sherief/lua-build/src/branch/master/src/lstate.c#L71

sigh

[technomancy]

Another source of randomness is pairs in Lua 5.2+; earlier versions would iterate tables in deterministic order, but since 5.2 it randomizes the hashing of table keys. I think this was done in order to improve robustness against DOS attacks where user-provided input is used as a table key: https://lua-users.org/wiki/HashDos

I would expect there to be a compile-time flag to disable this, but I haven't been able to find it.

[technomancy]

I've been trying to do some code spelunking but I can't figure out why a global is modified here, and whether it would be possible to compile Fennel to Lua without touching a global. Is that possible?

I think I see what you mean. The intent of the code in setReset() is to modify the root local, but since it happens during the declaration of the root local, the local isn't yet in scope, and it ends up resolving to the global instead. That is a mistake, and it only occurs in the bootstrap compiler; the real implementation of set-reset does not have that problem because it defines set-reset later after root is already in scope:

(local root {:chunk nil :scope nil :options nil :reset (fn [])})

(fn root.set-reset [{: chunk : scope : options : reset}]
  (fn root.reset []
    (set (root.chunk root.scope root.options root.reset)
         (values chunk scope options reset))))

So the bootstrap compiler should be modified to work like the canonical implementation so it does not modify a global.

On the other hand, your limited environment doesn't need to run the bootstrap compiler at all; it might make more sense to compile fennel.lua on a real full Lua first, and then just put the compiled output into your limited environment. But I don't know the context of what you're trying to do.

[technomancy]

I think 26b7165 should fix this; let me know if that does it.

[sherief]

I applied the changes above to https://code.sherief.fyi/sherief/fennel-standalone/commit/4f41115e5dcb5968ed952d35bd0bfbd0dadc26fb and I still end up getting the same error: [string "--[[..."]:340: Attempt to modify protected upvalues.

by compiling you mean run fennel.lua through luac or use a lua_dump() to store bytecode, then load that instead?

[sherief]

I ran fennel.lua through luac then used luaL_loadbuffer() to load it with the same result and error.

[technomancy]

by compiling you mean run fennel.lua through luac or use a lua_dump() to store bytecode, then load that instead?

No, not at all. The file you linked to was https://code.sherief.fyi/sherief/fennel-standalone/src/branch/master/fennel.lua which is a copy of the bootstrap compiler. The only purpose of the bootstrap compiler is to compile the Fennel code in https://git.sr.ht/~technomancy/fennel/tree/main/item/src/fennel into Lua. It is not meant to run application code. When you run make in the Fennel repository, you get a file called fennel.lua which is different from the one in your link: https://fennel-lang.org/downloads/fennel-1.5.0.lua

[sherief]

I used fennel-1.5.0.lua linked and applied the needed modifications to remove dependency on package: https://code.sherief.fyi/sherief/fennel-standalone/src/commit/2abb3d202dd407829c9c83ace40d7fe498674ba6/fennel.lua

I get the same error referencing this line: https://code.sherief.fyi/sherief/fennel-standalone/src/commit/2abb3d202dd407829c9c83ace40d7fe498674ba6/fennel.lua#L5585

Error: [string "-- SPDX-License-Identifier: MIT..."]:5585: Attempt to modify protected upvalues.

[technomancy]

That's very strange, because that line you're referencing clearly has root in scope on line 5572.

Can you provide a repro case?

[sherief]

If you're on Windows you should be able to clone this with submodules and build in Visual Studio - it's a small bootstrap app and it does the upvalue protection / compile at line 220: https://code.sherief.fyi/sherief/fennel-bootstrap/src/branch/master/fennel-bootstrap.cpp#L220

if you're using another platform let me know what it is and I'll try to add build files for it.

[technomancy]

No, I don't have a Windows machine; sorry. However, it's pretty easy to do global pollution prevention using pure Lua:

setmetatable(_G, {__newindex=function(_,k) error("global: "..tostring(k)) end})

print("bootstrap...")
dofile("bootstrap/fennel.lua").eval("(print :ok)")

print("mainline...")
dofile("fennel.lua").eval("(print :ok)")

Results are consistently good across all supported versions:

~/src/fennel $ luajit g.lua
bootstrap...
ok
mainline...
ok
~/src/fennel $ lua5.1 g.lua
bootstrap...
ok
mainline...
ok
~/src/fennel $ lua5.2 g.lua
bootstrap...
ok
mainline...
ok
~/src/fennel $ lua5.3 g.lua
bootstrap...
ok
mainline...
ok
~/src/fennel $ lua5.4 g.lua
bootstrap...
ok
mainline...
ok

So whatever you're encountering must be different from global pollution.

Error: [string "-- SPDX-License-Identifier: MIT..."]:5585: Attempt to modify protected upvalues.

It looks like your code prevents the root upvalue from being set. I don't understand why you would want to do this. Setting upvalues in this way is an integral part of how the compiler works. What problem are you trying to solve by preventing upvalues from being modified?