Oracle America, Inc. v. Google Inc.

Filing 1080

MOTION in Limine to Exclude Evidence Regarding Compatibility Testing Suite filed by Google Inc.. Responses due by 5/21/2012. Replies due by 5/29/2012. (Attachments: #1 Declaration of Truman Fenton, #2 Exhibit A, #3 Exhibit B, #4 Exhibit C, #5 Exhibit D, #6 Exhibit E, #7 Exhibit F)(Van Nest, Robert) (Filed on 5/6/2012)

u

7346884

UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
March 21, 2012
THIS IS TO CERTIFY THAT ANNEXED HERETO IS A TRUE COPY FROM
THE RECORDS OF THIS OFFICE OF:

U.S. PATENT: 6,061,520
ISSUE DATE: May 09, 2000

By Authority of the
Under Secretary of Commerce for Intellectual Property
and Director of the United States Patent and Trademark Office

T. LAWRENCE
Certifying Officer

UNITED STATES DISTRICT COURT
NORTHERN DISTRICT OF CALIFORNIA

TRIAL EXHIBIT 4011
CASE NO. 10-03561 WHA
DATE ENTERED
BY

Trial Exhibit 4011, Page 1 of 15

DEPUTY CLERK

111111 lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
US006061520A
United States Patent

[19]

Yellin et al.

[45]

[54]

METHOD AND SYSTEM FOR PERFORMING
STATIC INITIALIZATION

[75]

Inventors: Frank Yellin, Redwood City; Richard
D. Thck, San Francisco, both of Calif.

[73]

Assignee: Sun Microsystems, Inc., Palo Alto,
Calif.

[21]

Appl. No.: 09/055,947

[22]

Filed:

[51]
[52]
[58]

Apr. 7, 1998
7

Int. Cl. .......•.•••••••••.......•••••••• G06F 9/45; G06F 3/00
U.S. Cl. .................... 395/705; 395!704; 395/500.43;
709/100
Field of Search ..................................... 3951705, 707,
395!709
References Cited

[56]

[11]

Patent Number:
Date of Patent:

6,061,520
May 9, 2000

Bell, D.; "Make Java fast: Optimize!". Javaworld[online].
Cramer et al.; "Compiling Java just in time". IEEE Electronic Library[online], vol. 17, Iss. 3, pp. 36-43, May 1997.
Lindholm, Timet al., The Java Virtual Machine Specification, 1997.
Co mar et al.; "Targeting GNAT to the Java virtual machine".
ACM Digital Library[ online], Proceedings of the conference
on TRI-Ada '97, May 1997.
Hsieh et al.; "Compilers for improved Java Performance".
IEEE Electronic library[ online]. Computer[ online], vol. 30,
Iss. 6, pp. 67-75, Jun. 1997.
Armstrong, E.; "Hotspot: A new breed of virtual machine".
Javaworld[online].
Gosling et al.; The Java Language Specification. Reading,
MA, Addison-Wesley. Ch 12, pp. 215-236, Sep. 1996.

Primary Examiner-Tariq R. Hafiz
Assistant Examiner-Kelvin E. Booker
Attorney, Agent, or Firm-Finnegan, Henderson, Farabow,
Garrett & Dunner, L.L.P.

U.S. PATENT DOCUMENTS
5,361,350
5,367,685
5,421,016
5,437,025
5,615,400
5,668,999
5,812,828
5,815,718
5,903,899
5,966,702
5,999,732
6,003,038

[57]

11/1994
11/1994
5/1995
7/1995
3/1997
9/1997
9/1998
9/1998
5/1999
10/1999
12/1999
12/1999

The disclosed system represents an improvement over conventional systems for initializing static arrays by reducing
the amount of code executed by the virtual machine to
statically initialize an array. To realize this reduction, when
consolidating class files, the preloader identifies all <clinit>
methods and play executes these methods to determine the
static initialization performed by them. The preloader then
creates an expression indicating the static initialization performed by the <clinit> method and stores this expression in
the .mclass file, replacing the <clinit> method. As such, the
code of the <clinit> method, containing many instructions,
is replaced by a single expression instructing the virtual
machine to perform static initialization, thus saving a significant amount of memory. The virtual machine is modified
to recognize this expression and perform the appropriate
static initialization of an array.

Conner et a!. .......................... 707/103
Gosling ................................... 395/707
Conner eta!. .......................... 395/707
Bale eta!. .............................. 707/103
Cowsar et a!. .......................... 709/305
Gosling ................................... 395/704
Kaufer eta!. ...................... 395/500.43
Tock ........................................ 395/705
Steele, Jr................................. 707/206
Fresko eta!. ............................... 707/1
Bak eta!. ............................... 395/705
Chen ....................................... 707/103

01HER PUBLICATIONS
Tyma, P;, "Tuning Java Performance". Dr. Dobb's Journal
[online], vol. 21, No. 4, pp. 52-58, Apr. 1996.
Cierniak et al., "Briki: an optimizing Java compiler". IEEE/
IEEE Electronic Library, Proceedings, IEEE Compean pp.
179-184, Feb. 1997.

ABSTRACT

23 Claims, 3 Drawing Sheets

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 2 of 15

U.S. Patent

May 9, 2000

6,061,520

Sheet 1 of 3

BEGIN

102
COMPILE PROGRAM

104
CONSOLIDATE CLASS
FILES

106
RUN .m CLASS
FILE ON VM

END

FIG. 1

(PRIOR ART)

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 3 of 15

U.S. Patent

May 9, 2000

Sheet 2 of 3

6,061,520

j~
N

(X)

0
N

N

0
~

T""

N

N

"

0
N

" "

LU

>-(.)
en
a::> :2 .....J
LU
w <Cw
tC2
::J oo (!) lL
zw

w

0::

a..
:2
0

8~
~0
ten

(..)

~
a..

en

~

0

w
.....J
u.
E

::::>
a..
0

>
w
0

ra..

::J

z
-

(.)

7!!

V<OOO
NNN
NNN

<0
0

N

"
~

0
:2
w
:2

LU

liD~~

0:: :2
0:: w t-:2
w 0
.....J <(

a..

0

.....J

zw

::Jt0::(/)

:2 w
>0 0:: ~en
(..) a..
~
...,

77-(
COOT"""
"""" N N

~
_J

a..

en
0

0

w
0

>

7

NNN

Copy provided by USPTO from the PIRS lma~e Database on 03/14/2012

Trial Exhibit 4011, Page 4 of 15

U.S. Patent

May 9, 2000

6,061,520

Sheet 3 of 3

302

READ CLASS FILE TO
OBTAIN A CLINIT METHOD

304

ALLOCATE VARIABLES

306

READ A BYTE CODE

N

310

PERFORM OPERATION
REFLECTED BY BYTE CODE

y

STORE DIRECTIVES IN
ITS CLASS FILE

FIG. 3

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 5 of 15

318

6,061,520

1

2

METHOD AND SYSTEM FOR PERFORMING
STATIC INITIALIZATION

Given this static initialization, the Java ™ compiler creates a
<clinit> method that performs the static initialization as
functionally described below in pseudo-code:

FIELD OF TilE INVENTION
The present invention relates generally to data processing
5
systems and, more particularly, to a method and system for
performing static initializati<;m.

Code Table #2

temp=new int [ 4 ];
temp=[0]=1;
temp=[1]=2;
10
temp=[2]=3;
temp=[3]=4;
this.setup=temp;
As the above code table shows, merely describing the
<clinit> method functionally requires a number of state15
ments. More importantly, however, the actual processing of
the <clinit> method, performed by byte codes, requires
many more statements. These byte codes manipulate a stack
resulting in the requested static initialization. A stack is a
portion of memory used by the methods in the Java pro20
gramming environment. The steps performed by the <clinit>
method for the example static initialization described above
are expressed below in byte codes.

BACKGROUND OF TilE INVENTION
Java™ describes both a programming language and a
programming environment for generating and running
platform-independent code. This platform-independent code
runs on a Java™ virtual machine, which is an abstract
computing machine that interprets the platform-independent
code. The Java TM virtual machine is described in greater
detail in Lindholm and Yellin, The Java Virtual Machine
Specification, Addison-Wesley (1997), which is hereby
incorporated by reference. The Java™ virtual machine does
not specifically recognize the Java™ programming language
or any other programming language; instead, the Java virtual
machine only recognizes a particular file format, the class
file format. A class file contains the Java virtual machine
instructions (or byte codes) that constitute the platformindependent code.
As part of running a Java program, a developer performs
Code Table #3
a number of steps, as shown in FIG. 1. First, a developer 25
compiles a computer program (step 102). Typically, the
Method void <clinit>O
developer has developed a computer program containing
0 iconst_4 //push an integer value of 4 on the stack
source code in a high-level language, such as the Java
1 newarray int //create a new array of integers and put it
programming language, and invokes the Java™ compiler to
on the stack.
compile the code. The Java compiler is part of the Java™ 30
3 dup //duplicate top of stack
software development kit available from Sun Microsystems
of Mountain View, Calif,. The Java compiler outputs one or
4 iconst_O //push an integer value of 0 on the stack
more class files containing byte codes suitable for execution
5 iconst_1 //push an integer value of 1 on the stack
on the Java virtual machine. Each class file contains one type
6 iastore //store a 1 at index 0 of array
of the Java programming language, either a class or an 35
7 dup //duplicate the top of the stack
interface. The class file format is described in greater detail
8 iconst_1 //push an integer value of 1 on the stack
on pp. 83--137 of The Java Virtual Machine Specification.
Although the class file format is a robust file format, it is
9 iconst_2 //push an integer value of 2 on the stack
unable to instruct the virtual machine to statically initialize
10 iastore //store a 2 at index 1 of array
an array efficiently, thus posing a problem, discussed in 40
11 dup //duplicate top of stack
greater detail below.
12 iconst_2 //push an integer value of 2 on the stack
After compiling the program, the developer consolidates
13 iconst_3 //push an integer value of 3 on the stack
the class files output in step 102 into a single file, known as
14 iastore //store a 3 at index 2 of array
a .mclass file, by using a preloader (step 104). The prcloader
also available from Sun Microsystems, Inc., concatenates 45
15 dup //duplicate top of stack
the class files and performs preprocessing to facilitate the
16 iconst_3 //push an integer of value 3 on stack
execution of the class files. After consolidating the class
17 iconst_4 //push an integer of value 4 on stack
files, the developer loads the .mclass file into a virtual
18 iastore //store a 4 at index 3 of array
machine (step 106). In this step, the Java virtual machine
19 putstatic #3<Field foobar.setup [I> //modify set up
stores the .mclass file in memory and interprets the byte 50
array according to new array on stack
codes contained in the .mclass file by reading the byte codes
22 return
and then processing and executing them. Until interpretation
Although using the <clinit> method provides the Java™
of the byte codes is completed, the .mclass file is stored in
compiler with a way to instruct the virtual machine to
memory. The byte codes recognized by the Java virtual
machine are more clearly described on pp. 151-338 of The 55 initialize a static array, the amount of code required to
initialize the array is many times the size of the array, thus
Java Virtual Machine Specification.
requiring a significant amount of memory. It is therefore
As stated above, the class file format cannot instruct the
desirable to improve static initialization.
virtual machine to statically initialize arrays. To compensate
for this problem, the Java™ compiler generates a special
SUMMARY OF TilE INVENTION
method, <clinit>, to perform class initialization, including 60
The disclosed system represents an improvement over
initialization of static arrays. An example of the initialization
conventional systems for initializing static arrays by reducof a static array follows:
ing the amount of code executed by the virtual machine to
Code Table #1
statically initialize an array. To realize this reduction, when
static int setup[ ]={1, 2, 3, 4};
65 consolidating class files, the preloader identifies all <clinit>
In this example, an array "setup" contains four integers
methods and simulates executing ("play executes") these
methods to determine the static initialization performed by
statically initialized to the following values: 1, 2, 3, and 4.

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 6 of 15

6,061,520

3

4

them. The preloader then creates an expression indicating
cause the same static initialization as the <clinit> method
and outputs these directives to the Java virtual machine, thus
the static initialization performed by the <clinit> method and
replacing the <clinit> method. These directives are then read
stores this expression in the .mclass file, replacing the
at runtime by the Java virtual machine causing the Java
<clinit> method. As such, the code of the <clinit> method,
containing many instructions, is replaced by a single expres- 5 virtual machine to perform the same static initialization
performed by the <clinit> method. The directives require
sion instructing the virtual machine to perform static
significantly less memory space than the <clinit> method.
initialization, thus saving a significant amount of memory.
For example, the byte codes described above in code table
The virtual machine is modified to recognize this expression
#3 could be reduced to the following directives contained
and perform the appropriate static initialization of an array.
Methods consistent with the present invention receive 10 within the .mclass file indicating that an array of four
integers has the initial values 1, 2, 3, and 4:
code to be run on a processing component to perform an
CONSTANT___Array T_INT 4 1 2 3 4
operation. The code is then play executed on the memory
The virtual machine of an exemplary embodiment recogwithout running the code on the processing component to
nizes this expression and statically initializes the array to the
identify the operation if the code were run by the processing
component. Thereafter, a directive is created for the pro- 15 appropriate values. As a result, the exemplary embodiment
reduces memory consumption over conventional systems
cessing component to perform the operation.
when initializing a static array.
A data processing system consistent with the present
Implementation Details
invention contains a secondary storage device, a memory,
FIG. 2 depicts a data processing system 200 consistent
and a processor. The secondary storage device contains a
20 with the present invention. The data processing system 200
program with source code that statically initializes the data
comprises a computer system 202 connected to the Internet
structure and class files, where one of the class files contains
204. Computer system 202 contains a memory 206, a
a <clinit> method that statically initializes the data structure.
secondary storage device 208, a central processing unit
The memory contains a compiler for compiling the program
(CPU) 210, an input device 212, and a video display 214.
and for generating the class files and a preloader for consolidating the class files, for simulating execution of the 25 The memory 206 further includes the Java™ compiler 218,
the Java™ preloader 220, and the Java™ runtime system
<clinit> method to determine the static initialization the
221. The Java™ runtime system 221 includes the Java™
<clinit> method performs, and for creating an instruction to
virtual machine 222. The secondary storage device 208
perform the static initialization. The processor runs the
contains a program 224 with source code, various class files
compiler and the preloader.
30 226, and a .mclass file 228. The Java™ compiler 218
compiles the program 224 into one or more class files 226.
BRIEF DESCRIPTION OF TilE DRAWINGS
The preloader 220 then receives the class files 226 and
FIG. 1 depicts a flowchart of the steps performed when
generates a .mclass file 228 representing the consolidation of
developing a program in the Java™ programming environall of the class files. After consolidation, the .mclass file 228
ment.
35 can be run on the virtual machine 222.
FIG. 2 depicts a data processing system consistent with
Processing consistent with the present invention is perthe present invention.
formed by the preloader 220 searching for a <clinit>
FIG. 3 depicts a flowchart of the steps performed by the
method, and when it is found, the preloader (1) simulates
preloader depicted in FIG. 2.
execution of the <clinit> method to determine the effects it
40 would have on memory if it was interpreted by the virtual
DETAILED DESCRIPTION OF TilE
machine 222, (2) creates static initialization directives to
INVENTION
replicate these effects, and (3) outputs these directives in the
.mclass file to replace the <clinit> method, thus saving
Systems and methods consistent with the present invensignificant amounts of memory.
tion provide an improved system for initializing static arrays
In addition, processing consistent with the present invenin the Java™ programming environment by replacing the 45
<clinit> method with one or more directives which, when
tion is performed by the virtual machine 222 because it is
read by the virtual machine, causes the virtual machine to
modified to recognize the static initialization directives of
perform the same static initialization performed by the
the preloader. Although an exemplary embodiment of the
present invention is described as being stored in memory
<clinit> method, except using a significantly less amount of
memory and significantly less time. As a result, such sys- 50 206, one skilled in the art will appreciate that it may also be
stored on other computer-readable media, such as secondary
tems and methods can significantly reduce memory utilizastorage devices like hard disks, floppy disks, or CD-Rom; a
tion when statically initializing an array.
carrier wave received from the Internet 204; or other forms
Overview
Systems and methods consistent with the present invenof RAM or ROM. Additionally, one skilled in the art will
tion eliminate the need for the <clinit> method by perform- 55 appr~;;ciate that computer 202 may contain additional or
different components.
ing certain preprocessing in the preloader. Specifically, the
The Preloader
preloader receives class files for consolidation and scans
FIG. 3 depicts a flowchart of the steps performed by the
them looking for a <clinit> method. When the preloader
preloader 220 consistent with the present invention to perfinds the <clinit method, it simulates execting ("play
executes") the <clinit> method against memory to determine 60 form initialization of a static array. The first step performed
by the preloader is to read a class file to obtain the <clinit>
the effects that the <clinit> method would have on the
method (step 302). After obtaining a <clinit> method, the
memory if interpreted by the Java virtual machine. That is,
preloader allocates various variables for use during play
the preloadef simulates execution of the <clinit> method to
execution (step 304). When play executing, discussed below,
identify the static initialization that would result had the
<clinit> method been executed by the Java™ virtual 65 the preloader simulates execution of the byte codes contained in the <clinit> method by the virtual machine. These
machine. After identifying this static initialization, the preloader generates one or more directives (or instructions) to
byte codes manipulate various data structures associated

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 7 of 15

6,061,520

6

5

with the <clinit> method, such as the constant pool, the
<clinit> method (step 314). If so, processing returns to step
stack, or local variables (or registers).
306. However, if there are no more byte codes, the pre loader
The constant pool is a table of variable-length structures
stores directions in the .mclass file to statically initialize the
representing various string constants, class names, field
arrays (step 318). In this step, the preloader stores constant
names, and other constants referred to within the class file. 5 pool entries into the .mclass file like the following:
The stack is a portion of memory for use in storing operands
during the execution of the method. Thus, the size of the
stack is the largest amount of space occupied by the operSize
Values
Type
Tag
ands at any point during execution of this method. The local
variables are the variables that are used by this method.
10
T_INT
CONSTANT_Array
4
1234
When allocating variables, the pre loader obtains a pointer
to the constant pool of the <clinit> method, allocates a stack
This entry in the constant pool indicates that a particular
to the appropriate size, and allocates an array such that one
array has four integers that have the initial values of 1, 2, 3,
entry of the array corresponds to each of the local variables.
As described below, the play execution operates on these 15 and 4. At run time, when the virtual machine initializes the
class .mclass file, it will encounter a reference to this
variables.
constant pool entry and create the appropriate array. As a
After allocating the variables, the preloader reads a byte
result, the many instructions contained in the <clinit>
code from the <clinit> method (step 306). Next, the premethod are reduced to this one expression, saving significant
loader determines if it recognizes this byte code (step 308).
In this step, the preloader recognizes a subset of all byte 20 amounts of memory and time.
Example Implementation of the Preloader
codes where this subset contains only those byte codes that
are generally used to perform static initialization of an array.
The following pseudo-code describes sample processing
Following is a list of the byte codes recognized by the
of the pre loader of an exemplary embodiment. The preloader
preloader of an exemplary embodiment:
receives as a parameter a method information data structure
25 that defines the <clinit> method, described in the Java™
Virtual Machine Specification at pp. 104-106, and play
executes the byte codes of this <clinil> method. It should be
Code Table #4
noted that the processing described is only exemplary; as
such, only a few byte codes are described as being processed
aconst_null
iastore
iconst_m1
las tore
30 by the preloader. However, one skilled in the art will
fastore
iconst_O
appreciate that all of the byte codes in code table #4 may be
dastore
iconst_1
processed by the exemplary embodiment.
iconst_2
aastore
iconst_3
iconst_4
iconst_S
lconst_O
lconst_1
fconst_O
fconsL1
fconst_2
dconst_O
dconst_1
bipush
sipush

bastore
lastore
sastore
dup
newarray
anewarray

35

Code Table #5

return

Ide
ldc_w
ldc2_w
putstatic

Any byte codes other than those listed above are not
recognized. The appearance of other byte codes beyond
those described above indicates that the <clinit> method
performs functionality in addition to statically initializing an
array. In this case, the <clinit> method cannot be optimized.
If a byte code is not recognized, the preloader considers it
unsuitable for optimization (or play execution) and processing continues to step 316.
If the preloader recognizes the byte code, however, the
pre loader performs the operation reflected by the byte code
(step 310). In this step, the preloader play executes the byte
code on the variables allocated in step 304, and as a result,
a value may be popped from the stack, a local variable may
be updated, or a value from the constant pool may be
retrieved. Additionally, the preloader may encounter a "put
static" byte code indicating that a particular static variable
(e.g., array) is to be initialized in a particular manner. If the
preloader receives such a byte code, it stores an indication
of the requested initialization into a hash table for later use.
An example of such an entry in the hash table follows:
Setup:=Array (1 ,2,3,4)

After performing the operation reflected by the byte code,
the pre loader determines if there are more byte codes in the

40

45

50

55

60

65

void emulateByteCodes(Method_info mb)
int numberRegisters = mb.max_localsQ; //number of local variables
int stackSize = mb.max_stackQ;
//stack size
byte byteCode [] = mb.codeQ;
//get the byte code
ConstantPool constantPool = mb.constantPoolQ; // get constant pool
Object stack[] = new Object[stackSize];
//create stack for
play execution
Object registers[] = new Object[ numberRegisters]; //create local
variables
for play
//execution
/* Start with an empty stack. • I
int stackTop = -1;
//just below valid element
/* Map of static objects *I
Hashtable changes = new HashtableQ;
try {
boolean success;
execution_loop:
for (int codeOffset = 0, nextCodeOffset;
;codeOffset = nextCodeOffset) {
int opcode = byteCode[codeOffset] & OxFF;
//0 .. 255
nextCodeOffset = codeOffset + 1; II the most usual value
switch(opcode) {
case opc_iconst_)Il1: //push -1 on the stack
stack[ ++stackTop] = new Integer(-1);
break;
case opc_bipush:
nextCodeOffset = codeOffset + 2;
stack[ ++stackTop] = new Integer(bytecode[ codeOffset + 1D;
break;
case opc_lload_3:
//load the contents of register 3
stack[ ++stackTop] = (Long)register [3];
stack[ ++stackTop] = null;
//longs use two words on stack
break;
// subtract top of stack from item below
case opc_fsub: {
float b = stack[stackTop--].float\lllueQ;
float a= stack[stackTop].floatValueO;

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 8 of 15

6,061,520

7

8

-continued

-continued

Code Table #5
stack[ stackTop] = new Float(a - b);
break;

Code Table #6

5

}
case opc_1dc:
nextCodeOffset = codeOffset + 2;
stack[ ++stackTop] =
constantPool.getitem(byteCode (codeOlfset + 1));
break;
case sastore: {// store the contents into a "short" array
short valne = (short) (stack[StackTop--].intValueQ);
int index = stack(StackTop--].intvalueQ;
short[] array = (short[]stack[StackTop--];
array[ index] = value;
break;

ul type;
I* see below *I
u4 length;
I* number of elements of the army *I
ux objects[ length];
I* Actual values *I
I* The following field is included only if type ==
T_CLASS *I
I* index of CONSTANT_Class in constant pool *I
u2 type2;

10

15

The ul type field is one of the values listed in the following
table:

}
case opc_putstatic: {
nextCodeOffset = codeOffset + 3;
int index= ((byteCode[codeOffset + 1] & OxFF) « 8) +
(byteCode[ codeOffset + 2] & OxFF);
Field f = constantPool.getitem(byteCode[ codeOffset + 1 ];
if (f.getClassQ ! = mb.getClassQ) {
II we can on! y modify static's in our own class
throw new RuntimeExceptionQ;

Array Type
T_CLASS
T_BOOLEAN
T_CHAR
T_FLOIU
T_DOUBLE
T_BYTE
T_SHORr
T_INT
T_LONG

20

}
Type t = f.getTypeQ;
if (t.isl.ongQ II t.isDoubleO)
++stackTop;
Object value = stack[ ++stackTop]
changes. put(f, value); II put entry into hashtable
break;
case opc_return:
success = true;
break execution_loop;
defan!t: II some byte code we do not understand
success = false;
break execution_loop;

25

30

}
}

Value
2
4
5
6

7
8
9
10

11

The field ux objects[length] is an array of values, providing the elements of the array. The number of elements in the
array is given by the length field of the constant pool entry.
The actual size of each of these values is shown below:

35

} catch (RuntimeException) {
II any runtime exception indicates failure.
success = false;

Type

}
if (success) {
<modify .class file as indicated by "changes" hashtable>
<Remove this <clinit> method from the class>
} else {
<ran into something we cannot understand>
<do not replace this method>

40

ux

Meaning

T_BOOLEAN,T_BYTE
T_CHAR, T_SHORT, T_CLASS
T_INT, T_FLOAT
T_LONG, T_DOUBLE

u1
u2
u4
u8

1
2
4
8

byte
bytes
bytes
bytes

}
}

45

For all of the above types exceptforT_CLASS, the bytes
shown are the actual value that are stored in that element of
the array. ForT_CLASS, however, each u2 is itself an index
to an entry into the constant pool. The constant pool entry
referred to must itself be either a CONSTANT_Array,
CONSTANT_Object, or the special constant pool entry 0,
indicating a NULL value.

The Virtual Machine of the Exemplary Embodiment
As stated above, the Java virtual machine 222 is an
otherwise standard Java virtual machine as defined in the
Java Virtual Machine Specification, except that it is modi- 50
fied as will be described below. Conventional virtual
machines recognize various constant pool entries, such as
CONSTANT_Integer, CONSTANT_String, and
For example, to indicate the following array:
CONSTANT_Long. Constant pool entries of these types
store various variable information, including the initial 55
value. The virtual machine of an exemplary embodiment,
int[ ]={10, 20, 30, 40 };
however, additionally recognizes the CONSTANT_Array
entry in the constant pool.
The format of the CONSTANT_Array constant pool
the constant pool entry would be as follows:
60
entry in the class file format follows:

Tag

Code Table #6
CONSTANT_lUrny_info{
ul tag;
/*The literal value CONSTANT_lUrny *I

65

Type

Size

Initial Values

CONSTANT_lUrny

T_INT

4

10 20 30 40

Copy provided by USPTO from the PIRS Image Database on 03/1412012

Trial Exhibit 4011, Page 9 of 15

6,061,520

9
As another example, to indicate the following array:

10

allocating a stack;
reading a byte code from the clinit method that manipunew Foo[3 ]/* all initialized to NULL */
lates the stack; and
the constant pool entry would be as follows:
performing the stack manipulation on the allocated stack.
5
4. The method of claim 1 wherein the play executing step
includes the steps of:
allocating variables;
Tag
Type
Size Initial Values
Class
reading a byte code from the clinit method that manipuCONSTANT_Array
T_CLASS
3
000
XX
lates local variables of the clinit method; and
10
performing the manipulation of the local variables on the
where "xx" is an index into the constant pool indicating the
allocated variables.
class Foo in the constant pool.
5. The method of claim 1 wherein the play executing step
Two-dimensional arrays like the following:
includes the steps of:
15
obtaining a reference to a constant pool of the clinit
new byte[ I ]={ {1,2,3,4 }, {5,6,7,8 }};
method;
are encoded by having two constant pool entries encode the
reading a byte code from the clinit method that manipusub-arrays and by having two additional entries indicate the
lates the constant pool; and
association between the subarrays. This encoding correperforming the constant pool manipulation.
sponds to the Java™ notion of an array as a type of object 20
6. A method in a data processing system, comprising the
and a multi-dimensional array as an array of arrays. The
steps of:
constant pool entries of the above two-dimensional array
receiving code to be run on a processing component to
follows:
perform an operation;
play executing the code without running the code on the
Entry1: CONSTANT_Array T_BYfE 4 1 2 3 4
25
processing component to identify the operation if the
Entry2: CONSTANT_Array T_BYfE 4 56 7 8
code were run by the processing component; and
creating an instruction for the processing component to
Entry3: CONSTANT_Class with name "[[B"
perform the operation.
and then
7. The method of claim 6 wherein the operation initializes
30
a data structure, and wherein the play executing step
includes the step of:
play executing the code to identify the initialization of the
Tag
Type Size Initial Values
Class
data structure.
Entry4: CONSTANT_Array T_Class 2
Entry1 Entry2 Entry3
8. The method of claim 6 wherein the operation statically
35
initializes an array and wherein the play executing step
includes the step of:
where each of Entryl, Entry2, and Entry3 are the two-byte
play executing the code to identify the static initialization
encodings of the index of the corresponding constant-pool
entry.
of the array.
While the systems and methods of the present invention 40
9. The method of claim 6 further including the step of:
have been described with reference to a preferred
running the created instruction on the processing compoembodiment, those skilled in the art will know of various
nent to perform the operation.
changes in form and detail which may be made without
10. The method of claim 6 further including the step of:
departing from the spirit and scope of the present invention
interpreting the created instruction by a virtual machine to
45
as defined in the appended claims.
perform the operation.
What is claimed is:
11. The method of claim 6 wherein the operation has an
1. A method in a data processing system for statically
effect on memory, and wherein the play executing step
initializing an array, comprising the steps of:
includes the step of:
compiling source code containing the array with static
play executing the code to identify the effect on the
values to generate a class file with a clinit method 50
memory.
containing byte codes to statically initialize the array to
12. A data processing system comprising:
the static values;
a storage device containing:
receiving the class file into a preloader;
a program with source code that statically initializes a
simulating execution of the byte codes of the clinit 55
data structure; ami
method against a memory without executing the byte
class files, wherein one of the class files contains a
codes to identify the static initialization of the array by
clinit method that statically initializes the data structhe preloader;
ture;
storing into an output file an instruction requesting the
a memory containing:
static initialization of the array; and
a compiler for compiling the program and generating
60
the class files; and
interpreting the instruction by a virtual machine to pera preloader for consolidating the class files, for play
form the static initialization of the array.
executing the clinit method to determine the static
2. The method of claim 1 wherein the storing step includes
step of:
initialization the clinit method performs, and for
'
creating an instruction to perform the static initialstoring a constant pool entry into the constant pool.
65
ization; and
3. The method of claim 1 wherein the play executing step
includes the steps of:
a processor for running the compiler and the preloader.

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 10 of 15

6,061,520

11

12

13. The data processing system of claim U wherein the
pre loader includes a mechanism for generating an output file
containing the created instruction.
14. The data processing system of claim 13 wherein the
memory further includes a virtual machine that interprets the
created instruction to perform the static initialization.
15. The data processing system of claim 12, wherein the
data structure is an array.
16. The data processing system of claim U wherein the
clinit method has byte codes that statically initialize the data
structure.
17. The data processing system of claim U wherein the
created instruction includes an entry into a constant pool.
18. A computer-readable medium containing instructions
for controlling a data processing system to perform a
method, comprising the steps of:
receiving code to be run on a processing component to
perform an operation;
simulating execution of the code without running the code
on the processing component to identify the operation
if the code were run by the processing component; and
creating an instruction for the processing component to
perform the operation.
19. The computer-readable medium of claim 18 wherein
the operation initializes a data structure, and wherein the
simulating step includes the step of:

simulating execution of the code to identify the initialization of the data structure.
20. The computer-readable medium of claim 18 wherein
the operation statically initializes an array and wherein the
simulating step includes the step of:

5

10

15

20

25

simulating execution of the code to identify the static
initialization of the array.
21. The computer-readable medium of claim 18 further
including the step of:
running the created instruction on the processing component to perform the operation.
22. The computer-readable medium of claim 18 further
including the step of:
interpreting the created instruction by a virtual machine to
perform the operation.
23. The computer-readable medium of claim 18 wherein
the operation has an effect on memory, and wherein the
simulating step includes the step of:
simulating execution of the code to identify the effect on
the memory.

* * * * *

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 11 of 15

111111
c12)

1111111111111111111111111111111111111111111111111111111111111
US006061520Cl

EX PARTE REEXAMINATION CERTIFICATE (8658th)

United States Patent

cw) Number:

Yellin et al.

(45)

US 6,061,520 Cl

Certificate Issued:

Nov. 15, 2011

(54)

METHOD AND SYSTEM FOR PERFORMING
STATIC INITIALIZATION

References Cited

(75)

Inventors: Frank Yellin, Redwood City, CA (US);
Richard D. Tuck, San Francisco, CA
(US)

To view the complete listing of prior art documents cited
during the proceeding for Reexamination Control Number
90/011,489, please refer to the USPTO's public Patent
Application Information Retrieval (PAIR) system under the
Display References tab.

(73)

Assignee: Sun Microsystems, Inc., Palo Alto, CA
(US)

Primary Examiner-Eric B Kiss

(56)

(57)
Reexamination Request:
No. 90/011,489, Feb. 17, 2011
Reexamination Certificate for:
Patent No.:
6,061,520
Issued:
May 9, 2000
Appl. No.:
09/055,947
Filed:
Apr. 7, 1998
(51)

(52)
(58)

Int. Cl.
G06F 9/45
G06F 91445

(2006.01)
(2006.01)

U.S. Cl•.......................... 717/148; 703/22; 7171151;
718/100
Field of Classification Search ................... 395/705
See application file for complete search history.

ABSTRACT

The disclosed system represents an improvement over conventional systems for initializing static arrays by reducing
the amount of code executed by the virtual machine to statically initialize an array. To realize this reduction, when consolidating class files, the preloader identifies all <clinit>
methods and play executes these methods to determine the
static initialization performed by them. The preloader then
creates an expression indicating the static initialization performed by the <clinit> method and stores this expression in
the .mclass file, replacing the <clinit> method. As such, the
code of the <clinit> method, containing many instructions, is
replaced by a single expression instructing the virtual
machine to perform static initialization, thus saving a significant amount of memory. The virtual machine is modified to
recognize this expression and perform the appropriate static
initialization of an array.

304

306

310

318

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 12 of 15

US 6,061,520 Cl
2

1
EX PARTE
REEXAMINATION CERTIFICATE
ISSUED UNDER 35 U.S. C. 307

AS A RESULT OF REEXAMINATION, IT HAS BEEN
DETERMINED THAT:

5

THE PATENT IS HEREBY AMENDED AS
INDICATED BELOW.

The patentability of claims 1-4, 8, 10, 12-17, 20 and 22 is
confirmed.
Claims 6, 7, 9, 11, 18, 19,21 and 23 are cancelled.
Claim 5 was not reexamined.

* * * * *

Copy provided by USPTO from the PIRS Image Database on 03/14/2012

Trial Exhibit 4011, Page 13 of 15

Trial Exhibit 4011, Page 14 of 15

PT0-1683
(Rev. 7-96)

Trial Exhibit 4011, Page 15 of 15