Method and circuitry for detecting lost sectors of data in a solid state memory disk

• US 5,437,020 A
• Filed: 10/03/1992
• Issued: 07/25/1995
• Est. Priority Date: 10/03/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wells, Steven, Hasbun, Robert N., Garner, Richard P.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US07/969,723
• Time in Patent Office: 1,025 Days
• Field of Search: 395/400, 395/425
• US Class Current: 714/6.12
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 29/765 in solid state disks
• CPC Class Codes: G11C 29/88 with partially good memories

Abstract

A method of detecting the loss of a sector of data stored in a solid state memory disk is described. Detection is enabled by the creation of a header for each sector number during formatting. Each header includes a logical sector number equal to a sector number. Location and loss of a sector of data associated with a particular sector number is aided by a sector header translation table. The sector header translation table stores an offset, or pointer, for each sector number that points to its associated header. The method by which the sector header translation table is generated aids in the detection of lost sectors of data. Upon power-up, each offset in the sector header translation table is initialized to an initial, invalid value. Afterward, the nonvolatile semiconductor memory is scanned and the sector header translation table is modified so that for each sector number it points to the header including a logical sector number equal to the sector number. As a result, retrieving an invalid offset from the sector header translation table indicates that the sector of data associated with the sector number is lost.

Circuitry for detecting the loss of sector data stored in a solid state memory disk is also described.

Claims

1. A method of detecting the loss of a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory, the sector of data being associated with a sector number, the method comprising the steps of:

a) storing in the nonvolatile semiconductor memory a header for the sector number, the header including an offset to a first physical address for the sector of data;

b) after power-up initializing a pointer to an initial value and storing the pointer in a sector header translation table stored in a volatile semiconductor memory;

c) scanning the nonvolatile semiconductor memory to determine a second value for the pointer such that the pointer points to a physical address for the header;

d) writing the second value for the pointer into the sector header translation table if the second value is determined;

e) scanning the sector header translation table for the pointer in response to a command to locate the sector of data associated with the sector number; and

f) determining that the sector of data associated with the sector number is lost if the pointer is equal to the initial value.

2. The method of claim 1 wherein the nonvolatile semiconductor memory is a FLASH EEPROM.

3. The method of claim 1 wherein the header includes a data attached bit, the data attached bit initially being set to a first state indicating that no data is attached to the header, and wherein the data attached bit is set to a second state indicating that data is attached to header when data is written for the sector number associated with the header.

4. A method of detecting the loss of a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device, the sector of data being associated with a sector number, the method comprising the steps of:

a) storing in the nonvolatile semiconductor memory a header for the sector number, the header including an offset to a first physical address for the sector of data and a logical sector number equal to the sector number;

b) after power-up initializing a pointer to an initial value and storing the pointer in a sector header translation table stored in a volatile semiconductor memory;

c) scanning the nonvolatile semiconductor memory to determine a second value for the pointer such that the pointer points to a physical address for the header;

d) writing the second value for the pointer into the sector header translation table if the second value is determined;

e) scanning the sector header translation table for the pointer in response to a command to locate the sector of data associated with the sector number;

f) locating the header using the pointer; and

g) indicating that the sector of data associated with the sector number is lost if the logical sector number in the header does not equal to the sector number.

5. The method of claim 4 further comprising the steps of:

a) storing a cyclical redundancy check CRC_H for the header in the header; and

b) generating a cyclical redundancy check CRC_G after the step of locating the header using the pointer;

c) indicating that the sector of data associated with the sector number is lost if CRC_G does not equal CRC_H.

6. The method of claim 4 wherein the nonvolatile semiconductor memory is a FLASH EEPROM.

7. The method of claim 4 wherein the header includes a data attached bit, the data attached bit initially being set to a first state indicating that no data is attached to the header, and wherein the data attached bit is set to a second state indicating that data is attached to header when data is written for the sector number associated with the header.

8. A method of detecting the loss of a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device, the sector of data being associated with a sector number, the method comprising the steps of:

a) storing in the nonvolatile semiconductor memory a header for the sector number, the header including an offset to a first physical address for the sector of data and a logical sector number equal to the sector number;

b) after power-up initializing a pointer to an initial value and storing the pointer in a sector header translation table stored in a volatile semiconductor memory;

c) scanning the nonvolatile semiconductor memory to determine a second value for the pointer such that the pointer points to a physical address for the header;

d) writing the second value for the pointer into the sector header translation table if the second value is determined;

e) scanning the sector header translation table for the pointer in response to a command to locate the sector of data associated with the sector number;

