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

• US 6,088,759 A
• Filed: 06/30/1997
• Issued: 07/11/2000
• Est. Priority Date: 04/06/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Edwards, David A., Hasbun, Robert N.
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US08/885,117
• Time in Patent Office: 1,107 Days
• Field of Search: 711/103, 711/170, 711/173, 395/652, 395/182.13, 395/182.04, 365/185.11, 707/206
• 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
• CPC Class Codes: H04M 1/24 Arrangements for testing
• CPC Class Codes: H04Q 11/045 Selection or connection testing arrangements
• CPC Class Codes: H04Q 2213/13034 A/D conversion, code compression/expansion
• CPC Class Codes: H04Q 2213/13096 Digital apparatus individually associated with a subscriber line, digital line circuits
• CPC Class Codes: H04Q 2213/13097 Numbering, addressing
• CPC Class Codes: H04Q 2213/1316 Service observation, testing
• CPC Class Codes: H04Q 2213/13202 Network termination [NT]
• CPC Class Codes: H04Q 2213/13209 ISDN
• CPC Class Codes: H04Q 2213/13217 Cranckback in routing, trombone connection, loopback circuit
• CPC Class Codes: H04Q 2213/13302 Magnetic elements
• CPC Class Codes: H04Q 2213/1332 Logic circuits
• CPC Class Codes: H04Q 2213/13322 Integrated circuits
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Methods of allocating, writing, reading, de-allocating, re-allocating, and reclaiming space within a nonvolatile memory having a bifurcated storage architecture are described. In one embodiment, a method of reliably re-allocating a first object stored within a block erasable nonvolatile memory includes the step of allocating space for a second object. A write of the second object is initiated and the writing of the second object is tracked. In another embodiment, a method of re-allocating a first object stored within a block erasable nonvolatile memory includes the step of invalidating the first object, if the first object has an unreliable type of recovery level. Space is allocated for the second object. A write of the second object is initiated and the writing of the second object is tracked. In another embodiment, a method of reliably re-allocating a first object stored within the block erasable nonvolatile memory includes the step of allocating space for the second object. A write of the second object is initiated and the writing of the second object is tracked. The first object is invalidated after completion of writing the second object, if the first object has a reliable type of recovery. In one embodiment, the first object resides within a first portion of nonvolatile memory and the instructions for performing the described methods reside in a second portion of nonvolatile memory. The first and second portions can reside within a same nonvolatile memory such as a symmetrically blocked flash electrically erasable programmable read only memory.

Claims

1. A method of performing reliable updates in a block erasable nonvolatile memory comprising:

receiving an allocation request to reallocate a first object in said memory with a second object, wherein said first object and said second object have a same name and a same type, and said memory comprising a managed object space arranged into two classes of space to accommodate distinct objects, wherein objects of a first class are stored contiguously proceeding from a first end of said managed object space towards a second end of said managed object space to form a first class of space, and objects of a second class are stored contiguously proceeding from said second end towards said first end to form a second class of space;

validating said allocation request;

allocating a space for said second object if said allocation request is valid;

writing said second object into said space;

tracking a write status of said second object; and

invalidating said first object.

2. The method of claim 1 further comprising determining memory availability during space allocation.

3. The method of claim 1 wherein invalidating said first object occurs when said write status indicates writing of said second object is complete.

4. The method of claim 1 further comprising invalidating said second object if upon initialization, said write status indicates that writing of said second object is incomplete.

5. The method of claim 1 wherein validating said allocation request comprises scanning said memory to locate said first object having a valid status.

6. The method of claim 1 wherein allocating a space for said second object further comprises determining whether sufficient space exists in said memory to accommodate allocating said space for said second object.

7. The method of claim 6 further comprising initiating a reclaim process if insufficient free space exists to allocate said space for said second object.

8. The method of claim 1 wherein said nonvolatile memory comprises symmetrically blocked flash electrically erasable programmable read only memory.

9. The method of claim 1 wherein objects of said first class are page objects and objects of said second class are paragraph objects.

10. A method of reliably rewriting a first object in a block erasable nonvolatile memory comprising:

receiving an allocation request to reallocate a first object in said memory with a second object, said memory comprising a managed object space arranged into two classes of space to accommodate distinct objects, wherein objects of a first class are stored contiguously proceeding from a first end of said managed object space towards a second end of said managed object space to form a first class of space, and objects of a second class are stored contiguously proceeding from said second end towards said first end to form a second class of space;

validating said allocation request;

copying said first object from its associated space to a temporary location;

reclaiming said space associated with said first object;

writing said second object into said space associated with said first object;

tracking a write status of said second object; and

invalidating said first object.

11. The method of claim 10 wherein invalidating said first object occurs when said write status indicates writing of said second object is complete.

12. The method of claim 10 further comprising invalidating said second object if upon initialization, said write status indicates that writing of said second object is incomplete.

13. The method of claim 10 wherein validating said allocation request comprises scanning said memory to locate said first object having a valid status.

14. The method of claim 10 wherein validating said allocation request comprises determining whether said first object and said second object are of a same type and have a same name.

15. The method of claim 10 further comprising determining whether sufficient space exists in said memory to accommodate said second object.

16. The method of claim 15 further comprising generating an error if insufficient space is available.

17. The method of claim 10 wherein said nonvolatile memory comprises symmetrically blocked flash electrically erasable programmable read only memory.

18. The method of claim 10 wherein objects of said first class are page objects and objects of said second class are paragraph objects.

19. A method of reallocating a first object stored within a block erasable nonvolatile memory comprising:

receiving an allocation request to reallocate a first object in said memory with a second object, said memory comprising a managed object space arranged into two classes of space to accommodate distinct objects, wherein objects of a first class are stored contiguously proceeding from a first end of said managed object space towards a second end of said managed object space to form a first class of space, and objects of a second class are stored contiguously proceeding from said second end towards said first end to form a second class of space;

scanning said memory to locate said first object having a valid status and invalidating said first object;

allocating a space for said second object;

writing said second object into said space; and

tracking a write status of said second object.

20. The method of claim 19 further comprising determining memory availability during space allocation.

21. The method of claim 19 further comprising invalidating said second object if upon initialization, said write status indicates that writing of said second object is incomplete.

22. The method of claim 19 further comprising initiating a reclaim process if insufficient free space exists to allocate said space for said second object.

23. The method of claim 19 wherein said nonvolatile memory comprise symmetrically blocked flash electrically erasable programmable read only memory.

24. The method of claim 19 wherein objects of said first class are page objects and objects of said second class are paragraph objects.