-
1. Re: CFG necessary?
Hi Jahwan,
Jahwan Kim wrote:
Now I'm browsing through byteman source code, thinking about how to implement my goals
(which is a bit vague).
Well kudos for diving in!
Jahwan Kim wrote:
I'm particularly interested in how byteman implemented $^ as well as $!, and what I saw in
the code is different from what I imagined before looking into the code. In a nutshell,
I couldn't really understand why CFG should play a central role. It's well-commented, so
let me ask a simple question: What's the irreplaceable reason that CFG should be used?
Is it primarily for synchronized blocks?
Hmm, yes, in software window dressing usually belies the scaffolding that holds it up :-)
Well, even more kudos for getting this deep into the code and, once again, asking the right question (n.b. this question and answer probably ought to be posted on the Byteman Development forum but I'll answer here as you have asked here).
Synchronized blocks are one half of the necessity for class CFG. The other half is exception flow. How they combine is critical to correct program transformation. Actually there is a third (and not strictly necessary) half to this necessity which is the single pass visitor model employed by ASM (there's a historical wrinkle to that too) but I'll come to that later.
In essence Byteman's injection strategy is fairly simple -- it plants a callout into the trigger method, passing Object this (or null) plus an Object array containing local and parameter values into the call. Any values which might be updated are returned in said Object array and written back into the local or parameter slots. The thing which complicates this simple injection model is the need to handle the three types of exceptions which might flow out of the planted callout.
ExecuteException represents an error in the rule code. This needs to be rethrown from the trigger method to its caller. So, exception flow for this exception has to bypass and code following the callout and also bypass any exception handlers which wrap the injection point prior to injection. This is normally achieved by adding an exception region around the injected code and routing the exception flow to a handler tacked on to the end of the trigger method bytecode which rethrows the ExecuteException.
ReturnException is thrown when the rule action executes a RETURN. It contains a value which needs to be returned from the top-level of the trigger method. So, It also needs to bypass code following the callout and existing exception handlers. So, this is also achieved by adding an exception region around the injected code and routing the exception flow to a handler tacked on to the end of the trigger method bytecode. Only this time the handler unwraps the return value embedded in the ReturnException and ... returns it.
ThrowException is thrown when the rule action executes a THROW. It is normally handled in the same way, route to a handler at the end of the trigger method only this time unwrap the exception embedded in the ThrowException and rethrow that embedded exception.
The problem with this simple scheme is that the exception flow might take you out of what was a synchronized region in the original code. Now a synchronized region manifests as a region of the bytecode bounded by a monitorenter bytecode at the bytecode which represents the start of the block and one or more monitorexit bytecodes which represent the places where control flow inside the synchronized region can leave the region. The reason there may be more than one monitorexit for a given monitorenter is that control can leave the synchronized region via both normal control flow and via exception control flow.
There is normally only one control flow exit (although you may sometimes see more if for example on branch of an if executes a return and another drops through to code which follows the synchronized region). Each of these exit paths can easily be traced through and the monitorexit associated with a unique outstanding monitorenter. The normal control flow linkage in the basic block graph of the CFG makes this traversal simple.
The harder part is dealing with exceptions which flow out of the synchronized region into handlers beyond the end of the region The Java compiler has to ensure that this flow performs a monitorexit on the way to the handler. However, it cannot do that in the handler since exceptions outside the synchronized region might also reach the handler. So, it plants an intermediate handler just after the end of the synchronized region which executes the monitorenter and then rethrows the exception. The intermediate handler is wrapped in an exception region which ensures the rethrow reaches the correct outer handler. Just to make it more complicated note that the flow might cross multiple synchronized region boundaries, in which case a monitorexit+rethrow handler is needed for each such crossing.
So, this is really what CFG is for. If the code injected by Byteman lies inside one or more synchronized regions then Byteman has to route each of the three Byteman exceptions through intermediate monitorexit+rethrow handlers in order to ensure that the relevant objects are unlocked on the way to the top-level handler. I simplified this task by making ThrowException and ReturnException subtypes of ExecuteException. So, intermediate handlers only need to catch and rethrow ExecuteException (all 3 exceptions are handled the same way by an intermediate handler).
So, why did I mention the single pass visitor model? Well, when I originally implemented Byteman I was very taken with the performance of ASM, in particular the visitor model which means that you don't have to process any bits of the bytecode you are not interested in. That usually means less code, faster code and less data turnover than a library like, say, Javassist which unpacks the bytecode to a rich representation of the whole class, including the the ability to randomly access all instructions in a given method, and then repacks it into bytecode once you have finished munging your changes into the class. You can probably see where I am heading with this. The Javassist unpack and browse the model makes it easy to associate monitorenters with monitorexits and build up a set of (possibly nested) bytecode regions corresponding to the synchronized blocks in the source. It also makes it easier to overlay try catch and handler regions on the nested synchronized regions. You can do both these tasks incrementally knowing in advance what instructions you need to account for. With ASM's single pass model it's hard to know whetehr you have seen all possible exits for a given enter or when you are going to see the handler code for a given try catch region. I had to invent some rather complex one-pass algorithms to track precisely this information (method carry_forward is the driver that does the bulk of work needed to do this accounting). So, I made life rather difficult for myself (and now for you) by using ASM.
What was the historical wrinkle? Well, one of the things I needed to do when I moved Byteman from working on JDK5 to working only on JDK6 was cope with the deprecated (pre-JDK6) JSR instruction. So, I had to prefix all Byteman bytecode traversals with an ASM bytecode transformer called JSRInliner. This replaces jumps to shared handler code (that's what JSR does) with inline copies of the handler code. Class JSRInliner unpacks the full bytecode sequence and does surgery on it -- there is no other way it can work. In other words it pays the price of replacing the one pass model I so prized with the unpack and browse model used by other bytecode libraries. So, I guess I could have used the same approach and made life easier for myself. Ah well, by then I had my algorithms working and had no desire to rewrite such complex code.
n.b. I am glad you mentioned how well commented it is. There is a very good reason for that. No one who builds code based on algorithms even half as complex as these ones can afford to omit comments. Every programmer, no matter how gifted, is guaranteed to forget critical details of a large piece of code if s/he doesn't look at it for a few weeks (maybe months for a true genius). That's just as true of me, never mind the fact that I designed the code. So, the comments are there for my needs as much as for anyone else. I probably ought to have written more :-)
I hope the info above makes it clearer what the code is doing, helps you to understand how it works and lets you enjoy reading deeper. It's one of the great joys of open source that you occasionally find someone interested enough that you are able to share code like this with them. So, thank you very much for taking an interest in it.
regards,
Andrew Dinn
-
2. Re: CFG necessary?
Hi Andrew,
Thanks for the detailed reply.
Your explanation makes perfect sense, esp. in the presence of ASM's one-pass visitor model,
since a state machine of some kind is necessary to keep track of something under ASM.
(Unfortunately I haven't had chance to really delve into CFG.java, I must confess.)
Now this fact didn't come to my mind before asking, because I haven't thought about what happens
when an exception happens in the rule code itself. Well, that shouldn't happen for the goals I have in mind.
(And actually I plan to catch an exception in the rule code and redirect it to some error handler,
instead of throwing it back to the trigger method.)
I guess it is not necessary to keep track of the control flow, If no exception is assumed
to flow out of rule code.
Best,
Jahwan
P.S. I totally agree with your opinion about comments! Several months is enough for me
to exclaim "Who wrote this code?"