f) indicating that the sector of data associated with the sector number is lost if the pointer is equal to the initial value;

g) locating the header using the pointer if the pointer is not equal to the initial value; and

h) indicating that the sector of data associated with the sector number is lost if the logical sector number included in the header does not equal the sector number.

9. The method of claim 8 further comprising the steps of:

a) storing a cyclical redundancy check CRC_H for the header in the header; and

b) generating a cyclical redundancy check CRC_G after the step of locating the header using the pointer;

c) indicating that the sector of data associated with the sector number is lost if CRC_G does not equal CRC_H.

10. The method of claim 8 wherein the nonvolatile semiconductor memory is a FLASH EEPROM.

11. The method of claim 8 wherein the header includes a data attached bit, the data attached bit initially being set to a first state indicating that no data is attached to the header, and wherein the data attached bit is set to a second state indicating that data is attached to header when data is written for the sector number associated with the header.

12. A method of detecting the loss of sector data stored in a solid state memory disk including a nonvolatile semiconductor memory device, the solid state memory disk storing a multiplicity of sectors of data, each sector of data being associated with a sector number, the method comprising the steps of:

a) storing in the nonvolatile semiconductor memory a header for each sector number, each header including a logical sector number and an offset to a physical address of a sector of data associated with the header;

b) after power-up initializing a sector header translation table storing a pointer for each sector number, the pointer pointing to a physical address for the header including with the sector number, initialization setting each pointer to an initial value, the sector header translation table being stored in a volatile semiconductor memory;

c) upon power-up, for each sector number;

1) scanning the nonvolatile semiconductor memory to locate a header including a logical sector number equal to the sector number;

2) determining a physical location of the header if the the logical sector number included in the header is equal to the sector number is located;

3) storing a second value representative of the physical location of the header as the pointer for the sector number;

d) scanning the sector header translation table for a first pointer in response to a command to locate a first sector of data associated with a first sector number;

e) indicating that the first sector of data is lost if the first pointer is equal to the initial value;

f) locating a first header using the first pointer if the first pointer is not equal to the initial value; and

g) indicating that the first sector of data is lost if the first header does not include a first logical sector number equal to the first sector number.

13. The method of claim 12 further comprising the steps of:

a) storing a cyclical redundancy check CRC_H for each header in each header; and

b) generating a cyclical redundancy check CRC_G after the step of locating the first header; and

c) indicating that the first sector of data is lost if CRC_G does not equal CRC_H stored in the first header.

14. The method of claim 12 wherein the nonvolatile semiconductor memory is a FLASH EEPROM.

15. The method of claim 12 wherein the header includes a data attached bit, the data attached bit initially being set to a first state indicating that no data is attached to the header, and wherein the data attached bit is set to a second state indicating that data is attached to header when data is written for the sector number associated with the header.

16. A method of detecting the loss of sector data stored in a solid state memory disk including a nonvolatile semiconductor memory device, the solid state memory disk storing a multiplicity of sectors of data, each sector of data being associated with a sector number, the method comprising the steps of:

a) formatting the nonvolatile semiconductor memory by;

1) generating a header for each sector number, each header including a logical sector number equal to the sector number and a data attached bit, the data attached bit being set to a first state indicating that a sector of data is not attached to the header;

2) allocating a portion of memory within the nonvolatile semiconductor memory for each header, the portion of memory equal to an amount of memory within the nonvolatile semiconductor memory available to store sectors of data divided by a number of headers stored within the nonvolatile semiconductor memory;

3) storing the header for each sector number into the nonvolatile semiconductor memory;

b) after power-up;

1) initializing a sector header translation table by storing a pointer for each sector number, each pointer pointing to a physical address for a header including a logical sector number equal to the sector number, initialization setting each pointer to an initial value, the sector header translation table being stored in a volatile semiconductor memory;

2) for each sector number;

A) scanning the nonvolatile semiconductor memory to locate a header including a logical sector number equal to the sector number;

B) determining a physical location of the header including the logical sector number equal to the sector number;

C) changing the pointer for the sector number to a second value representative of the physical location of the header;

c) scanning the sector header translation table for a first pointer in response to a command to locate a first sector of data associated with a first sector number; and

d) indicating that the first sector of data is lost if the first pointer is equal to the initial value.

17. The method of claim 16 further comprising the steps of:

e) locating a first header using the first pointer if the first pointer is not equal to the initial value; and

f) indicating that the first sector of data is lost if a first logical sector number included in the first header does not equal the first sector number.

18. The method of claim 17 further comprising the steps of:

