US6154877A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for portable checkpointing using data structure metrics and conversion functions
Assignee: University of Iowa Research Foundation
•
Filing: 1997-08-15
•
Granted: 2000-11-28
•
Expires: 2017-08-15
Abstract
Abstract A method and apparatus for portable checkpointing comprising the steps of: pre-compiling an input application source code and basic data type conversion functions; and outputting an associated output application source code and structure metrics and conversion function source code, wherein the output application source code includes support for portable checkpointing. The portability of the checkpoints allows migration between systems with different hardware, software, and operating systems. The present invention additionally provides a method and apparatus for conversion of data representations between a local machine format and a Universal Checkpoint Format (UCF) and a method for pointer handling, which involves transforming as absolute pointer into a machine independent offset and vice versa.
Inventors
- 👤 Balkrishna Ramkumar
- 👤 Volker Strmupen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 00:03
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1438
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
87 words
A method for portable checkpointing comprising the steps of: pre-compiling an input application source code and basic data type conversion functions; and outputting an associated output application source code and structure metrics and conversion function source code, wherein the output application source code includes support for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 2
Independent Claim
87 words
A method for portable checkpointing comprising the steps of: pre-compiling an input application source code and basic data type conversion functions; and outputting an associated output application source code and structure metrics and conversion function source code, wherein the output application source code includes support for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 3
Dependent Claim
25 words
The method for portable checkpointing of claim 1, wherein the basic data type conversion functions include a separate conversion function for each target machine architecture.
Claim 4
Dependent Claim
28 words
The method for portable checkpointing of claim 1, wherein the structure metrics and conversion function source code includes code associated to structures in the input application source code.
Claim 5
Dependent Claim
40 words
The method for portable checkpointing of claim 1, comprising the further step of: compiling the output application source code and structure metrics and conversion function source code to produce application object code and a structure metric and conversion library, respectively.
Claim 6
Dependent Claim
26 words
The method for portable checkpointing of claim 4, wherein said compiling step includes compiling shadow library for runtime support source code to produce a shadow library.
Claim 7
Dependent Claim
30 words
The method for portable checkpointing of claim 4, comprising the further step of: linking the application object code and the structure metric and conversion library to produce application executable code.
Claim 8
Dependent Claim
33 words
The method for portable checkpointing of claim 5, comprising the further step of: linking the application object code, the structure metric and conversion library, and the shadow library to produce application executable code.
Claim 9
Dependent Claim
44 words
The method for portable checkpointing of claim 1, wherein said step of pre-compiling includes the sub-steps of: identifying data structures in the input application source code that need to be checkpointed; generating a shadow structure; and creating a structure metric to store conversion-specific information.
Claim 10
Dependent Claim
20 words
The method for portable checkpointing of claim 1, wherein the input application source code includes a general-purpose programming language code.
Claim 11
Dependent Claim
17 words
The method for portable checkpointing of claim 1, wherein the input application source code includes C code.
Claim 12
Independent Claim
115 words
A system for portable checkpointing, comprising: a marker inserter for receiving original source code, and inserting markers for support of portable checkpointing to produce input source code; and a pre-compiler, coupled to said marker inserter, for pre-compiling the input application source code and basic data type conversion functions, and for outputting an associated output application source code and structure metrics and conversion function source code, wherein the output application source code includes support for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 13
Independent Claim
115 words
A system for portable checkpointing, comprising: a marker inserter for receiving original source code, and inserting markers for support of portable checkpointing to produce input source code; and a pre-compiler, coupled to said marker inserter, for pre-compiling the input application source code and basic data type conversion functions, and for outputting an associated output application source code and structure metrics and conversion function source code, wherein the output application source code includes support for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 14
Independent Claim
77 words
A method for generating a structure metric for portable checkpointing, comprising: identifying data structures in an input application source code that need to be checkpointed; generating a shadow structure; and creating a structure metric to store conversion-specific information, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 15
Independent Claim
77 words
A method for generating a structure metric for portable checkpointing, comprising: identifying data structures in an input application source code that need to be checkpointed; generating a shadow structure; and creating a structure metric to store conversion-specific information, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size.
Claim 16
Independent Claim
83 words
A method for generating a pre-compiler for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, comprising: creating pre-compiler source code and architecture-specific configuration files; gathering metrics on the architecture-specific configuration files to produce a metric file; and compiling the pre-compiler source code and the metric file to generate a pre-compiler.
Claim 17
Independent Claim
83 words
A method for generating a pre-compiler for portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, comprising: creating pre-compiler source code and architecture-specific configuration files; gathering metrics on the architecture-specific configuration files to produce a metric file; and compiling the pre-compiler source code and the metric file to generate a pre-compiler.
Claim 18
Independent Claim
90 words
A method for run-time support of pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: pushing objects on a shadow stack; identifying which of the objects include pointers; generating an associated offset value for the identified pointers and objects that are pointed to; and adding the associated offset value to the shadow stack.
Claim 19
Independent Claim
90 words
A method for run-time support of pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: pushing objects on a shadow stack; identifying which of the objects include pointers; generating an associated offset value for the identified pointers and objects that are pointed to; and adding the associated offset value to the shadow stack.
Claim 20
Dependent Claim
23 words
The method for run-time support of claim 14, wherein said step of adding comprises replacing the identified pointer with the associated offset value.
Claim 21
Dependent Claim
24 words
The method for run-time support of claim 14, further comprising the step of: placing objects that can be pointed to on an object stack.
Claim 22
Dependent Claim
29 words
The method for run-time support of claim 16, further comprising the step of: searching the object stack for a target address of at least one of the identified pointers.
Claim 23
Dependent Claim
32 words
The method for run-time support of claim 17, further comprising the steps of: finding the identified pointer's target address on the object stack; and putting the identified pointer on a pointer stack.
Claim 24
Dependent Claim
26 words
The method for run-time support of claim 17, further comprising the step of: finding that the identified pointer's target address is not on the object stack.
Claim 25
Dependent Claim
32 words
The method for run-time support of claim 16, wherein said step of placing the objects that can be pointed to on the object stack comprises placing object information on the object stack.
Claim 26
Dependent Claim
36 words
The method for run-time support of claim 20, wherein the object information includes at least one of an address on a run-time stack, a size on the run-time stack, and an address on the shadow stack.
Claim 27
Dependent Claim
42 words
The method for run-time support of claim 14, wherein the associated offset value is the difference between a pointer address on the shadow stack of the pointer and an object address on the shadow stack of the object that is pointed to.
Claim 28
Dependent Claim
22 words
The method for run-time support of claim 14, wherein at least one of the objects that includes a pointer is a pointer.
Claim 29
Dependent Claim
21 words
The method for run-time support of claim 14, further comprising a step of: determining if the object can be pointed to.
Claim 30
Dependent Claim
18 words
The method for run-time support of claim 24, wherein said step of determining is based upon compile-time information.
Claim 31
Independent Claim
87 words
A method for run-time support of forward pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: completing pushing of objects on a shadow stack; locating forward pointers in the shadow stack; calculating an associated offset value for each forward pointer; and inserting the associated offset values in the shadow stack.
Claim 32
Independent Claim
87 words
A method for run-time support of forward pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: completing pushing of objects on a shadow stack; locating forward pointers in the shadow stack; calculating an associated offset value for each forward pointer; and inserting the associated offset values in the shadow stack.
Claim 33
Dependent Claim
23 words
The method for run-time support of claim 26, wherein said step of inserting comprises replacing the forward pointer with the associated offset value.
Claim 34
Dependent Claim
43 words
The method for run-time support of claim 26, wherein the associated offset value is the difference between a pointer address on the shadow stack of the forward pointer and an object address on the shadow stack of an object that is pointed to.
Claim 35
Independent Claim
77 words
A method for supporting portable checkpointing of heap data structures, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: providing a customized memory allocator; maintaining a used list with pointers to allocated memory blocks; and extending a memory block header to include additional information.
Claim 36
Independent Claim
77 words
A method for supporting portable checkpointing of heap data structures, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, the method comprising: providing a customized memory allocator; maintaining a used list with pointers to allocated memory blocks; and extending a memory block header to include additional information.
Claim 37
Dependent Claim
30 words
The method for supporting portable checkpointing of claim 29, wherein the additional information includes at least one of a tag, a shadow address, and a pointer to a type metric.
Claim 38
Independent Claim
36 words
A method for portable checkpointing of heap data structures, comprising: scanning a used list for pointers; pushing a pointed to heap object on to a shadow stack; and performing garbage collection based on said scanning step.
Claim 39
Independent Claim
36 words
A method for portable checkpointing of heap data structures, comprising: scanning a used list for pointers; pushing a pointed to heap object on to a shadow stack; and performing garbage collection based on said scanning step.
Claim 40
Independent Claim
73 words
A method for run-time support of pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, comprising: identifying which objects for checkpointing include pointers; and generating an associated offset value for the identified pointers and objects that are pointed to.
Claim 41
Independent Claim
73 words
A method for run-time support of pointers during portable checkpointing, wherein the portable checkpointing provides at least one portable checkpoint that can be executed on a destination platform that is independent of operating system restrictions and processor restrictions including one of memory page size, firmware byte-ordering and word size, comprising: identifying which objects for checkpointing include pointers; and generating an associated offset value for the identified pointers and objects that are pointed to.
References Cited (Backward Citations)
US5146460A
Cited
US5583988A
Cited
US5440726A
Cited
US5530802A
Cited
US5590277A
Cited
US5630047A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-28 | 2004-05-29 | 2004-11-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-28 | 2008-05-29 | 2008-11-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-28 | 2012-05-29 | 2012-11-28 | $7700.00 | Window Closed / Lapsed |