[Proposal][Question] Run-time paging of bytecode

[mjessome]

We are investigating the implementation of a paging mechanism for jerryscript bytecode. The goal is to minimize the RAM overhead when executing snapshots by dynamically loading bytecode in fixed-size pages. By doing this we hope that we can execute snapshots that are at least as large as the amount of memory available to the Jerryscript interpreter, and set expectations on the amount of memory available to the executing application.

While planning out a potential implementation of this, I have run into some roadblocks that I would appreciate some help to overcome, those are listed at the end of this post. My thoughts on a potential implementation are as follows:

Saving a snapshot

• Add a new CBC_CODE_FLAGS_SNAPSHOT to each bytecode header. This would make it clear during execution whether we need to account for paging or not.

Loading a snapshot

• In jerry_exec_snapshot() and snapshot_load_compiled_code(), we want to avoid any modification of the snapshot, either in place or into newly allocated blocks.
• Linking of CBC Literals to the global literal table should be done as late as possible.
  • With my understanding, this requires keeping around the literal map (lit_map_p) in RAM so that this can be done efficiently.
• In snapshot_load_compiled_code() we also do not want to recurse on template literals. The loading of this compiled code should be deferred until we need to create an object for these literals.

Executing a snapshot

• In order to enable paging of bytecode, rather than using a pointer to the bytecode, we would need to abstract this away to some concept of a program counter.
• In vm_run(), the vm_frame_ctx_t would be constructed with this program counter for byte_code_p and byte_code_start_p.
• In vm_loop() and the rest of the pipeline, we ask the underlying system to translate that program counter as necessary.

In my design investigation, I see many issues when looking through the execution stages. A few of the larger issues are:

• vm_init_loop() wants to create a literal object for all template literals in the frame. This requires our bytecode to be loaded, which we don't want to load until use. This is also a more general problem with the creation of function object which we do not want to use right away.
• Transparent pointers to ecma_compiled_code_t are used all over the place to access the bytecode, and we would like to abstract this away.
• Trying to maintain the common codepaths for paged and non-paged execution (directly from source, eval(), etc).

My thoughts on a good first step would be to only perform paging of the CBC_INSTRUCTION_LISTS. When loading the snapshot, we would load the literal tables as is currently done, but when setting CBC_SET_BYTECODE_PTR we would set a PC value in there and implement a translation step in vm_loop(). All of the literal tables would still have to sit in memory, but it would allow for paging of the bytecode itself.

Unfortunately, due to things that I've mentioned above I see no clear path to achieving paging of literal tables along with bytecode. It is quite likely that there are some things in Jerryscript that I have overlooked when trying to wrap my head around this, and I would appreciate any feedback on the approach and roadblocks I've mentioned here, as well as thoughts from the Jerryscript team on a feature of this nature.

Thank you

[zherczeg]

I would like to understand more this use case before suggesting any changes. May I have some questions:

• am I understand correctly that byte code is not accessible from ROM, it needs to be loaded into RAM in your system (this is usually not an issue on ARM, we can just access data from ROM)
• do you plan to translate a virtual program counter to a page for every executed instruction (wouldn't that be slow?)
• do you plan this to be a compile time enabled feature?

Personally I would probably mark those points in the where translating is possible (e.g. jumps, add a byte code to mark the end of a page for sequential execution), and would leave the current implementation. This would eliminate the handling of byte code splitting (when a byte code spans across two pages), and would do the costly translation when necessary

[mjessome]

am I understand correctly that byte code is not accessible from ROM, it needs to be loaded into RAM in your system (this is usually not an issue on ARM, we can just access data from ROM)

This is correct, these snapshots need to be loaded out of external flash and it is expensive to be reading from constantly. Paging allows for us to do a single bulk read out of flash into RAM per page, rather than having to reach to external flash on a per-instruction basis.

do you plan to translate a virtual program counter to a page for every executed instruction (wouldn't that be slow?)

Yes, that is the idea. A performance hit is expected, but when not at a page boundary PC translation should be very cheap. The trade off here is that we can enable larger applications and make a best-effort guarantee of RAM available to running apps.

do you plan this to be a compile time enabled feature?

Yes, part of the goal would be to have support enabled at Jerryscript compile time.

Personally I would probably mark those points in the where translating is possible (e.g. jumps, add a byte code to mark the end of a page for sequential execution), and would leave the current implementation.

This is a very interesting approach. It definitely simplifies paging and impact on the interpreter as well. One shortcoming that jumps out to me immediately is that it becomes the snapshot itself dictating page size rather than the interpreter / underlying system. While this probably isn't a massive concern, it potentially locks us into long-term support of these snapshots.

This would eliminate the handling of byte code splitting (when a byte code spans across two pages), and would do the costly translation when necessary

I am looking through vm_loop() and I am not so sure that I follow why bytecode splitting is an issue. Is there any chance that you could elaborate on this?

In addition to the Instruction List paging that we are discussing here, do have any thoughts on what might be done about function literal tables and regular expression objects? As I mentioned in my original post, one of the major hurdles that I see here is the required linking of function literal tables to the global literal table, as well as the fact that (for example) vm_init_loop() wants to load and construct these function objects whether they are used or not. As I read through how these template literals are loaded out of the snapshot and created at runtime, I've been unable to come up with a reasonable way to defer their loading until use.

[zherczeg]

Thank you for explaining the use case. Currently we support ROM execution only if the whole byte code is addressable. This saves a lot of RAM usage.

Yes, that is the idea. A performance hit is expected, but when not at a page boundary PC translation should be very cheap.

I think this is very important. Do you plan to add a macro which inlines the fast case?

While this probably isn't a massive concern, it potentially locks us into long-term support of these snapshots.

Does snapshots created by third party and you have to load them into flashes with various page sizes? Anyway my idea is a byte_code to byte_code translation, where the original byte code comes from a snapshot, and extra bytes are inserted at the end of each page and jump targets are updated. The result is another byte code which supports a specific page size. You can create multiple of these of course. Even the original byte code could be restored from an updated snapshot if necessary (since the translator inserts only a given byte code which is not used by the parser).

I am looking through vm_loop() and I am not so sure that I follow why bytecode splitting is an issue. Is there any chance that you could elaborate on this?

CBC is a variable length byte code. E.g. when we execute a CBC_EXT_SET_SETTER opcode, first we read an opcode byte, which tells that this is an extended opcode, so we read another opcode byte. Then we read two literal arguments. An argument read is similar, so we read a byte, and if the argument is two byte long we read a second byte. During this process we can encounter a page reload at any time. It feels like we need a lot of checks but the impact might be low. I cannot judge it.

In addition to the Instruction List paging that we are discussing here, do have any thoughts on what might be done about function literal tables and regular expression objects?

If you could mark those functions which has not loaded yet, you probably can defer function loading. Currently the function literal is a two byte compressed pointer, which points to the function in the memory. Somehow you need to mark those functions, which are not yet loaded from the flash (perhaps splitting the address space). Then vm_construct_literal_object could realize that its literal object comes from the flash, and construct the function in a different way.

Theoretically regular expressions could be executed from the flash as well, but their execution engine has not prepared for that yet, so I expect some serious rework first.

[rerobika]

Static snapshot was introduced in #2239 which is the correct solution for this problem so IMO, we can finally close this issue.