a) storing a cyclical redundancy check CRC_H for each header in each header;

b) generating a cyclical redundancy check CRC_G after the step of locating the first header; and

c) indicating that the first sector of data is lost if CRC_G does not equal CRC_H stored in the first header.

19. A method of detecting the loss of sector data stored in a solid state memory disk including a nonvolatile semiconductor memory device, the nonvolatile semiconductor memory device organized as blocks of memory, the solid state memory disk storing a multiplicity of sectors of data, each sector of data being associated with a sector number, the method comprising the steps of:

a) formatting the nonvolatile semiconductor memory by;

1) generating a header for each sector number, each header including a logical sector number equal to the sector number and a data attached bit, the data attached bit being set to a first state indicating that a sector of data is not attached to the header;

2) allocating a portion of memory within the nonvolatile semiconductor memory for each header, the portion of memory equal to an amount of memory within the nonvolatile semiconductor memory available to store sectors of data divided by a number of headers stored within the nonvolatile semiconductor memory;

3) storing the header for each sector number into a block of the nonvolatile semiconductor memory, a first maximum number of headers being stored in each block;

b) after power-up initializing a sector header translation table by storing a pointer for each sector number, each pointer pointing to an offset from a top of the block storing the header including a logical sector number equal to the sector number, initialization setting each pointer to an initial value, the sector header translation table being stored in a volatile semiconductor memory;

c) for each sector number;

1) scanning the nonvolatile semiconductor memory to locate the header including a logical sector number equal to the sector number;

2) determining the offset of the header;

3) writing a pointer for the sector number into the sector header translation table;

d) scanning the sector header translation table for a first pointer in response to a command to locate a first sector of data associated with a first sector number;

e) indicating that the first sector of data is lost if the first pointer is equal to the initial value;

f) locating the first header using the first pointer if the first pointer is not equal to the initial value, locating the first header including the steps of;

1) selecting a selected header near the first pointer;

2) comparing a selected logical sector number stored in the selected header to the first sector number;

3) indicating a physical address of the selected header if the selected logical sector number equals the first sector number;

4) repeating steps

     1) through

     3) if the selected logical sector number does not equal the first sector number and if a second maximum number of headers has not been scanned; and

5) indicating that the first sector of data is lost if the second maximum number of headers has been scanned.

20. The method of claim 19 further comprising the steps of:

a) storing a cyclical redundancy check CRC_H for each header in each header;

b) generating a cyclical redundancy check CRC_G after the step of locating the first header; and

c) indicating that the first sector of data is lost if CRC_G does not equal CRC_H stored in the first header.

21. The method of claim 19 wherein the formatting step further comprises:

a) decreasing a first number representative of an amount of free memory within the nonvolatile semiconductor memory by the the portion of memory allocated to each header; and

b) determining whether to allow a second sector of data to be written into the nonvolatile semiconductor memory based upon a comparison of a size of the second sector of data and the first number.

22. The method of claim 19 wherein the nonvolatile semiconductor memory is a FLASH EEPROM.

23. Circuitry for reliably storing sectors of data, each sector of data being associated with a sector number, the circuitry comprising:

a) a nonvolatile semiconductor memory device for storing the sectors of data;

b) a controller for controlling the nonvolatile semiconductor memory device, the controller including;

1) formatting means for formatting the nonvolatile semiconductor memory by generating a header for each sector number and by allocating a portion of memory within the nonvolatile semiconductor memory for each header, the portion of memory equal to an amount of memory within the nonvolatile semiconductor memory available to store sectors of data divided by a number of headers stored within the nonvolatile semiconductor memory, each header including a logical sector number equal to a sector number, an offset representative of a first physical location of the portion of memory allocated to the header, and a data attached bit, the data attached bit being set to a first state indicating that a sector of data is not attached to the header;

2) read/write means for writing a first sector of data associated with a first sector number to the nonvolatile semiconductor device in response to a write command and reading the first sector of data from the nonvolatile semiconductor memory in response to a read command, the read/write means changing the data attached bit in a first header associated with the first sector number from the first state to a second state in response to the write command, the second state indicating that the first sector of data is attached to the first header;

3) seeking means for locating the first header in response to a one of a read command and a write command for the first sector of data associated with the first sector number, the seeking means indicating that the first sector of data is lost if a pointer to the first header is equal to a first value, the seeking means indicating that the first sector of data is lost if the first header does not include a first logical sector number equal to the first sector number; and

c) a sector translation table storing for each sector number a pointer to a physical address for the header including a logical sector number to the sector number.