Bytecode Rewriting

The synchronization events earlier correspond to bytecode in Java class files. In order to log the events, I need to insert calls to a log function (edu.rice.cs.cunit.tm.SyncPointRecorder) around them. Depending on the event, this is done in several ways.

For all of the Thread methods except sleep and yield, this is easy. I rename the method, e.g. start, to start<wrapper>, and then generate a new method with the old name, i.e. start, that makes the necessary log calls and then forwards to the old method. Another way to do this would be to directly insert the calls into the old methods. That is probably faster, but was also more work. If necessary, I’ll change this.

For Thread.sleep and Thread.yield, as well as for all of the Object methods, this was not an option. They are native methods and cannot be renamed, probably because the name must be the same as in some kind of DLL. Directly inserting bytecode is not possible either, of course, since they do not consist of bytecode.

The strategy that I use here is to add wrapper methods, e.g. notify<wrapper> for the notify method in Object, which make the logging calls and then forward. Then I go through all Java class files (user and run-time library!) and replace calls to the original (i.e. to notify) by calls to the wrapper (i.e. notify<wrapper>).

For synchronized blocks, I go through all Java class files and insert log calls immediately before and immediately after MONITORENTER instructions, and another log call immediately before MONITOREXIT instructions.

Synchronized methods, both static and non-static, are handled by inserting a “try to enter” log call before the call site, as well as inserting an “entered” log call at the beginning of the method and “leaving” log calls at every method exit. Unless, of course, the method is native. In that case, a wrapper method is used, just like for the Object methods mentioned above.

I wrote most of this code last summer already. I have high confidence in the code for everything except for synchronized methods. Even that seems to work on user code, but whenever I instrument the entire Java runtime, I get in trouble. Unfortunately, this is hard to debug, since the errors occur before the Java runtime is completely initialized, which prevents the use any kind of debug output or breakpoint. It is rather frustrating.

By using JPDA and not instrumenting all of the Java runtime, we’re currently hoping to make advances.

Share
Posted in Concurrent Unit Testing | Leave a comment

Print This Post Print This Post  

Currently on my mind

Currently, I am working on monitoring synchronization events in Java programs.

I have identified the following synchronization events:

  • Thread.start
  • Thread.exit
  • Thread.interrupt
  • Thread.stop
  • Thread.destroy
  • Thread.setPriority
  • Thread.join (enter/leave)
  • Thread.sleep (enter/leave)
  • Thread.yield (enter/leave)
  • Object.notify
  • Object.notifyAll
  • Object.wait (enter/leave)
  • synchronized blocks (try/enter/leave)
  • synchronized (non-static) methods (try/enter/leave)
  • synchronized static methods (try/enter/leave)

There are a few more events that I haven’t really considered yet, such as RMI events, volatile variables, and finalizers.

Some of the events above were marked “enter/leave” or “try/enter/leave”. That means that they actually correspond to several events: “enter/leave” generate events when the method is entered and left; “try/enter/leave” generate events when the program tries to enter the corresponding portion of code (“try”), when it has managed to enter it (“enter”), and when it has left it (“leave”).

An external monitor program (“monitor”) is attached to the program to be monitored (“slave”) using JPDA. This has the advantage that the slave runs virtually undisturbed. There are no additional threads, and if the slave crashes or hangs, the monitor still continues to run.

JPDA provides a great deal of access to the slave. Unfortunately, many of these accesses take a long time. I experimented with using JPDA’s monitoring of thread starts and deaths — after 30 minutes of loading DrJava and still not seeing the IDE, I gave up.

Our contingency plan right now is a mixed approach of using both JPDA and bytecode rewriting. The slave stores the events in a list on the slave side, and the monitor attaches to the program several times a second to read and clear it. This minimizes the number of accesses to the slave, but it also keeps the changes to the slave small.

Share
Posted in Concurrent Unit Testing | Leave a comment

Print This Post Print This Post  

Project: Concurrent Unit Testing

The main project I am working on deals with unit testing concurrent programs. I am conducting this research under the supervision of Professor Robert “Corky” Cartwright.

The project focuses on Java programs and makes use of byte code rewriting, custom class loaders, and the Java Platform Debugger Architecture (JPDA).

To ensure deterministic behavior of unit tests, we need to find out when certain synchronization operations (like starting/exiting threads, acquiring/releasing locks, etc.) happen so that we can record them as some sort of trace. Later, we use these traces to generate a large (ideally exhaustive) number of schedules, and later we run programs exactly as described in these schedules.

