On transforming Java-like programs into memory-predictable code

ABSTRACT

The ScopedMemory class of the RTSJ enables the organization of objects into regions. This ensures time-predictable management of dynamic memory. Using scopes forces the programmer to reason in terms of locality, to comply with RTSJ restrictions. The programmer is also faced with the problem of providing upper-bounds for regions. Without appropriate compile-time support, scoped-memory management may lead to unexpected runtime errors.

This work presents the integration of a series of compile-time analysis techniques to help identifying memory regions, their sizes, and overall memory usage. First, the tool synthesizes a scoped-based memory organization where regions are associated with methods. Second, it infers their sizes in parametric forms in terms of relevant program variables. Third, it exhibits a parametric upper-bound on the total amount of memory required to run a method. We present some preliminary results showing that semi-automatic, tool-assisted generation of scoped-based code is both helpful and doable.

REFERENCES

• 1: E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. Cost analysis of java bytecode. ESOP, volume 4421 of LNCS, pages 157--172. Springer, 2007.
• 2: E. Albert, S. Genaim, and M. Gómez-Zamalloa. Live heap space analysis for languages with garbage collection. In ISMM, pages 129--138, 2009.
• 3: B. Alpern, S. Augart, S. M. Blackburn, M. Butrico, A. Cocchi, P. Cheng, J. Dolby, S. Fink, D. Grove, M. Hind, et al. The Jikes research virtual machine project: building an open-source research community. IBM Systems Journal, 44(2):399--417, 2005.
• 4: D. Bacon, P. Cheng, and V. T. Rajan. Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for java. In LCTES '03, pages 81--92.
• 5: V. Braberman, F. Fernández, D. Garbervetsky, and S. Yovine. Parametric prediction of heap memory requirements. In ISMM '08, pages 141--150.
• 6: V. Braberman, D. Garbervetsky, and S. Yovine. A static analysis for synthesizing parametric specifications of dynamic memory consumption. Journal of Object Technology, 5(5):31--58, 2006.
• 7: B. Cahoon and K. S. McKinley. Data flow analysis for software prefetching linked data structures in java controller. In PACT 2001, pages 280--291, 2001.
• 8: S. Cherem and R. Rugina. Region analysis and transformation for Java programs. ISMM'04, 2004.
• 9: W. Chin, H. H. Nguyen, S. Qin, and M. Rinard. Memory usage verification for oo programs. In SAS 05, 2005.
• 10: W. N. Chin, H. H. Nguyen, C. Popeea, and S. Qin. Analysing Memory Resource Bounds for Low-Level Programs. In ISMM '08), pages 151--160.
• 11: P. Clauss. Counting solutions to linear and nonlinear constraints through ehrhart polynomials: Applications to analyze and transform scientific programs. In ICS'96, pages 278--285, 1996.
• 12: Ph. Clauss and I. Tchoupaeva. A symbolic approach to bernstein expansion for program analysis and optimization. In CC 04, LNCS, pages 120--133.
• 13: M. Deters and R. K. Cytron. Automated discovery of scoped memory regions for real-time java. In ISMM 02, pages 25--35, 2002.
• 14: M. Ernst, J. Perkins, P. Guo, S. McCamant, C. Pacheco, M. Tschantz, and Ch. Xiao. The Daikon system for dynamic detection of likely invariants. Science of Computer Programming, 2007.
• 15: A. Ferrari, D. Garbervetsky, V. Braberman, P. Listingart, and S. Yovine. Jscoper: Eclipse support for research on scoping and instrumentation for real time java applications. In eTx '05, pages 50--54.
• 16: D. Garbervetsky. Parametric specification of dymamic memory utilization. PhD thesis, DC, FCEyN, UBA, November 2007.
• 17: D. Garbervetsky, Ch. Nakhli, S. Yovine, and H. Zorgati. Program instrumentation and run-time analysis of scoped memory in Java. RV 04, ENTCS, Spain.
• 18: D. Gay and A. Aiken. Language support for regions. In PLDI 01, pages 70--80, 2001.
• 19: James Gosling and Greg Bollella. The Real-Time Specification for Java. Addison-Wesley Longman Publishing Co., Inc., 2000.
• 20: R. Henriksson. Scheduling garbage collection in embedded systems. PhD. Thesis, Lund Institute of Technology, 1998.
• 21: F. Nielson, H. Nielson, and Ch. Hankin. Principles of Program Analysis. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999.
• 22: K. Nilsen. Improving abstraction, encapsulation, and performance within mixed-mode real-time Java applications. In JTRES 2007, pages 13--22.
• 23: F. Pizlo, J. Fox, D. Holmes, and J. Vitek. Real-time Java scoped memory: design patterns and semantics. In ISORC '04, Austria.
• 24: G. Salagnac, Ch. Rippert, and S. Yovine. Semi-automatic region-based memory management for real-time java embedded systems. In RTCSA '07, 2007.
• 25: G. Salagnac, S. Yovine, and D. Garbervetsky. Fast escape analysis for region-based memory management. ENTCS, 131:99--110, 2005.
• 26: A. Salcianu and M. Rinard. Pointer and escape analysis for multithreaded programs. In PPoPP 01, volume 36, pages 12--23, 2001.
• 27: Fridtjof Siebert. Hard real-time garbage-collection in the jamaica virtual machine. rtcsa, 00:96, 1999.
• 28: M. Tofte and J. P. Talpin. Region-based memory management. Information and Computation, 1997.
• 29: R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - A java optimization framework. In CASCON'99, pages 125--135, 1999.