merge “safe” and “unsafe” lists

[jan-ferdinand]

The primary purpose of this PR is to unify the two list types “safe” and “unsafe”. Even though both list types existed, only “unsafe” lists were used in practice. To make these lists safe, each memory allocation request results in enough memory being assigned to the caller to make out-of-bounds access impossible in practice.[^safe]

There are two additional major changes:

1. The dynamic memory allocator no longer accepts an argument. Its signature is now || -> address.
2. A new memory convention.

The new memory convention is as follows[^mem]:

• A memory page is contiguous memory of size $2^{32}$ words, aligned to $2^{32}$ word boundaries. There is one exception: due to the base field's prime being $2^{64} - 2^{32} + 1$, the last page, starting at address $2^{64} - 2^{32}$, is of size 1.
• The dynamic allocator lives at address $2^{64} - 2^{32}$, i.e., $-1$. It is a single word, containing the value of the next free page. It occupies the only page that is not of size $2^{32}$ words.
• Page 0 is reserved for non-deterministically initialized memory.
• The last full page, number $2^{32}-2$, starting at address $2^{64} - 2\cdot(2^{32})$, is reserved for static allocations.[^static]
• All other pages, i.e., pages 1 through $2^{32}-3$, are dynamically allocated.

[^mem]: The convention is now also part of the documentation. It can be found in src/memory.rs. [^safe]: It is always possible to access arbitrary memory locations if one chooses to do so; Triton VM has no understanding of anything resembling memory allocation. [^static]: The current implementation does not enforce this explicitly. Instead, it is assumed that calling the dynamic allocator often enough to accidentally access the memory page for static allocations is impossible.

[aszepieniec]

:+1:

[Sword-Smith]

One open question: Do we want to verify that the memory offsets are of type u32? E.g. in the Get snippet, we have:

            // BEFORE: _ *list index
            // AFTER:  _ elem{{N - 1}}, elem{{N - 2}}, ..., elem{{0}}
            {entrypoint}:
                push 1
                add
                {&mul_with_size}
                // stack: _ *list (N * (index + 1))

               // <--- Here, we could insert `split swap 1 pop 1` or something like that to actually achieve memory safety.

                add
                // stack: _ (*list + N * index + 1)

                {&self.data_type.read_value_from_memory_pop_pointer()}
                // stack: _ elem{{N - 1}}, elem{{N - 2}}, ..., elem{{0}}

                return

[jan-ferdinand]

Do we want to verify that the memory offsets are of type u32?

Good idea. :+1: Do think split swap 1 pop 1 or split swap 1 push 0 eq assert?

[Sword-Smith]

Do we want to verify that the memory offsets are of type u32?

Good idea. 👍 Do think split swap 1 pop 1 or split swap 1 push 0 eq assert?

We can go with the 2nd option, the one containing an assert instruction. Then we can always hand-optimize later when needed.