Method for verification and restoration of directories in CPU system managed store

• US 5,675,767 A
• Filed: 11/10/1992
• Issued: 10/07/1997
• Est. Priority Date: 07/19/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tetzlaff, William Harold, Baird, Robert, Guyette, Richard Roland, Lett, Alexander Stafford, Beretvas, Thomas, Myers, James Joseph, Hodges, Paul, Bozman, Gerald Parks
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US07/973,937
• Time in Patent Office: 1,792 Days
• Field of Search: 395/400, 395/575, 395/483, 395/486, 395/489, 395/182.3, 365/200, 365/201, 371/10.1 T, 371/21.1, 371/21.2, 364/DIG. 1
• US Class Current: 711/156
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

A method for dynamically detecting loss of map integrity in a form of system-managed storage (SMS). In SMS, maps are used to define access paths to data and to allocate and reallocate storage resources among applications running thereon. The method steps include incorporating as an indivisible part of an overwriting commmand the duplication of map information by appending a portion of it to each data block in store, and detecting loss of map integrity as a function of a comparison mismatch between the portion stored with a counterpart data block and the map upon each read/write access.

Claims

1. In a system having a central processing unit (CPU), a system managed store (SMS) for data blocks and at least one map defining each data block location and description of said block, and means responsive to applications executing on said CPU for reading and writing said data blocks and updating said map in the SMS by way of indivisible (atomic) operations, a method for ensuring integrity of said map comprising the steps of:

(a) duplicating a portion of the map pertinent to a data block, appending the duplicated portion to said data block, and writing both into a non-volatile segment of SMS as an indivisible part thereof;

(b) responsive to each read and write operation and forming an indivisible part thereof, matching the portion stored with the counterpart data block and the portion resident in the map; and

(c) upon any comparison mismatch between the portions, reconstructing said map from a sorted subset of the duplicated portions of the data blocks, said portions being limited to information having the same type as the map.

2. The method according to claims 1, wherein the duplicated portion is appended to the data block as a SUFFIX thereto.

3. The method according claim 1, wherein said reading and writing means deletes data blocks by removing their counterpart map entries and erases data blocks by overwriting their SMS non-volatile locations, and further wherein said reconstructing step includes using the appended portions of deleted data blocks but not those of erased blocks.

12. The method according to any one of the claims 1, 4, or 7, wherein the inclusion of name and attribute fields in the SUFFIX permits recovery of a directory form of a map.

4. A central processing unit (CPU) implemented method for dynamically detecting loss of map integrity in system managed storage (SMS), said maps being used to define access paths to data blocks located in SMS, said maps being a concordance of arbitrary block identifiers (names), block attributes, non-volatile SMS address, and other fields,

CPU applications providing access path arguments in the form of the identifiers (names), said path arguments being used by said SMS to index said maps, comprising the steps of:

(a) responsive to an initial write access, indivisibly creating a map entry for a new data block, duplicating at least a portion of the entry and appending the duplicated portion to said new data block, and writing both into a non-volatile segment of SMS;

(b) responsive to each subsequent read access or each subsequent write access, indivisibly matching the portion of the map entry appended and stored with the accessed data block and the counterpart map entry or portion thereof, and providing indication upon any comparison mismatch; and

(c) upon a mismatch, rebuilding said map or part thereof by rewriting the map or part thereof as a sorted subset of the entries appending each data block.

5. The method according to claim 4, wherein the duplicated portion is appended to each data block as a SUFFIX thereto.

6. The method according to claim 4, wherein the map entry and the duplicated portion of said entry as comparison matched in step (b) includes fields constituting a concordance between file and data block identifiers, virtual storage addresses in SMS, and non-volatile SMS addresses.

7. A method for ensuring verification and recovery of a central processing unit (CPU) based system managed store (SMS) from information corruption in maps, said maps defining the access paths between an application running on said CPU and data blocks located in the SMS, said SMS providing a virtual address interface between the application and the real storage within SMS, said maps including a first concordance between an application provided data block identifier and its virtual address, and, a second concordance between the virtual address and its real address in SMS, comprising the steps of:

(a) upon the initial writing of a data block to SMS, indivisibly executing the following substeps of making predetermined types of map entries, duplicating at least a portion of said entries, appending said duplicate portion to the data block as a SUFFIX, and recording both concurrently to SMS;

(b) responsive to each subsequent read or write access to the data block, indivisibly accessing said data block by way of a map defined path to a real storage address in SMS, and matching said SUFFIX of the accessed data block with the counterpart map entry; and

(c) in the event of a mismatch, rebuilding said map or part thereof by rewriting the map using a sorted subset of the SUFFIXES of said data block or blocks.

8. The method according to claim 7, wherein said map entry and SUFFIX including at least a data block identifier communicated from an application executing on said CPU, an SMS address, validity checking codes, data block attributes, and other fields;

and further wherein said method includes the step of localizing said source of map information corruption insofar as invalid checking codes being indicative of error in the SMS write path either because the CPU was either NOT notified of the fault location or the CPU itself was faulty.

9. The method according to claim 8, wherein said other fields includes a block status field in which the extent of replication of an object is maintained.

10. The method according to claim 7, wherein the rebuilding step includes the steps of replicating SUFFIXES and executing a an n-way sort among the n fields thereof.

11. The method according to claim 7, wherein the steps of duplicating at least a portion of a map entry, appending said duplicate portion to the data block as a SUFFIX, and recording both concurrently to SMS inclusively and indivisibly form steps within all write operations both at the time of data block creation in SMS and subsequently thereto.