JConsume: Automatic inference of parametric specifications of dynamic memory requirements

The long term goal of our work is to have a tool that is able to start from conventional Java code and automatically produce equivalent Java code that runs under a more predictable memory management together with certificates of memory requirements to guarantee proper execution.

 

Current implementation is fed by a Java application and is able to produce parametric over-approximations of the amount of memory requested by any method of the application.

The tool relies on a simple but useful scoped-based memory manager in which objects are allocated in regions that are associated with methods. Consequently, a region is created at method's entry and is destroyed at its end. When an object is created it has to be allocated in one region but when a region is collected all the objects within that region are also collected.

Under this setting our prototype tool is capable of predicting the size of the memory regions and the amount of memory required to run an application without crashing because running out of memory. This initial prototype is able to analyze single-threaded Java programs provided they do not feature recursion.

 

A view of the most important functional components that appear in our solution is shown in Fig. 1.

 

 

 

Figure 1: Main functional components of our solution.

 

Every component in the diagram is related with a technique we developed or adapted during this work. We can divide the components in two main categories:

 

Region Inference related components and techniques and Memory specification related components and techniques.

 

ˇ         Region inference related components:

o    Region Inference

§  Escape Analysis: to automatically approximate object lifetime

§  Memory Region Inference: to produce memory regions from escape analysis information

o    Region Management

§  Region-based API: to interact with a region-based memory manager

§  Region-based Code Generator: to translate conventional code to region based code using the computed region information

§   

ˇ         Memory specification related components:

 

o    Dynamic Memory utilization analyzer: to obtain parametric specifications of the amount of memory requested by a method

o    Region Size inference: to obtain parametric information about the size of a memory region

o    Memory requirements inference: to obtain parametric certificates of the amount of the dynamic memory required to safely run a method

o    Local Invariant generation: to the generate invariants required by the memory prediction techniques

 

 

The most conceptually challenging problems are the Dynamic memory utilization analysis and the Memory requirements inference and represent the core of this work. The former approximates total allocations made by the application without considering any kind of collection mechanism. The latter computes memory requirements taking into account that there might be some collection mechanism. Both techniques require program invariants. That is why an important part of the work is involved in solving the problem of producing useful invariants.

 

For region inference we develop two escape analysis techniques and implement also a tool to visualize and refine the inferred region information. Using this region information we are able to produce Java code that uses a Region-based API that bypasses the standard Java memory manager. An interesting aspect of the API is that is uses the register/subscriber paradigm that eases the task of object allocation

 

Bibliography

Memory Consumption

Region Inference and Region-based Memory Management

Escape Analysis

Others