Purifier1 Special Cases

Conflict Resolution Failure

Brief Description

A case has been found where the conflict resolution system fails to generate the same StackMap entry as Sun's preverifier does.

Status

Problem needs more investigation.

Action Items

1. Find out if there is a special case that has not been considered or if there is a general fault in the conflict resolution system.
2. Try to develop a simpler test case that makes the issue clear

Test Cases Exhibiting Conflict Resolution Failure

Details

Multiple branches that branch to or end up leading to a common branch target may have a difference in the "junk" elements in the LocalVariables table that may happen to have been used and abandonned by a particular branch source, but are not used by the branch target code. These extra values may be left in the local variables table, but they are irrelevant to the code following the branch target. Sun's perverifier purges the extra entries. The purifier, therefore has a method to resolve conflicting LocalVariables entries. The primary part of that method examines competing LocalVariables arrays and determines if two elements are compatible with each other or not. If they are, then the most general of the two is kept. Otherwise, they are assumed to be junk data and are purged.

Although this system works extremely well, a case has been found where it fails to work correctly. Several other cases were found in the past, but they were all special cases that were built into the conflict resolution system to enable it to resolve those special situations. This case, however, does not seem to be special in any way other than the fact that it disagrees with the StackMap created by Sun's preverifier.

Example

Tutorial2/Finished2.startApp provides an example of this issue and is shown below.

Source Code

 1:  public void startApp() throws MIDletStateChangeException {
 2:    display.setCurrent(items);
 3:
 4:    try {
 5:      if (rs == null) rs = RecordStore.openRecordStore("ToDoStore",true);
 6:    }
 7:    catch ( RecordStoreFullException excpt0 ) {
 8:    }
 9:    catch ( RecordStoreNotFoundException excpt1 ) {
10:    }
11:    catch ( RecordStoreException excpt2 ) {
12:    }
13:    // Code was added to the declarations, startApp, and destroyApp areas.
14:    String[] theRecords = null;
15:    try {
16:      int _maxRecords = rs.getNextRecordID();
17:      theRecords = new String[_maxRecords];
18:      for (int _i=0; _i < _maxRecords; ++_i ) {
19:        try {
20:          theRecords[_i] = new String(rs.getRecord( _i ),0,rs.getRecord(_i).length);
21:        } catch ( InvalidRecordIDException e ) {
22:          theRecords[_i] = "";
23:          continue;
24:        }
25:      }
26:    }
27:    catch ( InvalidRecordIDException excpt0 ) {
28:    }
29:    catch ( RecordStoreNotOpenException excpt1 ) {
30:    }
31:    catch ( RecordStoreException excpt2 ) {
32:    }
33:    for(int _i = 0; _i < theRecords.length; _i++) {
34:      items.append(theRecords[_i],null);
35:    }
36:  }
37:

Bytecode

The following byte code is from the compiled and preverified class file created from the source in the previous section. The StackMap has been reformatted for readability.

