[||||||||||||||||||||||||||||l||||||||||||||||||||||||||||||||||||||||l||||
`
`UStl0665 849231
`
`(12) United States Patent
`US 6,658,492 Bl
`Kawahara et al.
`(45) Date of Patent:
`Dec. 2, 2003
`
`(10) Patent N0.:
`
`(54) SYSTEM AND METHOD FOR REDUCING
`THE FOOTPRINT 0F [RELOADED
`
`*
`6,526,565 Bl
`6,530,080 BE *
`
`2r2003 Nally
`3r2ttfl3 Freskn el al.
`
`
`
`‘r'l‘r'r‘los
`“Inner:
`
`CLASSES
`
`FOREIGN PA'I‘ENT DOCUMENTS
`
`(75)
`
`Inventors: Hide-ya Kawahara, Mountain View, CA
`(US); Nedim Fresh), San Francisco,
`CA (US)
`.
`.
`.
`(73) Assignec: bun Mlerusystems, lne.. Santa Clara,
`CA (US)
`'
`'
`‘
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`( * ) Notice:
`
`(31) Amp Na: 09/045,503
`
`(22
`
`Filed:
`
`Mar. 20, 1998
`
`Int. C1,?
`(51)
`(52) U.S. Cl.
`(58) Field of Search
`
`G061r 9100
`709:332; alarms; 717r159
`709332 331-
`717y15i_16'}
`'
`
`(56)
`
`References Cited
`_
`U.S. PA] ENI DOCUMEN 13
`; 1,3483 A a mggs Houha el aL
`5:515:718 A s
`511998 Tuck
`3,966,542 A a
`lmggg vlhck
`3,966,?le A *
`ltltl‘JW Fresko at al.
`6,052,7'r8 A "
`4,2011! Hagyet at.
`6,061,520 A “
`5r'_ZUUO ‘Ijellin 6I all
`5,223,323 [:1 : hid? "10013
`L:
`t 1330”;
`‘
`.’"
`’
`.
`6,349,344 Bl
`*
`240.002 Sanntry et al.
`6,363,436 Bl
`‘"
`$2002 Ilagyetal.
`6,366,898 BE *
`4,0002 Taivalsaari et al.
`
`Tmmfi
`_ $09,331
`
`
`713“
`ain't)
`109L331
`'r‘U3r'22
`
`7131':
`"infilltfill:
`'
`
`
`--
`
`Uflfil-‘Nr‘M
`
`[LP
`
`S
`
`9r1999
`943989 A2 *
`‘
`_ 1
`I
`‘
`0 l'llLR PUBLICAIIONS
`.-T -
`‘..t ..“=.
`..
`I Memory Ugagc bah
`Mlcm?‘ cm: Pbmnauava l
`ntcal Note.
`1998.
`"The Java“ Virtual Machine Specification",Tim Lindltolm,
`hank yellm’ 4'75 Pages’ @1991 leN 0201_63452_X'
`as cited by cxamimr
`
`Primary Examiner
`John [’ollansbee
`
`Assistant Exmrtiner—[ewis A. Bullock, Jr.
`(74) Attorney, Agent, or Firm—Pennie & Edmonds LLP
`_
`(3?)
`
`ABSTRACT
`
`A method and System that reduces the Space allowed for
`imam“ d“ filmmms by a “Mime Win“- “w imam?"
`data structures store member
`information for preloaded
`classes used by applications executed by the runtime engine.
`The system determines the different types of internal data
`structures represented in the classes and identifies thee
`possible values of each type’s members. The system next
`determines the amount of space required to store the values
`for each type in a respective value table and the number of
`bits needed to index each entry of that table. The system
`determines based on the stored information whether occur-
`rences of a member are optimally represented as a set of
`value table indices and a value table or, in the conventional
`manner, as a general variable that stores the member’s value
`for each occurrence.
`'l‘htr): system then crmts appropriate
`information or the mem er and its parent data structure.
`
`44 Claims, 12 Drawing Sheets
`
`
`memmms-—" Tm
`fieutfidlnia-mbarnms
`"
`-:"“~—._Ilm
`Formmambar
`:
`aluminum-mere! —_—L\q__1wa
`mammal-ruby
`
`:31?”
`Demarm'mmmoryspaue
`Rh‘ 1' 12
`ratified lestoreead: value.
`Detanfinammowapm
`"xfium
`required watereanindexte
`aaehvatue.
`Deeerminesizentennventrmal wx_‘1;5
`mprwrabnnofmember.
`
`
`
`
`
`
`
`
`
`I
`
`at
`
`_
`I
`guts
`rut-pg:
`
`Computememnryspane
`---\_‘_1‘20
`Eeq’tl byeommbonat rep (Lass).
`__ hgigepineandta‘bleflgfiscfm by
`
`fix—‘m
`
`“'
`_
`Reuresent member as value Lama am innings.
`
`
`(12—8
`_|
`
`Represent member canvamenatly.
`
`1126
`
`
`
`
`‘1 13D
`
`
`Determine opt: ameJQQErRIéEé;_ -\.___,4_32
`Generate member values and header
`- x__"3‘
`
`inlb summing to the optimal nrrlemg
`
`
`1
`
`Apple v. Realtlme
`Proceeding No. |PR2016-01365
`APPLE 1018
`
`Apple v. Realtime
`Proceeding No. IPR2016-01365
`APPLE 1018
`
`1
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 1 0f 12
`
`US 6,658,492 B1
`
`Class File
`
`400
`
`Header Info
`
`402
`
`Constant Pool
`
`404
`
`(Prior Art)
`
`408
`
`Methods Table
`
`406
`
`Fields Table
`
`FIG. 1
`
`2
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 2 0f 12
`
`US 6,658,492 B1
`
`1200
`One per Class
`w
`I" _ _ _ - _ _ _ _ _ _ _ ' ' _ _ _ - _ - - _ _ _ _ _ _ _ _ _ _ ' - - _ — _ _ " '|
`
`Class Block
`1202
`
`Method Blocks
`1204
`
`
`
`Method Blocks
`Field Blocks
`Constant Pool
`
`
`
`1234
`
`
`
`
`
`
`
`
`
`Field Blocks
`Constant Pool
`1214
`1224
`
`
`
`
`Field B|k1
`
`1214.1
`
`Field Blk 2
`
`1214.2
`
`Field Blk N
`
`1214.N
`
`
`
`
`
`FIG. 2A
`
`
`
`ptr
`Mefihgggk 2
`
`ptr _
`
`
`
`
`
`(Prior Art)
`
`|I I lI II I I| l I || | | l I Il II I I
`
`:I
`
`I l I II lI lI I I I I I I l II l I
`
`
`1204.1
`
`
`
`Method Blk N
`
`1204.N
`
`
`
`
`
`
`
`
`3
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 3 0f 12
`
`US 6,658,492 B1
`
`Data Structure Declarations
`1 230
`
`Data Structure 1 Decl.
`
`Member 1.1 Decl.
`
`Member 1.2 Decl.
`
`Member 1.3 Decl.
`
`Member 1.1 Acc’or Fun
`
`Member 1.2 Acc'or Fun
`
`Member 1.3 Acc’or Fun
`
`Data Structure 2 Decl.
`Data Structure 3 Decl.
`
`Data Structure N Decl.
`
`1230.1
`
`1232.1.
`
`1232.1.2
`
`1232.1.3
`
`1234.1.1
`
`1234.1.2
`
`1234.1.3
`
`1230.
`
`(Prior Art)
`
`
`ember1 of (T) : T->member1
`member1? of (T) : T—>member2
`member3 or (1') : T->member3
`memberz of (T) : T->member2
`member3 or (T) : T->member3
`
`1232.N.1
`1232.N.2
`1232.N.3
`1232.N.4
`1232.N.5
`
`1234.N.1
`1234.N.2
`1234.N.3
`1234.N.4
`1234.N.5
`
`Struct T {
`mtype1 member1
`mtypez member2
`mtypeS member3
`mtype4 member4
`mtypes member5
`
`} m
`
`FIG. 23
`
`4
`
`

`

`110
`
`Network Access Procedures
`
`Compiler
`
`Source Code Repository
`
`- flfiflfillllflllfl -
`flflflflfllflflfl -
`Inunuunnflfl
`
`116
`
`Communications
`
`US. Patent
`
`Dec. 2, 2003
`
`Sheet 4 0f 12
`
`US 6,658,492 B1
`
`100
`\1‘
`
`112 Operating System
`
`Interface
`
`5
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 5 0f 12
`
`US 6,658,492 B1
`
`02
`Processor(s)
`
`204
`
`flfiflflflflflflfl
`""ggggg:
`User Interface
`
`203
`
`Java Applications
`0 eratin S stem
`
`Network Access Procedures
`
`internal Data Structures
`
`Preloaded Classes
`_
`
`Java Applications
`
`
`
`FIG. 4
`
`213
`
`214
`
`1200
`
`232
`
`215
`
`246
`
`240
`
`242
`216
`217
`228
`
`
`
`
`
`206
`Communications
`Interface
`
`Runtime Class Loader
`
`Bytecode Verifier Module
`Operatmg SYStem
`Network Access Procedures
`Data Files
`
`Execution
`
`Engine
`
`fl
`
`
`
`
`1 06
`
`Network interconnectivity
`(Switches, etc.)
`
`
`
`1
`
`6
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 6 0f 12
`
`US 6,658,492 B1
`
`Per Class
`
`131
`
`Class Block
`
`Method Blocks
`
`Field Blocks
`
`Constant Pool
`
`FIG. 5
`
`
`
`ROM portion
`
`RAM portion
`
`
`
`
`
`
`
`Preloaded executable module
`
`7
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 7 0f 12
`
`US 6,658,492 B1
`
`VM Sources 618
`
`Object
`Data 622
`
`Class Files fl
`
` Preloaded
`Class Preloader Classes 148
`Assemblerfl
`
`Compiler fl
`OR
`112'
` Updated Header File 614
`
`Value Tables 616
`
`
`
`
`
`
`FIG. 6
`
`Compiler
`3%
`
`Object Data 620
`
`Linker 1E
`
`
`
`Preloaded
`
`executable
`
`module 306
`
`8
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 8 0f 12
`
`US 6,658,492 B1
`
` Data Struct. Decls. Struct T{
`
`
`
`Updated Header File 614
`
`Updt. Member Decls.
`Un-Updt. Member Decls.
`int m3_idx: 8
`
`Updt. Member Table Decls.
`'70
`a x
`int m4__idx :11
`
`Updt. Member Acc’or Funs
`“ ~mtype2 member2
`
`Un-Updt Member Acc’or Funs
`mtype5 member5
`
`
`
`
`extern mtypel member1_value[l
`
`extern mtype3 member3flvaluefl
`
`
`extern mtype 4 member4_value[]
`
`
`
`member1 of (T) member1_valuefl'-
`>m‘l_idx]
`
`
`members of (T) member3_valuefl'-
`>m3_idx]
`member4 of (T) member4_value[T-
`>m4_idx]
`
`
`
`
`
`
`
`
`
` 712
`
`FIG. 7A
`
`722.1
`
`Value Tables 616 (.c)
`
`Member1 Table
`.
`
`Member 3 Table 722.3
`
`Member 4 Table
`
`9
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 9 0f 12
`
`US 6,658,492 B1
`
`ROM 208
`
`0 C U l
`
`' r e n C e 3
`
`
`
`N003
`N010!)
`mmozm—u—ucooo
`
`Value Table
`
`Total Memow
`Usage:
`M*(||092(N)I+1) +
`table_size bits
`
`852.6 m*32 bits
`
`Usage:
`
`FIG. 8A
`
`I
`
`854.6
`
`I
`
`FIG. 8B
`
`PRIOR ART
`
`10
`
`10
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 100112
`
`US 6,658,492 B1
`
`Data Structure Memory Usage
`in Present Invention for one
`
`occurrence of Data Structure T 902
`
`W
`
`Unused Space 904
`
`
`
`32 bits
`
`32 bits
`
`32 bits
`
`I
`
`FIG. 9A
`
`
`
` |
`
`Data Structure Memory Usage
`in Prior Art for one occurrence
`
`of Data Structure T 906
`
`\1‘
`
`I
`
`5‘32 bits
`
`FIG. QB
`
`Prior Art)
`
`11
`
`11
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 11 of 12
`
`US 6,658,492 B1
`
`For each data structure:
`
`Identify all member type
`For each member e:
`
`Determine number of
`occurrences of member.
`
`Identify all values.
`Determine memory space
`recluired to store each value.
`Determine memory space
`required to store an index to
`each value.
`
`Determine size of conventional
`representation of member.
`
`1104
`
`1 106
`
`1108
`
`1110
`
`1112
`
`1114
`
`111.3
`
`1118
`
`
`For each member type:
`
`Compute memory space
`req’d by conventional rep (LHS).
`
`Compute memory space req’d by 1 1 22
`indices and table (RHS).
`
`
`1120
`
`
`
`
`
`
`
`
`! 1124
`
`Y
`
`1126
`
`
`
`
`
`
`
`
`Represent member as value table and indices.
`
`Represent member conventionally.
`
`{#1128
`
`1124
`
`Y
`
`1130
`
`For each data structure
`
`info according to the optimal ordering.
`
`Determine opt. ordering of members.
`Generate member values and header
`
`1132
`
`1 134
`
`FIG. 10
`
`12
`
`12
`
`

`

`US. Patent
`
`Dec. 2, 2003
`
`Sheet 12 0f 12
`
`US 6,658,492 B1
`
`210
`
`RAM Space for dynamically loaded
`applets, classes and data
`
`Copy of Methods and Data
`to be executed from RAM
`
`
`r 208
`
`Boot Time Initializer -
`
`Copy made by Boot Time
`initializer upon power up or
`reboot
`
`1 320
`
`
`
`
`
`
`
`
`ROM
`
`
`
`
`
`
`Methods and Data to be
`
`executed from RAM
`
`Methods and Data to be
`
`executed from ROM
`
`FIG. 11
`
`13
`
`13
`
`

`

`US 6,658,492 B]
`
`
`
`l
`SYSTEM AND METHOD FOR REDUCING
`THE FOOTI’RINT 0F PRELOADICD
`CLASSES
`
`invention relates generally to a class pre-
`The present
`loader and, particularly, to a system and method for reducing
`the size in read only memory of preloaded Java classes.
`BACKGROUND 01" THE INVENTION
`
`A Java program comprises a number of small software
`components called classes. Each class contains Code and
`data and is defined by information in a respective class file.
`Each class file is organized according to the same platform—
`independent "class file format“. Referring to FIG. 1, there is
`shown a block diagram ofthe class file format, according to
`which each class file 400 includes header information 402,
`a constant pool 404, a methods table 406 and a fields table
`408. The header information 402 identifies the class file
`format, the sine ofthe constant pool, the number ofrnethods
`in the methods table 496 and the number of fields in the -
`fields table 408. The constant pool 404 is a table of structures
`representing various string constants, class names, field
`names and other constants that are referred to within the
`class file structure and its sub—structures. The methods table
`406 includes one or more method structures, each of which a
`gives a complete description of and Java code for a method
`explicitly declared by the class. The fields table 408 includes
`one or more field structures, each of which gives a complete
`description of a field declared by the class. An example of
`the fields table 408 is now described in reference to FIG. 13.
`
`10
`
`15
`
`so
`
`A Java program is executed on a computer containing a
`program called a virtual machine (VM), which is respon—
`sible for executing the code in Java classes. It is customary
`for the classes of a Java program to be loaded as late in the
`program’s execution as possible: they are loaded on demand
`from a network server or from a local file system when first
`referenced during the program’s execution. The VM locates
`and loads each class, parses the class file format, allocates
`internal data structures for its various components, and links
`it in with other already loaded classes. This process makes
`the method code in the class readily executable by the VM.
`For small and embedded systems for which facilities,
`required for class loading, such as a network connection, a
`local file system or other permanent storage, are unavailable,
`it is desirable to preload the classes into read only memory
`(ROM). One preloading scheme is described in US. patent
`application Ser. No. 08i655,474 ("A Method and System for
`Loading Classes in Read-Only Memory“), which is entirely
`incorporated herein by reference. In this method and system,
`the VM data structures representing classes,
`fields and
`methods in memory are generated offline by a class pre-
`loadcr. The preloader output is then linked in a system that
`includes a VM and placed in read-only memory. This
`eliminates the need for storing class files and doing dynamic
`class leading.
`Referring to FIG. 2A, there is shown a more detailed
`block diagram of the VM data structures l200.generated by
`the class preloader. The data structures 1200 include a class
`block 1202, a plurality of method blocks 1204, a plurality of
`field blocks 1214 and a constant poo] 1224.
`The class block 1202 is a fixed-size data structure that can
`include the following information:
`the class name 1230;
`a pointer 1232 to the class block of the current class’s
`immediate superclass;
`a pointer 1234 to the method blocks 1204;
`
`35
`
`4!)
`
`45
`
`50
`
`60
`
`65
`
`14
`
`modified to save memory space, the VM code would need to
`
`2
`a pointer 1236 to the field blocks 1214; and
`a pointer 1238 to the class‘ Constant pool;
`The elements of a class block data structure are referred
`to herein as class block members.
`A method block 1204 is a fixed-sized data structure that
`represents one of the class’s methods. The elements of a
`method block data structure are referred to herein as method
`block members. A field block 1214-
`is a fixed-size data
`structure that represents one of the class’s instance variables.
`The elements of a field block data structure are referred to
`herein as field block members.
`Each type of VM data structure, including the class block
`1202, method blocks 1204, field blocks 1214 and constant
`pool 1224, has a format defined by a corresponding data
`structure declaration. For example, a single method block
`declaration defines the format of all method blocks 1204.
`The data structure declarations also define accessor func-
`tions (or macros) that are used by the VM to access data
`structure members. These data structure declarations are
`internal to the VM and are not used by class components.
`The prior art data structure declarations are now described in
`reference to FIG. ZB.
`Referring to FIG. 2B, there is shown a depiction of data
`structure declarations 1230 that define the format of all data
`structure types employed by a particular VM. Each decla-
`ration 1230 includes a set of member declarations 1232 and
`accessor functions 1234 for accessing respective members.
`The member declarations 1232 and accessor functions 1234
`are defined conventionally, according to the syntax of the
`language used in the implementation of the VM. For
`example, assuming the C language is used in the data
`structure declarations 1230, a generic field data structure
`I230.N (shown in FIG. ZB} could be defined as a structure
`'I‘ with five members of the following types with respective
`accessor functions:
`
`member name
`
`member type
`
`accessor functions
`
`member]
`membefi
`memberS
`menibcrd
`mcmbcr5
`
`mtypel
`mtypel
`mtype3
`mly‘pcll-
`mty'pcS
`
`memt of (1') ‘f—aniembert
`memE of (T) T—sntemberl
`mem3 of (T) T—smember3
`mam-1 of (T3 T—bmcrnburd-
`memS of (T3 T—bmcrnberS
`
`In this example, the member types can be any type defined
`by the relevant computer language, including user defined
`types or language types, such as integer, float, char or
`double. 'I'he accessor functions are macros used by the VM
`to access the fields without needing to access directly the
`structure containing the field. For example,
`instead of
`employing the expression “T->memberl" to access field] in
`structure type T, the VM need only employ the expression
`"mentl of (T)". Aecessor functions are well known in
`programming languages, such as C', that provide sophisti-
`cated data structure capabilities.
`The internal data structures used to store "class meta data"
`(Le, the class, method and field blocks 1202, 1204, 1214)
`require large, fixed amounts of space in read-only memory.
`In fact, measurements indicate that this sort of class meta
`data often takes up much more space than the bytecodes for
`the class methods themselves. These internal data structures
`are therefore often unsuitable for use in small, resource—
`constrained devices in which class preloading is desirable
`andr‘or necessary.
`Moreover, if the internal data structures were individually
`
`14
`
`

`

`
`
`US 6,658,492 B1
`
`3
`be extensively revised to enable the VM to correctly access
`the modified data structures. To make such changes to the
`VM could he onerous and inefficient.
`Therefore, there is need for a modified representation of
`the internal data structures that is smaller in size than the
`prior art data structures, includes all information required by
`the VM, and does not require extensive or onerous modifi—
`cation of the VM code.
`
`SUMMARY OF THE INVENTION
`
`In summary, the present invention is a method and system
`that reduces the ROM space required for preloaded Java
`classes.
`
`the method and system of the present
`In particular,
`invention are based upon the realization that, in an environ-
`ment where the Java VM classes are preloaded, it is highly
`likely that
`the VM would be a closed system with a set
`number of classes and class components. such as fields and
`methods. Such a closed VM would include a fixed number
`of internal data structures, such as class blocks, method
`blocks and field blocks. Moreover, each member of these
`data structures (e.g., a method block or field block member)
`would have one of a well-known set of distinct values.
`
`5
`
`ll]
`
`15
`
`Given this assumption and its implications, the present H
`invention reduces the memory space required to represent
`the internal data structures by:
`1) determining distinct values of each type of data struc-
`ture member;
`2) determining occurrences ofeach data structure member
`type {e.g., each occurrence in the method blocks of a
`field block member type) and each occurrence’s value;
`3) determining memory space that Would be saved if each
`(recurrence were represented as an index to a table of
`values of the data structure member type rather than ‘
`conventionally (storing the value for each occurrence in
`a general variable); and
`4) if sufiicient savings Would result, allocating a value
`table containing the distinct data structure member type
`values and configuring each occurrence of that field
`block member type as an index to the appropriate value
`table entry; and
`5) generating new sources to the VM so that its access to
`the modified structures is adapted automatically.
`In a preferred embodiment,
`the decision is made to
`represent a data structure member type as a value table index
`plus a value table if the following comparison is true:
`
`3o
`
`40
`
`(floccurrences of type]x(size of index)+(size of value
`tublc)<(#occurrenocs of typc)x(5izc of general variable).
`
`Once the present method has determined for each data
`structure member type whether an occurrence of that type is
`to be represented as an index into a value table or as a
`general variable storing the value, the present method emits
`appropriate information for that
`type,
`including accessor
`functions, language declarations and source code that ini-
`tializes the value tables. The accessor functions are macros
`through which all
`runtime access to the data structure
`members is accomplished—by the VM. Preferably, prior to
`emitting the above-described information,
`the present
`method determines the most compact arrangement of the
`value table indices, conventional representations of mem—
`bers and value tables and generates the value tables, value
`table indices, accessor functions and dams accordingly.
`The present method emits accessor functions, declarations
`and other data structure information after determining
`
`50
`
`55
`
`60
`
`65
`
`15
`
`4
`whether to modify the conventional representation of the
`data structure members. As a result, all emitted data struc-
`ture information is consistent with changes in the internal
`class representation. This automatic generation of consistent
`data structure information minimizes changes to the VM that
`are required whenever new classes are added to the VM, and
`whenever class representations change. This provides a
`significant improvement over the prior art.
`The system of the present invention includes a collection
`of class files, a Java class preloader in which the above
`method is implemented and output files generated by the
`preloader,
`including preloaded classes, header files and
`source code files.
`The class files define the complete set of classes to be
`preloaded. The preloader performs a first pass on the class
`files to determine the: different
`types of members of the
`internal data structures,
`distinct values of each type of member,
`amount of space required to store the values,
`the size of the value indices, and
`the number of occurrences of each member type.
`'I‘he preloader then performs a secoan pass on the class
`files and the internal data structures to determine how each
`member is to be represented, conventionally or as an index
`to a value table entry, and then emits the appropriate output
`Iiles.
`files
`files are compatible with similar
`The output
`employed by conventional Java systems. That is, the pre-
`loaded classes can be assembled or compiled into class
`object data and the header files and source files can be
`compiled with VM sources into VM object data. The VM
`and class object data can then be linked in the conventional
`manner into the executable VM for a particular Java envi-
`ronment.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Additional objects and features of the invention will be
`more readily apparent from the following detailed descrip-
`tion and appended claims when taken in conjunction with
`the drawings. in which:
`FIG. 1 illustrates the class file format common to the prior
`art and the present invention;
`FIG. 2Ais a block diagram of VM internal data structures
`used in the prior art
`to encode class. method and field
`information;
`illustrates the data structure declarations that
`FIG. 21!
`define the format of” the VM internal data structures shown
`in FIG. 2A;
`FIG. 3 is a block diagram of a distributed computer
`system in which the class preloader system and method of
`the present invention can be implemented;
`FIG. 4 is a block diagram of a execution engine in the
`distributed computer system of FIG. 1 in which the pre-
`loaded classes generated by the class preloader of FIG. 3 are
`loaded into ROM;
`FIG. 5 is a flow diagram illustrating the processing
`components used to produce the preloaded executable mod
`ule;
`flow diagram illustrating the processing
`FIG. 6 is a
`components used to reduce the memory footprint of the
`preloaded executable module;
`F] G. 7A illustrates the organization of the updated header
`file 614 of FIG. 6;
`FIG. TB illustrates the organization oI‘the value table 616
`of FIG. 6;
`
`
`
`15
`
`

`

`
`
`5
`FIG. 8A illustrates the organization of same member
`occurrences and values after allocation in the execution
`engine ROM 208 in accordance with the present invention;
`FIG. 8B illustrates the organization of same member
`occurrences after allocation in the execution engine ROM
`208 in accordance with the prior art;
`FIG. 9A illustrates the compact organization of a data
`structure instance with five members generated by the
`present invention;
`FIG. 93 illustrates the organization of the data structure
`instance from FIG. 9A generated by the prior art;
`FIG. 10 is a flow chart of the method usnd by the class
`preloader to build the internal data structures used in thc
`preloaded classes; and
`FIG. 11 is a block diagram showing the mapping of a
`preloaded application into read-only memory and random-
`access memory and indicating the loading of the portion of
`the methods and data mapped into random-access memory
`by a static class initializer.
`DESCRIP'ITON OF THE PREFERRED
`EMBODIMENT
`
`The method and system described herein are directed to a
`Java class preloader configured to output preloaded Java
`classes that are optimized for storage in the ROM of a target
`computer (referred to herein as the execution engine). Given
`that the execution engine is likely to he a computer with little
`or no secondary storage, it is preferable that the Java class
`preloader be implemented in a separate computer, which
`shall be referred to herein as a server. Assuming such a
`configuration,
`the preloaded classes could be transferred
`from the server to the execution engine in a variety of ways
`(e.g., network connection, direct communication link or
`“sneaker net" transfer of readable media, such as floppy
`disks or CD5]. Accordingly, a preferred embodiment of the
`present invention described herein is directed to a computer
`system with a server and an execution engine wherein the
`preloaded classes are generated by the server and subse-
`quently transferred to the execution engine for use in the
`VM. The preferred embodiment is now described in refer-
`ence to FIGS. 3 and 4.
`
`10
`
`15
`
`3n
`
`35
`
`4!)
`
`45
`
`50
`
`Referring to FIG. 3, there is shown a distributed computer
`system 100 in which the present invention is implemented.
`The computer system 100 has one or more execution
`engines 102 and one or more server computers 104. In a
`preferred embodiment, each execution engine 102 is con-
`nected to the server 104 via the Internet 106, although other
`types of communication connections between the computers
`102, 104 could be used (cg, network connection, direct
`communication link or sneaker net
`transfer of readable
`media, such as floppy disks or CDs). Preferably, the server
`and execution engines are desktop computers, such as Sun
`workstations,
`IBM compatible computers andtor Apple
`Macintosh computers; however, virtually any type of com— _
`puter can be a server or execution engine. Furthermore, the
`system is not limited to a distributed computer system. It
`may be implemented in various computer systems and in
`various configurations, or makes or models of tightly-
`coupled processors or in various configurations of loosely-
`coupled microprocessor systems.
`The server computer 104 typically includes one or more
`processors 112, a communications interface 116, a user
`interface 114, and memory 110. The memory 110 stores:
`an operating system 118;
`an Internet communications manager program or other
`type of network access procedures 12.0;
`
`60
`
`65
`
`16
`
`US 6,658,492 B1
`
`6
`a compiler 122 for translating source code written in the
`Java programming language into a stream of bytecodes;
`a source code repository 124 including one or more
`source code files 126 containing Java source code;
`a class file repOsitory 128 including one or more platform-
`indcpcndent class files 130 and one or more class
`libraries 131 containing class files, each class file
`containing the data representing a particular class;
`a class preloader 132 that generates a set of preloaded
`classes 148 for a particular configuration of the execu-
`tion engine (the class preloader is sometimes referred to
`as a static class loader);
`an assembler 134 that produces an object file representing
`the class members, class data structures and memory
`storage indicators in a format that is recognizable for
`the linker;
`a linker 136 for determining the memory layout for a set
`of preloaded classes and for resolving all symbolic
`references; and
`one or more data files 146 for use by the server (including
`the. preloaded classes 148).
`Note that the clam file repository 128, class preloader 132,
`assembler 134 and linker 136 need not reside on, the server
`104, but can be on any computer whose output {c.g., files or
`messages representing the preloaded classes 148) can be
`copied to the execution engine 102.
`Referring to FIG. 4, an execution engine 102 can include
`one or more processors 202, a communications interface
`206, a user interface 204, a read-only memory 208 and a
`random access memory 210. The read—only memory 208
`stores program methods that have no unresolved references
`and program data that remains constant during program
`operation. In the preferred embodiment, methods and data
`stored in the ROM 208 include portions ofJava applications
`212 and the execution engine’s support procedures. These
`support procedures include an operating system 213, net—
`work accem procedures 214, preloaded classes 232 and
`internal data structures 1200 (FIG. 2} used by the preloaded
`classes 232.
`The random access memory 210 stores:
`a second portion of the Java applications 215 and support
`procedures 216, 217 that contain methods having unre—
`solved references and data that is altered during the
`application’s execution; and
`one or more data files 228 that the execution engine may
`utilize during its processing.
`Referring to FIG. 5, there is shown a flow chart illustrat-
`ing the sequence of steps used to produce a preloaded
`executable module. It should be noted that the method and
`system described herein pertains to prcloading a Java appli—
`cation and other support procedures. Any Java application,
`or any other set of methods that are normally linked at run
`time could be preloaded using the method and system
`described herein.
`The source code 126 for each class that comprises the
`Java application is compiled by the compiler 122 into a class
`file 130, which is a platform-independent representation of
`the class. As described in reference to FIG. 1, the class file
`contains field and method tables, each method‘s bytecodes,
`constant data and other information. Alternatively, the class
`files corresponding to the application can already reside
`in—one or more class libraries 131. The entire .set of class files
`128 that constitute an application to be preloaded are trans-
`mitted to the class preloader 132.
`The job of the class preloader is to generate the preloaded
`
`classes 148 for an execution engine 102 (FIG. 4). The
`
`16
`
`

`

`
`
`10
`
`15
`
`3o
`
`7
`preloaded classes 148 include the class block 1202, method
`blocks 1204,
`field blocks 1214 and constant pool 1224
`described in reference to FIG. 2. Among other things, the
`class preloader 132 determines which methods and fields
`associated with each class 130 can be stored in a read—only
`memory 208 and which must be stored in a random access
`memory device 210. For example, methods that invoke Java
`interfaces or utilize non-static instance variables need to
`reside in random access memory. This is because the byte-
`codes that implement interfaces are determined at runtime
`and non-static instance variables are altered for each instan-
`tiation of the associated class.
`The class preloader 132 also performs a number of
`optimizations in order to produce a more compact internal
`representation of the executable code when that code is
`loaded into the execution engine ROM 208. For example,
`the class preloader 132 combines the constant pools asso-
`ciated with each class to eliminate redundancy in the internal
`representation of the class constant pool 310. In accordance
`with the present
`invention,
`the class preloader 132 also .
`modifies the internal data structures 1200 (FIG. 2A) to take
`up less space in the ROM of the execution engine 102. It is
`an advantage of the present invention that this data structure
`optimization largely frees the internal representation from
`inefficient standard data structure formats 1200 used in the H
`prior art.
`The preloaded classes 148 are transmitted to an assembler
`or compiler 134 that produces an object module 304 having
`the required format for the linker 136 to map the data into
`the appropriate address spaces. Preferably, there will be two
`address spaces, one for a random access memory device and
`a second for read—only memory device. The object module
`304 is then transmitted to the linker 136 which generates a
`memory layout for the classes in the application. Once the
`memory layout is determined, the linker 136 resolves all
`symbolic references and replaces them with direct
`addresses. The memory layout
`is partitioned into the two
`address spaces. The methods and fields that were flagged for
`read-only memory are included in the first address space and
`the methods and data that were flagged as requiring storage
`in a random access memory are included in a second address
`space. The output
`from the linker 136 is a preloaded
`executable module 306 containing the methods and data for
`these two address spaces. The processing flow of the present
`invention is now described with reference to FIG. 6.
`Referring to FIG. 6, there is shown a data flow diagram of
`the process employed by the present invention to reduce the
`memory footprint of internal data structures used by the VM.
`As already described in reference to FIG. 3,
`the class
`preloader 132 generates a set of platform-specific preloaded
`classes 148 from the class files 128. The preloaded classes
`148 are data structure declarations that can be declared in
`assembler source or by a high level language. An assembler
`134 or compiler 122 then converts these data declarations to
`object data 622. The class preloader 132 also determines the _
`most elficient representation of the internal data structures
`1200 composing the preloaded Classes 232.
`In the preferred embodiment a member of the internal
`data structures can be represented in one of two ways:
`1) as a generic memory word (cg, of 32 bits) that is the
`value of the member; or
`2) as an index to a table of disti