Method for locating sector data in a memory disk by examining a plurality of headers near an initial pointer

• US 5,471,604 A
• Filed: 10/30/1992
• Issued: 11/28/1995
• Est. Priority Date: 10/30/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wells, Stephen, Hasbun, Robert N.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US07/969,780
• Time in Patent Office: 1,124 Days
• Field of Search: 395/400, 395/425
• US Class Current: 711/4
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system

Abstract

A method of allocating free physical memory in a solid state memory disk for a sector of data of a given size is described. Allocation begins by determining the amount of free physical memory in each block of the solid state memory disk. Afterward, the block with the greatest amount of free physical memory is selected. Sufficient free memory to store the sector of data is reserved in the selected block, provided the amount of free memory within selected block exceeds the given size of the sector of data.

A method of allocating free physical memory for sectors of user data stored within a block that is the focus of clean-up is also described.

A method of locating a sector of data stored in a solid state memory disk given a sector number and a pointer to a block sector translation table of a block is also described.

Claims

1. A method of locating a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device having a block, the block including a block translation table storing headers and a data space storing sectors of data, the method comprising the steps of:

a) receiving an input sector number and a pointer into the block translation table;

b) initializing a scan count;

c) selecting a selected header from a multiplicity of headers near a location pointed to by the pointer, each of the multiplicity of headers including a selected logical sector number, a selected offset representing an offset to a selected sector of data associated with the selected logical sector number;

d) indicating the selected offset if the selected logical sector number of the selected header equals the input sector number;

e) incrementing the scan count if the selected logical sector number does not equal the input sector number;

f) comparing the scan count to a maximum scan count; and

g) repeating steps c) through f) once for each of a set of headers which excludes the selected header if the scan count is not equal to the maximum scan count.

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

3. A method of locating a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device having a block, the block including a block translation table storing headers and a data space storing sectors of data, the method comprising the steps of:

a) receiving an input sector number and a first pointer into the block translation table;

b) initializing a scan count;

c) selecting a selected header from a multiplicity of headers near a location pointed to by the first pointer, each of the multiplicity of headers including a selected logical sector number, a selected offset representing an offset to a selected sector of data associated with the selected logical sector number, and including a selected cyclical redundancy check for the selected header;

d) if the selected logical sector number of the selected header equals the input sector number;

1) generating a first cyclical redundancy check for the selected header;

2) indicating the selected offset and ending if the selected cyclical redundancy check equals the first cyclical redundancy check;

3) incrementing the scan count if the first cyclical redundancy check does not equal the selected cyclical redundancy check;

e) if the selected logical sector number does not equal the input sector number incrementing the scan count;

f) comparing the scan count to a maximum scan count, the maximum scan count equal to a maximum number of headers in the block translation table divided by a maximum number of pointers into the block; and

g) repeating steps c) through f) once for each of a set of headers which excludes the selected header if the scan count is not equal to the maximum scan count.

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

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

h) marking the selected header dirty if the selected logical sector number is equal to the input sector number and the selected cyclical redundancy check does not equal the first cyclical redundancy check.

6. The method of claim 3 further comprising the step of:

h) indicating that a first sector of data associated with the input sector number cannot be found if the scan count equals the maximum scan count.

7. The method of claim 3 prior to the step of initializing the scan count further comprising the steps of:

a.1) reading a next header located in a predetermined location relative to a last located header in the block translation table, the next header including a next logical sector number, a next offset representing an offset to a next sector of data associated with the next sector number;

a.2) indicating the next offset if the next logical sector number equals the input logical sector number; and

a.3) continuing locating the sector of data if the next logical sector number does not equal the input logical sector number.

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

h) comparing the first pointer to an invalid pointer value; and

i) indicating a first sector of data associated with input sector number cannot be found and ending if the first pointer is equal to the invalid pointer value.

9. The method of claim 3 prior to the step of initializing the scan count further comprising the steps of:

a.1) reading a next header located in a predetermined location relative to a last located header in the block translation table, the next header including a next logical sector number, a next cyclical redundancy check for the next header, a next offset representing an offset to a next sector of data associated with the next logical sector number;

a.2) if the next logical sector number equals the input sector number

1) generating a second cyclical redundancy check for the next header;

2) indicating the next offset if second cyclical redundancy check equals the next cyclical redundancy check;

3) indicating that a first sector of data associated with the input sector number cannot be found if the second cyclical redundancy check does not equal the next cyclical redundancy check; and

a.3) continuing locating the sector of date if the next logical sector number does not equal the input sector number.

10. A method of locating a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device having a block, the block including a block translation table storing headers and a data space storing sectors of data, comprising the steps of:

a) receiving an input sector number and a pointer into the block translation table;

b) initializing a scan count; and

c) repeating the steps of

c.1) selecting a selected header from a multiplicity of headers near a location pointed to by the pointer, each of the multiplicity of headers including a selected logical sector number, a selected offset representing an offset to a selected sector of data associated with the selected logical sector number;

c.2) indicating the selected offset if the selected logical sector number of the selected header equals the input sector number; and

c.3) incrementing the scan count if the selected logical sector number does not equal the input sector number;

until a maximum scan count is reached or the selected logical sector number of the selected header equals the input sector number.

11. A method of locating a sector of data stored in a solid state memory disk including a nonvolatile semiconductor memory device having a block, the block including a block translation table storing headers and a data space storing sectors of data, comprising the steps of:

a) receiving an input sector number and a pointer into the block translation table;

b) initializing a scan count; and

c) repeating the steps of

c.1) selecting a selected header from a multiplicity of headers near a location pointed to by the pointer, each of the multiplicity of headers including a selected logical sector number, a selected offset representing an offset to a selected sector of data associated with the selected logical sector number;

c.2) if the selected logical sector number does not equal the input sector number incrementing the scan count

c.3) if the selected logical sector number of the selected header equals the input sector number,

c.3.a) generating a first cyclical redundancy check for the selected header;

c.3.b) indicating the selected offset and ending if the selected cyclical redundancy check equals the first cyclical redundancy check; and

c.3.c) incrementing the scan count if the first cyclical redundancy check does not equal the selected cyclical redundancy check;

until a maximum scan count is reached or the selected logical sector number of the selected header equals the input sector number and the selected cyclical redundancy check equals the first cyclical redundancy check.

12. A method of locating a sector of data stored in a solid state memory disk including a non-volatile memory device which includes an organizational data structure storing a plurality of data descriptors and a data space for storing a plurality of sectors described by the plurality of data descriptors, comprising the steps of:

a) receiving an input sector number and a pointer to an initial location in the organizational structure;

b) initializing a scan count;

c) reading a data descriptor for a stored sector, the data descriptor containing a stored sector number and an offset of the stored sector into the data space;

d) incrementing the scan count if the stored sector number does not correspond to the input sector number;

e) repeating steps c) through e) for a plurality of different data descriptors until the scan count reaches a maximum count if the stored sector number does not correspond to the input sector number; and

f) indicating the offset if the stored sector number corresponds to the input sector number.