We will also have to deal with detecting race conditions, as race conditions may lead to non-deterministic behavior; and keeping the schedules of synchronization events up-to-date with source code changes.

Share
Posted in Concurrent Unit Testing | Leave a comment

Print This Post Print This Post  

New Blog

Hello everyone. I’ve finally given in and decided to follow a trend: I’ve started my own blog. I plan to not just ramble on here on my blog, but to actually put it to good use and write about my work. The blog will supplement, if not even replace my pen-and-paper notebook.

The blog is hosted on one of my computers at home. It uses Apache, MySQL, PHP, and WordPress.

If you have any comments or questions, please let me know.

Share
Posted in Uncategorized | Leave a comment

Print This Post Print This Post  

Presentation: Design Patterns for Parsing

Design Patterns for Parsing

Where: SIGCSE 2005
When: February 27, 2005

We provide a systematic transformation of an LL(1) grammar to an object model that consists of

  • an object structure representing the non-terminal symbols and their corresponding grammar production rules,
  • a union of classes representing the terminal symbols (tokens).

We present a variant form of the visitor pattern and apply it to the above union of token classes to model a predictive recursive descent parser on the given grammar. Parsing a non-terminal is represented by a visitor to the tokens. For non-terminals that have more than one production rule, the corresponding visitors are chained together according to the chain of responsibility pattern in order to be processed correctly by a valid token. The abstract factory pattern, where each concrete factory corresponds to a non-terminal symbol, is used to manufacture appropriate parsing visitors.

Our object-oriented formulation for predictive recursive descent parsing eliminates the traditional construction of the predictive parsing table and yields a parser that is declarative and has minimal conditionals. It not only serves to teach standard techniques in parsing but also as a non-trivial exercise of object modeling for objects-first introductory courses.

Share
Posted in OOP Book, Publications | Leave a comment

Print This Post Print This Post  

Paper: Automatic Ad Blocking: Improving AdBlock for the Mozilla Platform

Automatic Ad Blocking: Improving AdBlock for the Mozilla Platform

With: Justin Crites
Where: Rice University, COMP 527 Computer Systems Security
When: December 7, 2004

Advertising on the world wide web is increasingly becoming problematic. In addition to merely being a nuisance, advertisements may also pose a threat to user security. Blocking web advertisements can thus substantially improve the user’s browsing experience.

AdBlock is an open-source plugin for Mozilla browsers that uses regular expressions, an advanced concept unfamiliar to novice users, to block a limited number of HTML elements. This paper describes some of AdBlock’s shortcomings and the remedies we implemented: automatically generating regular expressions, allowing for web updates, and vastly extending the set of blockable elements.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: Automatic Ad Blocking: Improving AdBlock for the Mozilla Platform

Automatic Ad Blocking: Improving AdBlock for the Mozilla Platform

With: Justin Crites
Where: Rice University, COMP 527 Computer Systems Security
When: November 24, 2004

Advertising on the world wide web is increasingly becoming problematic. In addition to merely being a nuisance, advertisements may also pose a threat to user security. Blocking web advertisements can thus substantially improve the user’s browsing experience.

AdBlock is an open-source plugin for Mozilla browsers that uses regular expressions, an advanced concept unfamiliar to novice users, to block a limited number of HTML elements. This paper describes some of AdBlock’s shortcomings and the remedies we implemented: automatically generating regular expressions, allowing for web updates, and vastly extending the set of blockable elements.

Share
Posted in Uncategorized | Leave a comment

Print This Post Print This Post  

Paper: Design Patterns for Parsing

Design Patterns for Parsing

SIGCSE 2005

We provide a systematic transformation of an LL(1) grammar to an object model that consists of

  • an object structure representing the non-terminal symbols and their corresponding grammar production rules,
  • a union of classes representing the terminal symbols (tokens).

We present a variant form of the visitor pattern and apply it to the above union of token classes to model a predictive recursive descent parser on the given grammar. Parsing a non-terminal is represented by a visitor to the tokens. For non-terminals that have more than one production rule, the corresponding visitors are chained together according to the chain of responsibility pattern in order to be processed correctly by a valid token. The abstract factory pattern, where each concrete factory corresponds to a non-terminal symbol, is used to manufacture appropriate parsing visitors.

