File system for a data storage device having a power fail recovery mechanism for write/replace operations

• US 5,559,957 A
• Filed: 05/31/1995
• Issued: 09/24/1996
• Est. Priority Date: 05/31/1995
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Balk, Michael W.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Decady, Albert
• Application Number:
  US08/455,926
• Time in Patent Office: 482 Days
• Field of Search: 395/180, 395/181, 395/182.21, 395/182.12, 395/650, 395/750, 364/260.8, 364/280.2, 364/280.3, 364/273.4
• US Class Current: 714/23
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

The present invention provides a method and apparatus in a data storage device of a data storage system under the control of a microprocessor for preventing a microprocessor stall upon the occurrence of a power failure during read/write operations. During normal operations, files are written to a first storage area of the data storage device where a first flag associated with each file is set when the writing of the respective file has successfully completed. Upon the occurrence of a power failure, a data storage device initialization routine is commenced upon reboot of the microprocessor. During initialization, an analysis phase is begun to generate sequences of events for at least those files not having the first flag set. The events comprise memory operations and associated data and are each re-executable upon interruption of its execution and before execution of another event without modifying results of a previous execution of the respective event. The events generated are then written to an event storage area in the data storage device. During an execution phase of the data storage device initialization, the events are retrieved and executed by the microprocessor to cause the files having at least the first flag set to be written in a compacted manner to storage locations in a second storage area of the memory device to maintain the integrity of those files. Subsequently, the first storage area of the memory device is erased to provide additional storage space for the writing of new files to the memory device. If a power failure or system failure occurs during the two-phase initialization process, the process is re-started generally at the point where it was interrupted so as not to leave the data storage device in a partially compacted, and hence, a potentially inconsistent state.

Claims

1. In a data storage device under control of microprocessor and having storage locations for storing files written to the data storage device, a method is provided for preventing a microprocessor stall during reboot of the microprocessor and initialization of the data storage device, the method comprising the steps:

writing files to a first storage area of the data storage device;

tagging those files successfully written to the first storage area of the data storage device with a first tag; and

commencing initialization of the data storage device upon reboot of the microprocessor, the data storage device initialization forming a garbage collection routine comprising the steps of

tagging files stored in the first storage area of the data storage device comprising unwanted files which are no longer desired for use with a second tag, and

erasing files stored in the first storage area of the data storage device comprising files not tagged with the first tag and files tagged with the second tag.

2. The method of claim 1, wherein the step of erasing files stored in the first storage area of the data storage device comprising files not tagged with the first tag and files tagged with the second tag comprises the steps of:

copying both the files tagged with the first tag and the files not tagged with a second tag stored in the first storage area to a second storage area of the data storage device; and

erasing the files stored in the first storage area of the data storage device.

3. The method of claim 2, wherein the second storage area comprises one of a storage area disposed within the first storage area and a storage area disposed outside of the first storage area.

4. The method of claim 2, wherein the data storage device comprises a read-mostly memory device.

5. The method of claim 4, wherein the event storage area comprises a storage area disposed outside of the first storage area.

6. The method of claim 4, wherein the read-mostly memory device comprises one of EEPROM memory device and a FLASH memory device.

7. The method of claim 4, wherein the event storage area comprises a storage area disposed outside of the first storage area.

8. In a data storage device under control of microprocessor and having storage locations for storing files written to the data storage device, a method is provided for preventing a microprocessor stall during reboot of the microprocessor and initialization of the data storage device, the method comprising the steps:

writing files to a first storage area of the data storage device;

tagging those files successfully written to the first storage area of the data storage device; and

commencing initialization of the data storage device upon reboot of the microprocessor, the data storage device initialization comprising the steps of

generating sequences of executable events comprising memory operations and associated data for untagged files which when executed cause the untagged files to be removed from the data storage device,

writing the generated events to an event storage area in the data storage device, and

executing the events written to the event storage area of the data storage device to remove the untagged files from the first storage area of the data storage device.

9. The method of claim 8, wherein the event storage area is disposed outside of the first storage area of the data storage device.

10. The method of claim 8, wherein the data storage device comprises a read-mostly memory device having a flat file structure in which files are read from and written to the data storage device in a contiguous manner.

11. The method of claim 10, wherein the event storage area is disposed outside of the first storage area of the read-mostly memory device.

12. The method of claim 8, wherein the events comprise memory operations and associated data and are each re-executable upon interruption of an execution of a respective event and before execution of another event without modifying results of a previous execution of the respective event.

13. The method of claim 12, wherein the data storage device comprises a read-mostly memory device.

14. The method of claim 12, wherein the data storage device comprises one of an EEPROM memory device and a FLASH memory device, and wherein the event storage area is disposed outside of the first storage area of the data storage device.

15. In a data storage system comprising a microprocessor for controlling access to a data storage device, the data storage device having storage locations for contiguously storing files written to the data storage device, a method is provided for ensuring the integrity of files written to the data storage device upon the occurrence of a failure comprising one of a power failure and a system failure in the data storage system, the method comprising the steps of:

(a) writing files to a first storage area of the data storage device;

(b) tagging with a first tag those files successfully written to the first storage area of the data storage device; and

(c) commencing initialization of the data storage device after occurrence of a failure, the initialization of the data storage device comprising the steps of

(1) commencing a garbage collection analysis routine comprising the steps of

(a) tagging with a second tag those files stored in the first storage area of the data storage device determined to be unwanted files no longer desired for use, and

(b) writing to an event storage area of the data storage device sequences of executable events for files comprising one of files not tagged with the first tag and files tagged with the second tag, the sequences of executable events comprising memory operations and associated data which when executed cause the unwanted files to be removed from the data storage device,

(2) commencing a garbage collection execution routine comprising the steps of;

(a) executing the events written to the event storage area to cause the files tagged with the first tag and not tagged with the second tag to be copied from respective source storage locations in the first storage area to respective destination storage locations in a second storage area and further cause the files stored in the first storage area to be erased, and

(b) setting an event executed flag for each event in the event storage area of the data storage device upon successful execution of each individual event, and

(3) erasing the events stored in the event storage area of the data storage device.

16. The method of claim 15, wherein when the failure does not occur during the step (c), the method further comprises the step of proceeding to step (c) to commence initialization of the data storage device.

17. The method of claim 15, wherein when the failure occurs during the step (c), the method further comprises the steps of:

erasing the events stored in the event storage area of the data storage device and returning to step (c)(1) to commence a new garbage collection analysis routine if the failure occurred in the step (c)(1); and

returning to step (c)(2) to commence or resume execution of events stored in the event storage area of the data storage device if the failure occurred in the step (c)(2).

18. The method of claim 17, wherein the step of returning to step (c)(2) to commence or resume execution of events stored in the event storage area of the data storage device if the failure occurred in step (c)(2) comprises the step of executing those events not having an event executed flag set starting with the first event stored in the event storage area not having its event executed flag set.