Yes I think that’s a very good suggestion. Should definitely help
I’m editing the spec now. How would that go?
If this were to be applied to the network I would really suggest to make it into a separate EIP, required by 2315, otherwise mixing different restrictions into a feature EIP sounds weird.
I could be convinced on the contrary though.
2 Likes
What’s the current thoughts about tail calls and e.g. @chfast’s suggestion of TAILJUMPSUB? I’ve personally been wanting to implement tail call optimizations in solidity for a while (although I think there’s no consensus about how beneficial they woud be - however, e.g. potential more functional languages might suffer even more from lacking the possibility of such an optimization). So I’m wondering, since the current proposal reads like that will no longer be possible when using subroutines.
(or wait: actually BEGINSUB JUMPDEST ... RETURNSUB and then jumping to that jumpdest from another subroutine would work? If so, then that would encourage jumping into subroutines for this, which @axic wants to avoid; I need to read the proposal a bit more carefully)
EDIT: ok, reading the proposal a bit more carefully makes me realize that the only benefit tail call optimizations would bring would be to save one slot in the return_stack - apart from that the combination of JUMPSUB RETURNSUB should do exactly what I want already. And the size of return_stack is probably a reasonable limitation, so further support for tail call optimizations might really not be needed.
So far as preventing jumping into subroutines goes – my problem remains that it has no semantics. It’s syntax, not mechanism, and the Rationale for this proposal is the least amount of mechanism needed to implement subroutines.
Throughout this discussion my take becomes stronger that syntactic restrictions should be no part of the specification of the opcodes.
- Opcodes control state-machine transitions, and should be constrained only by the validity of the states.
This lack of syntax should pose no obstacles to compilers from high level languages to EVM code – they can enforce whatever syntax they like. I understand that when compiling from EVM to lower level code this matters, but I’ve generally seen compilers just “throw up their hands” and generate bad code when their input has too little structure. We can avoid this if we want …
We may later want to propose a separate EIP for a more-constrained EVM. It can enforce code structure at deployment time that is better suited for streaming compilation and other purposes. So along the lines of EIP-615, taking recent conversations and experience with EIP-2315 into account.
Subroutine map with capped executable code size
Current max size of deployable code is 24576 (0x6000). We propose to also limit the size of executable code to 2x the above limit, i.e. 49152 (0xc000).
This gives nice properties:
- instruction offset in code fits 16-bit value,
- code size fits 16-bit value.
Possible implementations of subroutine maps
Shadow array
Max memory footprint: 0xc000
We create a byte array of the size of the code shadowing the instructions in the code. The array is initially filled with zeros.
- a
JUMPDESTinstruction is indicated by0x80mask in the shadow array.
To validate jump destination:(shadow_array[location] & 0x80) != 0. - a
BEGINSUBinstruction is indicated by0x40mask in the shadow array. - the size of a subroutine is encoded in the remaining 6-bits using variable-length encoding analogous to LEB128. Examples:
40- subroutine of length zero,5f- subroutine of length 31 (0x1f), the max length that fits single byte encoding,6001- subroutine of length 32 (0x00+ 2^5 *0x01)7f- subroutine of length 1023 (0x1f+ 2^5 *0x1f), the max length that fits two-byte encoding,6081- subroutine of length 32 followed by aJUMPDESTinstruction.
Bitset with linear search
Max memory footprint: 0xc000 / 4 == 12288
We create a bitset indicating an instruction is JUMPDEST and another bitset indicating an instruction is BEGINSUB. During execution we keep track of where the current subroutine starts.
To validate if a jump stays within a subroutine:
- when jumping backwards, just check if
juspdest_location >= current_subroutine_begin, - when jumping forward, find the beginning of the next subroutine starting from current
PC(where the jump is). This is done by linear search in subroutine bitset. We can process 64 bits at a time by using 64-bit load and checking if value is not zero. This may be optimized further using SSE2 (128-bit) or AVX (256-bit).
In worst case we need 0xc000 / 64 == 768 comparisons.
Span map
Max memory footprint: 0xc000 * 2 == 98304 + jumpdest map.
We keep an array of all BEGINSUB instructions offsets. Single value is uint16 and values are already sorted.
To verify JUMPSUB check if location is in the array using binary search.
When entering a subroutine remember subroutines begin and end location. The end location is the next value in the array.
To verify if a jump stays within a subroutine check if jumpdest_location is between subroutine’s begin and end.
I’m not able to prove it, but that was exactly my intention.
The deploy-time code validation is the precise boundary I don’t want to cross. See EIP-2315 "Simple Subroutines for the EVM" - Analysis - #19 by AlexeyAkhunov.
One detail that you don’t mention explicitly, but might be worth to note: I believe all three implementations would require that JUMPSUB pushes current subroutine start into control stack togetter with return location, so that after RETURNSUB we can remember to which one we returned.
Here is a complete (untested) C++ implementation of a variant of @chfast’s idea of the shadow array. It does not use a complicated variable-length encoding and needs less memory, though. It needs two bit fields with code_size number of bits: The first stores at bit i whether code[i] is push data or not. The second stores the length of each subroutine such that the length of the subroutine that starts at byte i is stored in binary starting at the ith bit.
It does not need a stop marker for the length encoding because it reads the length bit-by-bit and checks if the end of the subroutine has been reached already. This can easily be removed by making the size of the bitset twice as large or by using a more complicated (prefix-free) number encoding.
This PR incorporates the fix to prevent the EVM from stepping (as opposed to jumping) to BEGINSUB – JUMPSUB transfers control to the instruction after BEGINSUB; BEGINSUB itself aborts. This PR does not prevent “jumping into subroutines.”
PR
EIP
it looks like the example is wrong https://github.com/ethereum/EIPs/blob/1e3659c86d284473fde869a7a8129c5e7af6fe7e/EIPS/eip-2315.md#subroutine-at-end-of-code. BeginSub shouldn’t be present. Right?
Here is a specification for the restrictions on the jump and jumpi opcodes: https://github.com/ethereum/EIPs/pull/2663
(the “do not walk into subroutines” part is already merged into EIP-2315)
Subroutine maps help answering following questions (sometimes also by using information in the code itself):
- is this instruction a
JUMPDEST? - is this instruction a
BEGINSUB? - what is the length of this subroutine?
For subroutine maps we have two classes of implementations (as identified with @chriseth).
- “Code shadow array”
The size is proportional to the code length. We believe the variant with the lowest memory footprint would use 2 bits per byte of code (proposed by @chriseth). Up to one byte per byte of code presented as “Shadow array” in EIP-2315 "Simple Subroutines for the EVM" - Analysis - #41 by chfast. This class of implementations is generic and does not depend on the discussed executable code length cap. - “Span map”
This is a map/set of subroutine begins/ends but can be efficiently stored as an array and binary search can be used to lookup values in the map. The size is proportional to the number of subroutines. But in worst case the code may be only 1-byte long subroutines.
This depends on the code length cap because with the cap we can useuint16type, otherwise we needuint32. In the worst case withuint32type the memory footprint is 4x the code length.
True. I actually did not realized that I need to remember the all the subroutines on the control stack.
This is however not needed for “span map”. One binary search is enough to find both begin and end of a subroutine.
That’s what I meant here:
Proof of concept / draft implementation, with an implementation of the shadow-array analysis can be found here: https://github.com/ethereum/go-ethereum/pull/21161
Coming back around to this, do we know what the changes to the Yellow paper will be to support this? When I went into it recently I found that even BEGINSUB would add more to the YP than I’d like. I’d be more sympathetic if this feature can be expressed succinctly there.
Also, one reason I don’t like this feature is that it prevents other means of implementing subroutines – e.g. I think Christian has shown that in some cases leaf routines can be implemented more efficiently with JUMP than JUMPSUB.
I don’t know how difficult it would be to add this to the YP, as I never edited it myself. But I personally don’t see much interest in the community to keep the YP up to date nowadays - it’s never considered when EIPs are being proposed / discussed, and the most recent version only partially covers Petersburg (the fork from February 2019)
It wouldn’t prevent ignoring JUMPSUB by the compiler and implementing all the subroutines with only JUMPs.
Mixing two kinds of subroutines in one contract (JUMPSUB subs and JUMP subs) doesn’t sound like a good idea in general to me, for the reasons pointed out in the original analysis: difficulty to test all the edge cases of such complicated contract, complications for the static analysis, complications for finding limits of each subroutine if we want to merklize them separately or runtime-analyze them separately.
Nick Saves endeavors to keep the YP up to date - it’s the only spec we have. Actually editing the TeX is difficult, but getting an idea of how much work a new feature would be isn’t so bad.
At the least, we need a PR to the EIP, if there isn’t one I missed. I expect this will be a pain to specify, as currently there is almost no structure specified for bytecode and it amounts to a huge expansion of illegal jump locations. The EIP will also need to explain how to implement this efficiently.
Part of my change of heart here is that although a check for this is needed at runtime (and in my experience checking syntactic constraints at runtime is trouble) a compiler from EVM code can assume that it never happens and take advantage of that promise inside of the subroutine. (And I still wish I’d never introduced beginsub, but stuck with the bare minimum.)