Our object-oriented formulation for predictive recursive descent parsing eliminates the traditional construction of the predictive parsing table and yields a parser that is declarative and has minimal conditionals. It not only serves to teach standard techniques in parsing but also as a non-trivial exercise of object modeling for objects-first introductory courses.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: Marine Biology Simulation – Nifty Assignment

Marine Biology Simulation – Nifty Assignment

Where: OOPSLA 2004 Educators Symposium
When: October 25, 2004

The Marine Biology Simulation is designed as a final project in an objects-first CS2 course. It provides an entertaining setting that serves as compelling example of the powers of object-oriented design and programming.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Poster: Unit Testing for Concurrent Programs

Unit Testing for Concurrent Programs

Where: Rice University Computer Science Department, Corporate Affiliates Meeting 2004
When: October 18, 2004

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Paper: Assignments for an Objects-First Introductory Computer Science Curriculum

Assignments for an Objects-First Introductory Computer Science Curriculum

Designing an effective curriculum to teach programming and software engineering to beginning students is challenging. An objects-first course prepares students in an excellent way for the requirements in industry and academia by focusing on program design, thereby enabling students to write correct, robust, flexible, and extensible software. This paper outlines the effects of an object-oriented approach on software quality and describes five assignments that can be used as teaching tools in an objects-first course to evaluate and reinforce the students’ understanding.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Paper: Abstract Factories and the Shape Calculator – Nifty Assignment

Abstract Factories and the Shape Calculator – Nifty Assignment

OOPSLA 2004 Educators Symposium

The Shape Calculator is an assignment targeted at CS1 students in an objects-first curriculum. It can serve as a powerful yet entertaining example of the advantages of object-orientation.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Paper: Marine Biology Simulation – Nifty Assignment

Marine Biology Simulation – Nifty Assignment

OOPSLA 2004 Educators Symposium

The Marine Biology Simulation is designed as a final project in an objects-first CS2 course. It provides an entertaining setting that serves as compelling example of the powers of object-oriented design and programming.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: TeachJava – Rice Marine Biology Simulation – Milestone 2

TeachJava – Rice Marine Biology Simulation – Milestone 2

Where: Rice University Computer Science Department, TeachJava
When: June 25, 2004 and July 1, 2005

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: TeachJava – Rice Marine Biology Simulation – Milestone 1

TeachJava – Rice Marine Biology Simulation – Milestone 1

Where: Rice University Computer Science Department, TeachJava
When: June 25, 2004 and July 1, 2005

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: TeachJava – Rice Marine Biology Simulation – Introduction

TeachJava – Rice Marine Biology Simulation – Introduction

Where: Rice University Computer Science Department, TeachJava
When: June 25, 2004 and July 1, 2005

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Presentation: Design Patterns for Marine Biology Simulation

Design Patterns for Marine Biology Simulation
(please contact me for this presentation)

Where: SIGCSE 2004
When: March 6, 2004

We specify and implement a GUI application that simulates marine biological systems by making extensive use of object-oriented design patterns.

The key design patterns are model-view-control, observer/observable, visitor, command, factory method and decorator. These design patterns help delineate the roles and responsibilities of the objects in the system, establish loose coupling between objects and arrange for the objects to communicate and cooperate with one another at the highest level of abstraction. The result is an application that exhibits minimal control flow, yet is powerful, robust, flexible and easy to maintain.

Our work entails a non-trivial redesign of the current AP Computer Science Marine Biology Simulation case study and may serve as a case study for an introductory “object-first” curriculum.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post  

Paper: Design Patterns for Marine Biology Simulation

Design Patterns for Marine Biology Simulation

SIGCSE 2004

We specify and implement a GUI application that simulates marine biological systems by making extensive use of object-oriented design patterns.

The key design patterns are model-view-control, observer/observable, visitor, command, factory method and decorator. These design patterns help delineate the roles and responsibilities of the objects in the system, establish loose coupling between objects and arrange for the objects to communicate and cooperate with one another at the highest level of abstraction. The result is an application that exhibits minimal control flow, yet is powerful, robust, flexible and easy to maintain.

Our work entails a non-trivial redesign of the current AP Computer Science Marine Biology Simulation case study and may serve as a case study for an introductory “object-first” curriculum.

Share
Posted in Publications | Leave a comment

Print This Post Print This Post