Re: Deterministic hashing for lua tables

[Florian Weimer <fw@...>]

> I am working on a fully deterministic Lua, and I gather that one
> source of indeterminacy in a script's execution is that Lua tables
> hash objects according to their positions in memory, and traversing
> table contents follows the hash table positions, resulting in
> different traversal orders depending on memory layout.

Heap randomization is a security feature to some degree, and so is
non-deterministic hashing (which most Lua implementations don't
provide, alas).

> Other potential indeterminacies could arise from floating-point
> rounding errors

No, these are fully deterministic.

> I am imagining changing ltable.c:hashpointer to a function which
> when called with a pointer p, looks p up in an internal hash table
> IHT.

It may be beneficial to store the hash of the object inside the
object.  This is what JVMs do if they move an object whose
identity-based hash code has been fixed (before that, it can be
derived from the address of the object).

> However, I am not sure what I could use for deterministic hashing of
> the LUA_TFUNCTION and LUA_TTHREAD types, and I would need to require
> the LUA_T*USERDATA types to provide some kind of hashing function
> for themselves.

It is sufficient to number all allocated objects sequentially.  The
numbers might not be easily predictable, but they are fully
determinstic.  (Similar to floating-point rounding errors.)