[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Deterministic hashing for lua tables
- From: Florian Weimer <fw@...>
- Date: Sun, 18 Dec 2011 22:41:52 +0100
> 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
> 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
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.)