Data processing: software development – installation – and managem – Software program development tool – Linking
Reexamination Certificate
2000-08-28
2004-01-27
Ingberg, Todd (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Linking
Reexamination Certificate
active
06684394
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a relocation format for linking, and in particular to a method of linking, a linker and a computer program product containing relocation instructions.
BACKGROUND OF THE INVENTION
Linkers for producing executable programs are known. Generally speaking, a linker acts to link a number of object code modules to form a single executable program. Object code modules are usually generated from program source code modules, these modules being written in a high level language. An assembler/compiler reads each source code module and assembles and/or compiles the high level language of the source code module to produce an object code module. The assembler also generates a number of relocations which are used to combine the object code modules at link time in a linker.
The ELF (executable linking format) standard defines a convention for naming relocation sections belonging to a given section, e.g. rela.abc is relocation section of section .abc. Standard relocations under the ELF format allow an offset in section data to be defined where patching is to occur and a symbol whose value is to be patched. A type field also exists which is used to describe the appropriate method of encoding the value of the symbol into the instruction or data of the section data being patched. According to the existing arrangements, the relocation type definitions are usually created on an ad hoc basis for each instruction set targeted. The 32 bit ELF standard allows only 256 distinct relocation types, so the same types are reascribed to different semantics for each instruction set.
The existing linkers each have to be set up to understand the particular semantics used for the type definitions in the relocations for each instruction set. Moreover, the relocation operations which can be defined by the relocations are limited in the existing ELF standard.
It is an object of the invention to provide a more flexible relocation format which, in particular, provides independence from target architecture and allows for user written optimizations of code to be accomplished at link time.
SUMMARY OF THE INVENTION
According to an aspect of the present invention there is provided a method of preparing an executable program from a plurality of object code modules, each module containing sets of section data and relocation instructions, wherein the relocation instructions have an instruction format (e.g. ELF32_relo) including a classification field (r_class) holding a relocation class indicator (RT_BIT) and a set of relocation fields holding relocation data, the meaning of said relocation data depending on the class indicator whereby said instruction format is common to first and second classes of relocations, the method comprising: reading the section data and relocation instructions; determining from the relocation class indicator the class of relocation instruction; and executing relocation operations on the section data based on said relocation data depending on the class of relocation instruction indicated by the relocation class indicator.
The first class of relocation holds relocation data denoting the size and position of a bit field to be patched into the section data. To this end, the relocation fields include a bit start field, a field denoting the length of the bit field in bits and a field denoting the length of the section data offset being patched in bytes.
According to the second class of relocation, the relocation fields denote the type of relocation instruction and may include at least one sub-type field for holding a value the meaning of which depends on the contents of the type field.
The relocation format can comprise at least one argument field for holding a value in either class of relocation, the nature of the value held in the argument field depending on the classification field and the type field.
The novel relocation format defined in the above link method allows a number of novel relocation operations to be carried out.
One novel relocation operation is performing calculations using a stack, the nature of the calculations being defined by relocation data in the second class.
Another relocation instruction causes a value to be pushed onto the stack.
A store relocation instruction pops a value from the stack which is then stored in a condition array for subsequent use at an index which is also conveyed by the store relocation.
A fetch relocation instruction allows the value to be recalled from the condition array and pushed on the stack, the index being supplied with the fetch relocation instruction.
A further relocation operation determines whether or not section data is to be included in the executable program based on resolving a condition. The condition calculations have already been effected by the linker, conveyed by earlier relocations, so that the resultant boolean is on the stack.
A macro call relocation defines a symbol identifying a location in a macro section of an object code module, said macro section including at that location a plurality of code sequences for possible inclusion in the executable program. This relocation also specifies the number of bytes which are replaced by any such included code sequence. In a scheme described later with respect to one embodiment, using marker bytes, it was always the case that one byte was to be replaced by the macro insertion. More generally, however, it can be any non-zero number of bytes planted in the ordinary section to be replaced by the conditional sequence (F) from the macro section. It is nevertheless important that at least one byte is present in order to ensure that different macro calls have different addresses.
Another aspect of the invention provides a linker for preparing an executable program from a plurality of object code modules, each module containing sets of section data and relocation instructions, wherein the relocation instructions have an instruction format including a classification field holding a relocation class indicator and a set of relocation fields holding relocation data, the meaning of said relocation data depending on the class indicator whereby said instruction format is common to first and second classes of relocations, the linker comprising: a relocation module for reading the relocation instructions and for determining from the relocation class indicator the class of relocation instruction; a section data module for holding section data to which the relocation instruction relates; wherein the relocation module executes relocation operations on the section data held in the section data module based on said relocation data depending on the class of relocation instruction indicated by the relocation class indicator.
The linker can comprise a stack for holding values conveyed by the relocation instructions as said relocation data.
The linker can comprise means for implementing calculations conveyed by the relocation instructions using the values on the stack.
The linker can include a condition evaluator for examining the value at the top of the stack to determine whether or not a condition is satisfied, the relocation module being operable to instruct the section data module to conditionally include sequences of the section data in the executable program based on the evaluated condition. It will be understood that unwanted code sequences are deleted.
The linker can comprise a parameter array holding a set of parameters each associated with a respective index, said parameters modifying code sequences for possible inclusion in the executable program.
The linker can comprise a symbol table which holds values in association with symbols, said symbols being conveyed by the relocation instructions.
The linker can include a condition array which holds respective values of associated indexes, the indexes being conveyed by the relocation instructions.
The invention also provides in a further aspect a computer program product in the form of an object code module which contains sets of section data and relocation instructions, wherein the relocation instructions hav
Ingberg Todd
Jorgenson Lisa K.
Morris James H.
STMicroelectronics Limited
Wolf Greenfield & Sacks P.C.
LandOfFree
Relocation format for linking with relocation instructions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Relocation format for linking with relocation instructions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relocation format for linking with relocation instructions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220078