Method of performing reliable updates in a symmetrically blocked nonvolatile memory having a bifurcated storage architecture

• US 20040044837A1
• Filed: 09/02/2003
• Published: 03/04/2004
• Est. Priority Date: 04/06/1997
• Status: Active Grant

• Current Assignee: Andrew H. Gafken, Christopher J. Spiegel, David A. Edwards, Robert N. Hasbun
• Original Assignee: Andrew H. Gafken, Christopher J. Spiegel, David A. Edwards, Robert N. Hasbun
• Inventors: Edwards, David A., Hasbun, Robert N., Gafken, Andrew H., Spiegel, Christopher J.
• Granted Patent: US 7,174,416 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 8/654 using techniques specially adapted for alterable solid state memories, e.g. for EEPROM or flash memories
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Methods of allocating, writing, reading, de-allocating, re-allocating, and reclaiming space within a nonvolatile memory having a bifurcated storage architecture are described. A method of reliably re-allocating a first object includes the step of storing a location of a first object in a first data structure. A location of the first data structure is stored in a second data structure. A duplicate of the first object is formed by initiating a copy of the first object. An erase of the first object is initiated. A write of a second object to the location of the first object is then initiated. The duplicate object is invalidated. The status of copying, erasing, and writing is tracked. The copy status, erase status, write status, and a restoration status are used to determine a recovery state upon initialization of the nonvolatile memory. The duplicate object is invalidated, if the writing status indicates that the writing of the second object has been completed. The first object is erased, if a restoration status indicates copying of the duplicate object was initiated but not completed. The erasing of the first object is completed, if the erase status indicates that erasure of the first object is not completed. A restoration of the duplicate object to the location of the first object is initiated, if the copying status indicates that copying of the first object was completed. The copying of the duplicate object is tracked as a restoration status.

Claims

1. A method of re-allocating object space within a block erasable nonvolatile memory, comprising the steps of:

a) storing a location of a first object in a first data structure within the nonvolatile memory;

b) storing a location of the first data structure in a second data structure within the nonvolatile memory;

c) initiating an erase of the first object;

d) tracking an erase status of the first object.

2. The method of claim 1 further comprising the steps of:

e) completing the erase of the first object upon initialization of the nonvolatile memory, if the erase status indicates erasure of the first object has not completed.

3. The method of claim 2 wherein initialization occurs upon re-application of power to the nonvolatile memory.

4. A method of reallocating object space within a block erasable nonvolatile memory, comprising the steps of:

a) storing a location of a first object in a first data structure within the nonvolatile memory;

b) storing a location of the first data structure in a second data structure within the nonvolatile memory;

c) initiating a copy of the first object to form a duplicate object within the nonvolatile memory;

d) tracking a copying status of the first object.

5. The method of claim 4, wherein step a) further comprises the steps of:

i) determining an object class for the first object, wherein objects of a first class are stored contiguously proceeding from a first end towards a second end of a managed object space within the nonvolatile memory to form a first class of space, wherein objects of a second class are stored contiguously proceeding from the second end towards the first end of managed object space to form a second class of space;

ii) storing a first data structure header identifying the first data structure at a bottom of the first class of space; and

iii) storing the first data structure at a selected one of the bottom of the first class of space and a bottom of the second class of space in accordance with the object class of the original object.

6. The method of claim 4 wherein the second data structure is located at a pre-determined position within the nonvolatile memory.

7. The method of claim 4, wherein step c) further comprises the steps of:

i) determining an object class for the first object, wherein objects of a first class are stored contiguously proceeding from a first end towards a second end of a managed object space within the nonvolatile memory to form a first class of space, wherein objects of a second class are stored contiguously proceeding from the second end towards the first end of managed object space to form a second class of space;

ii) storing a duplicate header identifying the duplicate object at a bottom of the first class of space; and

iii) copying the first object to the duplicate object, wherein the duplicate object is located at a selected one of the bottom of the first class of space and a bottom of the second class of space in accordance with the object class of the first object.

8. The method of claim 4 further comprising the step of:

e) marking the duplicate object invalid upon initialization of the nonvolatile memory, if the copying status indicates copying of the first object was initiated but not completed.

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

e) initiating an erase of the first object; and

f) tracking an erase status of the first object.

10. The method of claim 9 wherein the location of the original object identifies every block storing at least a portion of the original object, wherein step e) further comprises the step of:

i) performing the following steps for each selected block storing any portion of the object;

1) copying a bottom portion of the selected block to a temporary storage if the selected block is the first block, wherein the bottom portion is bound by a bottom block boundary of the first block and a beginning of the object;

2) copying a top portion of the last block to the temporary storage if the selected block is the last block, wherein the top portion is bound by an upper block boundary of the last block and an end of the object;

3) erasing the selected block; and

4) copying the temporary storage to the selected block, if the selected block is one of the first and the last blocks.

11. The method of claim 10 wherein the temporary storage is a reclaim block within the nonvolatile memory.

12. The method of claim 9 further comprising the step of:

g) completing the erase of the first object upon initialization of the nonvolatile memory, if the erase status indicates that erasure of the first object is not completed.

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

h) initiating a copy of the duplicate object to the location of the first object upon initialization of the nonvolatile memory, if the copying status indicates that copying of the first object was completed; and

i) tracking a restoration status of the copying of the duplicate object.

14. The method of claim 13 further comprising the step of:

j) returning to step e) if the restoration status indicates that copying of the duplicate object has been initiated but is not complete.

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

g) initiating a write of a second object to the location of the first object; and

h) tracking a writing status of the writing of the second object.

16. The method of claim 15 further comprising the step of:

i) returning to step e) upon initialization of the nonvolatile memory, if the writing status indicates that the writing of the second object has been initiated but not completed.

17. The method of claim 15 further comprising the step of:

i) invalidating the duplicate object upon initialization of the nonvolatile memory, if the writing status indicates that the writing of the second object has been completed.

18. The method of claim 4 wherein the nonvolatile memory comprises flash electrically erasable programmable read only memory.

19. The method of claim 4 wherein the nonvolatile memory is a symmetrically blocked nonvolatile memory.

20. The method of claim 4 wherein the nonvolatile memory is coupled to a processor, wherein executable instructions for performing steps a), b), c), d), and e) are stored in the nonvolatile memory, wherein the processor executes the executable instructions.

21. The method of claim 4 wherein the nonvolatile memory is a boot device.