[android-developers] Re: VerifyError reloaded
On Sep 25, 12:33 pm, Dirk wrote: > The project I am trying to build and run contains only Java sources > (no libraries). Therefore, I assume, that if these are compiled > successfully, they would pass the verification process. But during > runtime, I get the following error: > > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: invalid switch start: at > 8, switch offset -31132, count 34530 > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: rejected Lcom/espertech/ > esper/epl/generated/EsperEPL2GrammarParser > $DFA156;.specialStateTransition (ILorg/antlr/runtime/IntStream;)I This sounds interesting. Can we get a copy of the APK? (Easiest way is probably to file a bug on b.android.com and attach it there.) -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
VerifyError occurs for two basic reasons: 1) An error in the bytecodes. 2) An error due to a mismatch between two different class files. It's really unusual to find a case for reason (1) but you apparently "lucked out". If this is code that runs OK in a regular Java environment but fails on Android then I would suspect a bug in the Android verifier (or perhaps a "feechur" -- some sort of limitation/restriction). Apparently fadden suspects a bug in the Android verifier as well. On Sep 25, 2:33 pm, Dirk wrote: > Hi, > I'm currently trying to port the famous complex event processing > runtime "Esper" to the Android (2.2) platform and am facing a > VerifyError, which I - although reading several other post on > VerifyErrors - do not understand. > > The project I am trying to build and run contains only Java sources > (no libraries). Therefore, I assume, that if these are compiled > successfully, they would pass the verification process. But during > runtime, I get the following error: > > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: invalid switch start: at > 8, switch offset -31132, count 34530 > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: rejected Lcom/espertech/ > esper/epl/generated/EsperEPL2GrammarParser > $DFA156;.specialStateTransition (ILorg/antlr/runtime/IntStream;)I > 09-25 18:33:27.549: WARN/dalvikvm(300): Verifier rejected class Lcom/ > espertech/esper/epl/generated/EsperEPL2GrammarParser$DFA156; > 09-25 18:33:27.559: DEBUG/AndroidRuntime(300): Shutting down VM > 09-25 18:33:27.559: WARN/dalvikvm(300): threadid=1: thread exiting > with uncaught exception (group=0x4001d800) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): FATAL EXCEPTION: main > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): java.lang.VerifyError: > com.espertech.esper.epl.generated.EsperEPL2GrammarParser$DFA156 > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.epl.generated.EsperEPL2GrammarParser.(EsperEPL2GrammarParser.java: > 28870) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.epl.generated.EsperEPL2GrammarParser.(EsperEPL2GrammarParser.java: > 338) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.epl.parse.ParseHelper.parse(ParseHelper.java:108) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.core.EPAdministratorImpl.compileEPL(EPAdministratorImpl.java: > 299) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.core.EPAdministratorImpl.createEPLStmt(EPAdministratorImpl.java: > 142) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.espertech.esper.core.EPAdministratorImpl.createEPL(EPAdministratorImpl.java: > 94) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > esper.android.EsperAndroidTest.onCreate(EsperAndroidTest.java:39) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.Instrumentation.callActivityOnCreate(Instrumentation.java: > 1047) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.ActivityThread.performLaunchActivity(ActivityThread.java: > 2627) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.ActivityThread.handleLaunchActivity(ActivityThread.java: > 2679) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.ActivityThread.access$2300(ActivityThread.java:125) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.ActivityThread$H.handleMessage(ActivityThread.java:2033) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.os.Handler.dispatchMessage(Handler.java:99) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.os.Looper.loop(Looper.java:123) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > android.app.ActivityThread.main(ActivityThread.java:4627) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > java.lang.reflect.Method.invokeNative(Native Method) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > java.lang.reflect.Method.invoke(Method.java:521) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.android.internal.os.ZygoteInit > $MethodAndArgsCaller.run(ZygoteInit.java:868) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > com.android.internal.os.ZygoteInit.main(ZygoteInit.java:626) > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > dalvik.system.NativeStart.main(Native Method) > > The source of "EsperEPL2GrammarParser" is quite big ( > 40,000 lines) > and so is the above mentioned inner class DFA156, which mainly > contains a switch-statement (> 60 cases) and each case contains > several (> 50?) if-then-else statements. Just an idea ... when reading > the error message above (invalid switch start: at 8, switch offset > -31132, count 34530) my alarm bells ring, cause some values around > 32768 (16 bit range) always make me nervous. > > Nevertheless, I am confused with this VerifyError and would appreciate > any help getting closer to the error's source. What can I do to > encirc
[android-developers] Re: VerifyError reloaded
Hi, thanks for the replies and sorry for the delay, it took me some time to extract the application part which throws the VerifyError. Sure you can have access to the APK and to the sources as well - if they are of any need. The APK can be found here: http://vsis-www.informatik.uni-hamburg.de/projects/jadex-android/AndroidVerifyTest.apk And the whole eclipse project, containing the sources, here: http://vsis-www.informatik.uni-hamburg.de/projects/jadex-android/AndroidVerifyTest.rar Before filing a bug, I would feel much better if someone else could have a look and approve that there's really something not working as it should. If you have a look at the sources, don't let all the classes confuse you, the Activity test.verify.AndroidVerifyTestActivity is the entrypoint which simply instantiates the Class upon which the VerifyError is throws. All the other classes and packages are just dependencies. Thanks in advance, Dirk On 28 Sep., 04:06, DanH wrote: > VerifyError occurs for two basic reasons: > > 1) An error in the bytecodes. > 2) An error due to a mismatch between two different class files. > > It's really unusual to find a case for reason (1) but you apparently > "lucked out". > If this is code that runs OK in a regular Java environment but fails > on Android then I would suspect a bug in the Android verifier (or > perhaps a "feechur" -- some sort of limitation/restriction). > > Apparently fadden suspects a bug in the Android verifier as well. > -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Hi, thanks for the replies and sorry for the delay, it took me some time to extract the application part which throws the VerifyError. Sure you can have access to the APK and to the sources as well - if they are of any need. The APK can be found here: http://vsis-www.informatik.uni-hamburg.de/projects/jadex-android/AndroidVerifyTest.apk And the whole eclipse project, containing the sources, here: http://vsis-www.informatik.uni-hamburg.de/projects/jadex-android/AndroidVerifyTest.rar Before filing a bug, I would feel much better if someone else could have a look and approve that there's really something not working as it should. If you have a look at the sources, don't let all the classes confuse you, the Activity test.verify.AndroidVerifyTestActivity is the entrypoint which simply instantiates the Class upon which the VerifyError is throws. All the other classes and packages are just dependencies. Thanks in advance, Dirk On 28 Sep., 04:06, DanH wrote: > VerifyError occurs for two basic reasons: > > 1) An error in the bytecodes. > 2) An error due to a mismatch between two different class files. > > It's really unusual to find a case for reason (1) but you apparently > "lucked out". > If this is code that runs OK in a regular Java environment but fails > on Android then I would suspect a bug in the Android verifier (or > perhaps a "feechur" -- some sort of limitation/restriction). > > Apparently fadden suspects a bug in the Android verifier as well. > > On Sep 25, 2:33 pm, Dirk wrote: > > > Hi, > > I'm currently trying to port the famous complex event processing > > runtime "Esper" to the Android (2.2) platform and am facing a > > VerifyError, which I - although reading several other post on > > VerifyErrors - do not understand. > > > The project I am trying to build and run contains only Java sources > > (no libraries). Therefore, I assume, that if these are compiled > > successfully, they would pass the verification process. But during > > runtime, I get the following error: > > > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: invalid switch start: at > > 8, switch offset -31132, count 34530 > > 09-25 18:33:27.549: WARN/dalvikvm(300): VFY: rejected Lcom/espertech/ > > esper/epl/generated/EsperEPL2GrammarParser > > $DFA156;.specialStateTransition (ILorg/antlr/runtime/IntStream;)I > > 09-25 18:33:27.549: WARN/dalvikvm(300): Verifier rejected class Lcom/ > > espertech/esper/epl/generated/EsperEPL2GrammarParser$DFA156; > > 09-25 18:33:27.559: DEBUG/AndroidRuntime(300): Shutting down VM > > 09-25 18:33:27.559: WARN/dalvikvm(300): threadid=1: thread exiting > > with uncaught exception (group=0x4001d800) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): FATAL EXCEPTION: main > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): java.lang.VerifyError: > > com.espertech.esper.epl.generated.EsperEPL2GrammarParser$DFA156 > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.epl.generated.EsperEPL2GrammarParser.(EsperEPL2GrammarParser.java: > > 28870) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.epl.generated.EsperEPL2GrammarParser.(EsperEPL2GrammarParser.java: > > 338) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.epl.parse.ParseHelper.parse(ParseHelper.java:108) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.core.EPAdministratorImpl.compileEPL(EPAdministratorImpl.java: > > 299) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.core.EPAdministratorImpl.createEPLStmt(EPAdministratorImpl.java: > > 142) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > com.espertech.esper.core.EPAdministratorImpl.createEPL(EPAdministratorImpl.java: > > 94) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > esper.android.EsperAndroidTest.onCreate(EsperAndroidTest.java:39) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.Instrumentation.callActivityOnCreate(Instrumentation.java: > > 1047) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.ActivityThread.performLaunchActivity(ActivityThread.java: > > 2627) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.ActivityThread.handleLaunchActivity(ActivityThread.java: > > 2679) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.ActivityThread.access$2300(ActivityThread.java:125) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.ActivityThread$H.handleMessage(ActivityThread.java:2033) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.os.Handler.dispatchMessage(Handler.java:99) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.os.Looper.loop(Looper.java:123) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > android.app.ActivityThread.main(ActivityThread.java:4627) > > 09-25 18:33:27.589: ERROR/AndroidRuntime(300): at > > java.lang.refle
[android-developers] Re: VerifyError reloaded
On Sep 28, 11:28 am, Dirk wrote: > Before filing a bug, I would feel much better if someone else could > have a look and approve that there's really something not working as > it should. It's a bug in the verifier. Specifically, dvmCheckSwitchTargets is treating the switch table offset as a 16-bit value when it's actually a 32-bit value. The switch statement data starts at 0x8664. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Hej fadden, I only have a glance of what might be wrong, but I'll post that bug (and your comment) on the Android bug list. Thank you very much, I'll really appreciate this ! Cheers Dirk On 28 Sep., 22:53, fadden wrote: > On Sep 28, 11:28 am, Dirk wrote: > > > Before filing a bug, I would feel much better if someone else could > > have a look and approve that there's really something not working as > > it should. > > It's a bug in the verifier. Specifically, dvmCheckSwitchTargets is > treating the switch table offset as a 16-bit value when it's actually > a 32-bit value. The switch statement data starts at 0x8664. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Just for the sake of completeness: In order to get around the problem, I tried to replace the whole switch-statement with lots of if-elseif statements. Unfortunately, another problem arose. The Verifyer now says: 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting large method (regs=127 count=34916) There's already another thread on this topic: http://groups.google.com/group/android-developers/browse_thread/thread/e2a36821d0476057/b549ddd81b5e8ca7?lnk=raot Maybe one should keep this issue in mind when fixing the Verifier bug, cause they seem to go hand in hand. Cheers Dirk The method has several thousand lines ( ~ 3000 to 9000 lines, depending on the formatting) of code On 28 Sep., 22:53, fadden wrote: > On Sep 28, 11:28 am, Dirk wrote: > > > Before filing a bug, I would feel much better if someone else could > > have a look and approve that there's really something not working as > > it should. > > It's a bug in the verifier. Specifically, dvmCheckSwitchTargets is > treating the switch table offset as a 16-bit value when it's actually > a 32-bit value. The switch statement data starts at 0x8664. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Java has some fairly arbitrary restrictions on the size of programs. Most are fairly reasonable, but one that isn't so much is the one that limits the number of bytecodes in a method to 65535. (Curiously, methods can have more.) In general, a verifier should be able to handle any large method up to the 65535 limit without choking, but there are a number of oddball (and not so oddball) cases where Sun's can't, and most other verifiers have similar Achilles heels. (Eg, I wrote the "BigUglyMethod" testcase that breaks Sun's verifier, even though it's only a few hundred lines long.) (And rather than respond by fixing the verifier, Sun did a major redesign of the bytecode file format to circumvent the problem. Though curiously they never did the very minor modifications that would have been required to lift the 65535 limitation.) Anyway, it's likely that this program is bumping into several limits in the Dalvik. The best thing to do would be to figure out some way to break up the mongo method that's causing these problems. On Sep 29, 1:32 pm, Dirk wrote: > Just for the sake of completeness: > In order to get around the problem, I tried to replace the whole > switch-statement with lots of if-elseif statements. > Unfortunately, another problem arose. The Verifyer now says: > > 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting > large method (regs=127 count=34916) > > There's already another thread on this > topic:http://groups.google.com/group/android-developers/browse_thread/threa... > > Maybe one should keep this issue in mind when fixing the Verifier bug, > cause they seem to go hand in hand. > > Cheers Dirk > > The method has several thousand lines ( ~ 3000 to 9000 lines, > depending on the formatting) of code > On 28 Sep., 22:53, fadden wrote: > > > On Sep 28, 11:28 am, Dirk wrote: > > > > Before filing a bug, I would feel much better if someone else could > > > have a look and approve that there's really something not working as > > > it should. > > > It's a bug in the verifier. Specifically, dvmCheckSwitchTargets is > > treating the switch table offset as a 16-bit value when it's actually > > a 32-bit value. The switch statement data starts at 0x8664. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Thanks for the insights. I broke up the method into several smaller ones, and now it works ! ... at least until it's time to regenerate the class (the class is automatically generated by ANTLR, a parser generator). On 29 Sep., 23:15, DanH wrote: > Java has some fairly arbitrary restrictions on the size of programs. > Most are fairly reasonable, but one that isn't so much is the one that > limits the number of bytecodes in a method to 65535. (Curiously, > methods can have more.) > > In general, a verifier should be able to handle any large method up to > the 65535 limit without choking, but there are a number of oddball > (and not so oddball) cases where Sun's can't, and most other verifiers > have similar Achilles heels. (Eg, I wrote the "BigUglyMethod" > testcase that breaks Sun's verifier, even though it's only a few > hundred lines long.) (And rather than respond by fixing the verifier, > Sun did a major redesign of the bytecode file format to circumvent the > problem. Though curiously they never did the very minor modifications > that would have been required to lift the 65535 limitation.) > > Anyway, it's likely that this program is bumping into several limits > in the Dalvik. The best thing to do would be to figure out some way > to break up the mongo method that's causing these problems. > > On Sep 29, 1:32 pm, Dirk wrote: > > > Just for the sake of completeness: > > In order to get around the problem, I tried to replace the whole > > switch-statement with lots of if-elseif statements. > > Unfortunately, another problem arose. The Verifyer now says: > > > 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting > > large method (regs=127 count=34916) > > > There's already another thread on this > > topic:http://groups.google.com/group/android-developers/browse_thread/threa... > > > Maybe one should keep this issue in mind when fixing the Verifier bug, > > cause they seem to go hand in hand. > > > Cheers Dirk > > > The method has several thousand lines ( ~ 3000 to 9000 lines, > > depending on the formatting) of code > > On 28 Sep., 22:53, fadden wrote: > > > > On Sep 28, 11:28 am, Dirk wrote: > > > > > Before filing a bug, I would feel much better if someone else could > > > > have a look and approve that there's really something not working as > > > > it should. > > > > It's a bug in the verifier. Specifically, dvmCheckSwitchTargets is > > > treating the switch table offset as a 16-bit value when it's actually > > > a 32-bit value. The switch statement data starts at 0x8664. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
On Sep 29, 11:32 am, Dirk wrote: > In order to get around the problem, I tried to replace the whole > switch-statement with lots of if-elseif statements. > Unfortunately, another problem arose. The Verifyer now says: > > 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting > large method (regs=127 count=34916) I fixed that one too while I was at it. The limit was intended to prevent the verifier from soaking up huge amounts of memory, but (a) the limit is too low, and (b) there are better mechanisms in the system for doing that. So now it's just a warning that says, "hey, this is huge". With both fixes in place, the original code passes. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Of course, the real problem is that the verifier is mis-designed. I'm guessing it uses reference chains. I redid the one for iSeries to use sparse bit vectors and cut the heap requirements by about a factor of 100, and made it much faster as well. On Sep 30, 12:29 pm, fadden wrote: > On Sep 29, 11:32 am, Dirk wrote: > > > In order to get around the problem, I tried to replace the whole > > switch-statement with lots of if-elseif statements. > > Unfortunately, another problem arose. The Verifyer now says: > > > 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting > > large method (regs=127 count=34916) > > I fixed that one too while I was at it. The limit was intended to > prevent the verifier from soaking up huge amounts of memory, but (a) > the limit is too low, and (b) there are better mechanisms in the > system for doing that. So now it's just a warning that says, "hey, > this is huge". > > With both fixes in place, the original code passes. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
That was fast ! Thank you. Do you know if the fix will be included in the next Android version ? On 30 Sep., 19:29, fadden wrote: > On Sep 29, 11:32 am, Dirk wrote: > > > In order to get around the problem, I tried to replace the whole > > switch-statement with lots of if-elseif statements. > > Unfortunately, another problem arose. The Verifyer now says: > > > 09-29 18:02:44.058: WARN/dalvikvm(450): VFY: arbitrarily rejecting > > large method (regs=127 count=34916) > > I fixed that one too while I was at it. The limit was intended to > prevent the verifier from soaking up huge amounts of memory, but (a) > the limit is too low, and (b) there are better mechanisms in the > system for doing that. So now it's just a warning that says, "hey, > this is huge". > > With both fixes in place, the original code passes. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
On Sep 30, 3:59 pm, DanH wrote: > Of course, the real problem is that the verifier is mis-designed. I'm > guessing it uses reference chains. I'm not sure those two sentences go together. :-) -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Reference chains are slow and take up too much space. On Oct 4, 3:25 pm, fadden wrote: > On Sep 30, 3:59 pm, DanH wrote: > > > Of course, the real problem is that the verifier is mis-designed. I'm > > guessing it uses reference chains. > > I'm not sure those two sentences go together. :-) -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
On Oct 4, 1:45 pm, DanH wrote: > Reference chains are slow and take up too much space. I don't know what you mean by "reference chains". Could you point out where in the code they're being used? -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
The verifier must create what is commonly known a "use-def chains" for
the bytecodes in a method, to determine which results from one
bytecode can flow as inputs to another bytecode ("data flow"). The
traditional way to do this (and the one used in most verifiers) is to
literally construct chains -- lots of little objects chained together
into lists. This is space consuming and time-consuming to do.
A different way to do it is with bitsets, where one bit in the set
represents one possible result from one bytecode. One bitset
represents the values set at any point in the program, and others
represent the values "killed" by the program flow. These can be
accumulated for basic blocks (whereas use-def chains are generally
done on a per-instruction basis) and fairly simple bit masking
operations can then be used to perform the global data flow analysis
that's needed for verification.
(Morel and Renvoise produced what's probably the best explanation of
this technique in http://doi.acm.org/10.1145/359060.359069 )
Of course, in the general case the bitsets can get too large, but
there are techniques for compressing them that reduce bitset size by a
factor of ten or more, and make even the largest Java method easily
tractable with this approach. (Though this technique I'll likely take
to my grave, since no one else is interested in it.)
On Oct 4, 6:32 pm, fadden wrote:
> On Oct 4, 1:45 pm, DanH wrote:
>
> > Reference chains are slow and take up too much space.
>
> I don't know what you mean by "reference chains". Could you point out
> where in the code they're being used?
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to android-developers@googlegroups.com
To unsubscribe from this group, send email to
android-developers+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
On Oct 4, 5:09 pm, DanH wrote:
> The verifier must create what is commonly known a "use-def chains" for
> the bytecodes in a method, to determine which results from one
> bytecode can flow as inputs to another bytecode ("data flow"). The
> traditional way to do this (and the one used in most verifiers) is to
> literally construct chains -- lots of little objects chained together
> into lists. This is space consuming and time-consuming to do.
Ah. The current verifier just tracks the contents of each register
(Dalvik isn't Java, registers not stack), and uses a work-list
approach to figure out what to do next. Each register value is a
small enumeration (indicating a primitive type) or a Class reference.
The verification process is also used to generate the register maps
for type-precise GC, which means it needs to store the register state
for every instruction that could be a GC point. (If it were just
about verification, it would only need to retain it for the start of
each basic block.)
The current version doesn't really treat basic blocks in a fancy way;
it just has a bit flag on each instruction that indicates if it's a
branch target. This leads to some inefficiencies in the work-list
scan. A future version will identify the basic blocks, use a reverse
postorder traversal to reduce the number of times we have to process
the same stretch, and do backward flow analysis for live-precise
register maps.
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to android-developers@googlegroups.com
To unsubscribe from this group, send email to
android-developers+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
Yeah, I oversimplified the above description -- the verifier tracks
(and must do so, in order to do valid verification) stack entry
contents, which is equivalent to registers (assuming that Dalvik
somehow tracks "spill" registers, which it must in order to do valid
verification). Apparently Dalvik, like Sun, treats each bytecode as
essentially a separate basic block, which is a valid way to do it --
there are pros and cons to having explicit basic blocks. The work
list is a fairly standard way to iterate through the bytecodes/blocks
(though in many cases reverse postorder is better -- my memory's a
little fuzzy on the tradeoffs).
In the bitmap scheme each stack entry/register has several bits
assigned, one for each possible type that could conceivably reach it.
If an object pointer is assigned then all the bits for that class
hierarchy are set, and when flows combine the bitsets are "anded"
together. Thus the value that reaches a use automatically represents
the classes valid at that point, taking into account the different
flows.
The same bitmap can also be used to track the "newness" of values
(those that still need to be "constructed") and several other things.
And of course in any dataflow scheme a degree of constant propagation
falls out for free.
On Oct 5, 1:05 pm, fadden wrote:
> On Oct 4, 5:09 pm, DanH wrote:
>
> > The verifier must create what is commonly known a "use-def chains" for
> > the bytecodes in a method, to determine which results from one
> > bytecode can flow as inputs to another bytecode ("data flow"). The
> > traditional way to do this (and the one used in most verifiers) is to
> > literally construct chains -- lots of little objects chained together
> > into lists. This is space consuming and time-consuming to do.
>
> Ah. The current verifier just tracks the contents of each register
> (Dalvik isn't Java, registers not stack), and uses a work-list
> approach to figure out what to do next. Each register value is a
> small enumeration (indicating a primitive type) or a Class reference.
>
> The verification process is also used to generate the register maps
> for type-precise GC, which means it needs to store the register state
> for every instruction that could be a GC point. (If it were just
> about verification, it would only need to retain it for the start of
> each basic block.)
>
> The current version doesn't really treat basic blocks in a fancy way;
> it just has a bit flag on each instruction that indicates if it's a
> branch target. This leads to some inefficiencies in the work-list
> scan. A future version will identify the basic blocks, use a reverse
> postorder traversal to reduce the number of times we have to process
> the same stretch, and do backward flow analysis for live-precise
> register maps.
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to android-developers@googlegroups.com
To unsubscribe from this group, send email to
android-developers+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
On Oct 5, 11:28 am, DanH wrote: > In the bitmap scheme each stack entry/register has several bits > assigned, one for each possible type that could conceivably reach it. > If an object pointer is assigned then all the bits for that class > hierarchy are set, and when flows combine the bitsets are "anded" > together. Thus the value that reaches a use automatically represents > the classes valid at that point, taking into account the different > flows. Dalvik needs to keep more state than this around, because it needs to keep track of what type of object is in each register that holds an object. The verifier is responsible for determining if method A is allowed to access fields and methods in class B, so it needs to know what type of object the code is operating on. The register merge procedure can actually involve searching for a common superclass. I'm sort of curious now to see if there's a way to detect invalid conversions and perform legal widening conversions with bitwise operations. I'm not sure it'd be a win over the table lookup, but it creates the possibility of doing a whole bunch of registers in parallel. I'm not sure the relations are simple enough. For example, Dalvik is more picky than certain other VMs when it comes to the contents of short integers (e.g. you could have a value of 1024 in a "byte" in some VMs). Dalvik tries to do all this ahead of time (via "dexopt") when the app is first installed, which results in various limitations and re-verify triggers when other parts of the system change. This doesn't always work, so it'll do the verification / register map generation on first load if necessary. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
[android-developers] Re: VerifyError reloaded
> Dalvik needs to keep more state than this around, because it needs to > keep track of what type of object is in each register that holds an > object. The verifier is responsible for determining if method A is > allowed to access fields and methods in class B, so it needs to know > what type of object the code is operating on. The register merge > procedure can actually involve searching for a common superclass. The "anding" of the bitsets together implicitly does the search for the common superclass, since when a "reference" is placed in a slot (register/stack entry) then all of the bits of the class hierarchy are turned on. That's the meat-and-potatoes of verification. The iSeries scheme also did pre-verification (on first touch), and then did a load-time post-verification step (using tables created during the verification) to assure that everything "plugged together" legally. Unlike many implementations, there was no option to bypass verification on iSeries, since verification was necessary to insure machine integrity, so verification had to be reasonably fast and very secure. (This fit in with the RPG and COBOL implementations that also relied on a "safe backend" to produce code that could not violate system integrity.) On Oct 5, 3:49 pm, fadden wrote: > On Oct 5, 11:28 am, DanH wrote: > > > In the bitmap scheme each stack entry/register has several bits > > assigned, one for each possible type that could conceivably reach it. > > If an object pointer is assigned then all the bits for that class > > hierarchy are set, and when flows combine the bitsets are "anded" > > together. Thus the value that reaches a use automatically represents > > the classes valid at that point, taking into account the different > > flows. > > Dalvik needs to keep more state than this around, because it needs to > keep track of what type of object is in each register that holds an > object. The verifier is responsible for determining if method A is > allowed to access fields and methods in class B, so it needs to know > what type of object the code is operating on. The register merge > procedure can actually involve searching for a common superclass. > > I'm sort of curious now to see if there's a way to detect invalid > conversions and perform legal widening conversions with bitwise > operations. I'm not sure it'd be a win over the table lookup, but it > creates the possibility of doing a whole bunch of registers in > parallel. I'm not sure the relations are simple enough. For example, > Dalvik is more picky than certain other VMs when it comes to the > contents of short integers (e.g. you could have a value of 1024 in a > "byte" in some VMs). > > Dalvik tries to do all this ahead of time (via "dexopt") when the app > is first installed, which results in various limitations and re-verify > triggers when other parts of the system change. This doesn't always > work, so it'll do the verification / register map generation on first > load if necessary. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to android-developers@googlegroups.com To unsubscribe from this group, send email to android-developers+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