0:    aload_0
1:    getfield		Tutorial2.Finished2.display Ljavax/microedition/lcdui/Display; (40)
4:    aload_0
5:    getfield		Tutorial2.Finished2.items Ljavax/microedition/lcdui/List; (49)
8:    invokevirtual	javax.microedition.lcdui.Display.setCurrent (Ljavax/microedition/lcdui/Displayable;)V (54)
11:   aload_0
12:   getfield		Tutorial2.Finished2.rs Ljavax/microedition/rms/RecordStore; (52)
15:   ifnonnull		#40
18:   aload_0
19:   ldc		"ToDoStore" (7)
21:   iconst_1
22:   invokestatic	javax.microedition.rms.RecordStore.openRecordStore (Ljava/lang/String;Z)Ljavax/microedition/rms/RecordStore; (51)
25:   putfield		Tutorial2.Finished2.rs Ljavax/microedition/rms/RecordStore; (52)
28:   goto		#40
31:   pop
32:   goto		#40
35:   pop
36:   goto		#40
39:   pop
40:   aconst_null
41:   astore_1
42:   aload_0
43:   getfield		Tutorial2.Finished2.rs Ljavax/microedition/rms/RecordStore; (52)
46:   invokevirtual	javax.microedition.rms.RecordStore.getNextRecordID ()I (46)
49:   istore_2
50:   iload_2
51:   anewarray		<java.lang.String> (12)
54:   astore_1
55:   iconst_0
56:   istore_3
57:   goto		#100
60:   aload_1
61:   iload_3
62:   new		<java.lang.String> (12)
65:   dup
66:   aload_0
67:   getfield		Tutorial2.Finished2.rs Ljavax/microedition/rms/RecordStore; (52)
70:   iload_3
71:   invokevirtual	javax.microedition.rms.RecordStore.getRecord (I)[B (47)
74:   iconst_0
75:   aload_0
76:   getfield		Tutorial2.Finished2.rs Ljavax/microedition/rms/RecordStore; (52)
79:   iload_3
80:   invokevirtual	javax.microedition.rms.RecordStore.getRecord (I)[B (47)
83:   arraylength
84:   invokespecial	java.lang.String.<init> ([BII)V (34)
87:   aastore
88:   goto		#97
91:   pop
92:   aload_1
93:   iload_3
94:   ldc		"" (1)
96:   aastore
97:   iinc		%3	1
100:  iload_3
101:  iload_2
102:  if_icmplt		#60
105:  goto		#117
108:  pop
109:  goto		#117
112:  pop
113:  goto		#117
116:  pop
117:  iconst_0
118:  istore_2
119:  goto		#137
122:  aload_0
123:  getfield		Tutorial2.Finished2.items Ljavax/microedition/lcdui/List; (49)
126:  aload_1
127:  iload_2
128:  aaload
129:  aconst_null
130:  invokevirtual	javax.microedition.lcdui.List.append (Ljava/lang/String;Ljavax/microedition/lcdui/Image;)I (37)
133:  pop
134:  iinc		%2	1
137:  iload_2
138:  aload_1
139:  arraylength
140:  if_icmplt		#122
143:  return

Data Flow Analysis

Although this case also has problems with the Unresolved Null Object Issue, this analysis is aimed at describing how the Conflict Resolution Error comes about.

The conlfict occurs at the aload_0 instruction at offset 122, which is the branch target for several branch sources. The first branch source encountered by the Purifier1's DFA is the if_icmplt instruction at offset 140. At instruction 140, the Frame is:

Local Variables:
			0: (type=Object, class=Tutorial2.Finished2)
			1: (type=Object, class=[Ljava.lang.String;)
			2: (type=Integer)
			3: (type=Integer)
		OperandStack:
			Slots used: 0 MaxStack: 8.

LocalVariables slot 0 was set by the JVM prior to method execution. Slot 1 was set by the anewarray instruction at offset 51 and following astore_1 at offset 54, though it was originally initialized to null by the aconst_null at offset 40 and the following astore_1 at offset 41. Similarly, slot 2 was first set to an Integer by the istore_2 instruction at offset 49 based on the inokevirtual's result at offset 46. However, for the loop of interest, it was reset by the iconst_0 and istore_2 instructions at offsets 117 and 118. It is only after reaching offset 122 that slot 2 is modified by the iinc instruction at offset 134. Finally, slot 3 was set by the iconst_0 and istore_3 instructions at offsets 55 and 56 respectively.

After branching from offset 140 back to the aload_0 at offset 122, the DFA ends up back at the if_icmplt at offset 140. Nothing in between changes the types of the LocalVariables, though several instructions do change the values at run time.

Next, the alternate branch of the if_icmplt instruction at offset 102 is evaluated. This goes to offset 60 where nothing is changed all the way back down to offset 102 again. Since the branch from there has already been investigated, control flow falls trhough to the goto instruction at offset 105, which pushes the Frame and target onto the BranchStack for further investigation. At this point, the stored Frame is identical to the one shown above.

After processing several all of the other branches, the last Exception handler at offset 116 is processsed. After several instructions, the iconst_0 instruction at offset 117 is reached. Since offset 117 is a branch target, there is already a frame stored in the BranchStack for that offset, which has locals that are identical to those shown above. However, the locals for the exception handler code are much different and the conflict resolution detection system removes the extraneous data. Since the StackMap entries for offset 117 agree between the Purifier1 and Sun's preverifier, this resolution is obviously done correctly. Continuing on, we eventually get to the goto instruction at offset 119 (again) reached a second time. Since this is a branch the Frame is pushed onto the BranchStack, which detects that this offset has already been visited. In addition, it detects that the Frame from the normal execution was very different than what is passed on from the Exception handler. Again the conflict resolution system kicks into action and determines that slot 3 has junk data in it and discards this data. However, it is not just discarded in the current Frame, but in the stored Frame in the BranchStack. The effect is that the change affects the Frame stored at offset 122, which should not be changed according to Sun's preverifier.

Side note: Why doesn't conflict resolution at goto instruction at offset 113 fix the Null in the 116 Frame too?

Solutions

None at the moment.

Back to Developer's Guide   Purifier1 Home Page