Project: Encoding Immutable State In Object Addresses

Overview

In Section 4.3 of our paper on scanning techniques, we made a neat observation: that the address of a TIB (a type object) could encode immutable state held within the TIB. This is a cool (and strange) idea. For example, one of the things a TIB does is encode where the pointers are within an object. This information is immutable in Java, since the type itself cannot change, so the locations of the reference fields will never change once the type is created. The insight we had was that by playing careful tricks with the allocation of the TIB, we could encode information in the address of the TIB. By doing this, that information could be discovered simply by looking at the TIB pointer, without having to dereference the TIB pointer and find that information within the TIB. The allocation ‘trick’ was simply to allocate more space than necessary and then ‘slide’ the TIB within the generous space until its address matched the desired value, and then settle on that address as the address of the TIB. This approach meant that we wasted some space on each TIB allocation, but since there is only one TIB per type and there are vastly more objects per type, it was cost-effective. It turned out to be a useful optimization that we still use today.

This project extends that idea to be far more general, encoding such information in the pointer of every object. It does this by using a different allocation ‘trick’. Rather than sliding the object within a generous space (to select low-order bits in the object’s address), we use multiple mappings of virtual memory. Then the high order bits of the object will encode the relevant information (such as object size, location of pointers, etc). Because multiple virtual addresses can map to a given physical address, we can avoid losing space or locality, by multiply mapping each physical page and chosing the appropriate virtual page according to the property we want to encode.

Themes

Garbage collection
Programming Languages

Requirements

Coding This project will not involve a large amount of coding, but will depend some very careful performance-critical coding, most likely in Rust, but possibly in C++.
Analysis This project will involve detailed performance analysis.

Project Length

This project is probably a one-semester project.

Project Outputs

If successful, this project will result in an idea that becomes used in production virtual machines, and results in a research publication.

References

This is a fairly novel problem. I have to do more work to gather some references…