Increased reliability of data stored on flash memory in applications sensitive to power-loss

• US 6,839,823 B1
• Filed: 09/29/2000
• Issued: 01/04/2005
• Est. Priority Date: 04/21/1998
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: del Pozo, Phillip J. III, Dunlap, Jeffrey A., See, Deborah L., Hasbun, Robert N., Garner, Richard P.
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US09/675,578
• Time in Patent Office: 1,558 Days
• Field of Search: 711/103, 711/85, 711170-173, 711/159, 711/165, 707/205
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

Methods for storing data in an erasable nonvolatile memory are described herein. In one embodiment, an example method includes allocating a space within a block of an erasable nonvolatile memory for an object, wherein the allocated space is within a single block of the erasable nonvolatile memory and the allocated space includes a plurality of areas capable of storing multiple instances of the object, storing a first instance of the object in one of the areas within the allocated space, storing a superseding second instance of the object in another one of the areas within the allocated space without erasing any of the allocated space, and for each of the first and second instances of the object, storing status information corresponding to the respective instance of the object within the allocated space which is within the single block of the erasable nonvolatile memory.

Claims

1. A method of storing objects in a nonvolatile memory comprising:

allocating a space within a block of an erasable nonvolatile memory for an object, wherein the allocated space is within a single block of the erasable nonvolatile memory and the allocated space includes a plurality of areas capable of storing multiple instances of the object;

storing a first instance of the object in one of the areas within the allocated space;

storing a superseding second instance of the object in another one of the areas within the allocated space without erasing any of the allocated space; and

for each of the first and second instances of the object, storing status information corresponding to the respective instance of the object within the allocated space which is within the single block of the erasable nonvolatile memory.

2. The method of claim 1, further comprising:

updating status information within the allocated space to reflect that the second instance supersedes the first instance.

3. The method of claim 1, further comprising:

storing a header within a same block as the allocated space, wherein the header identifies a location of the allocated space within the same block.

4. The method of claim 1, wherein the nonvolatile memory is a flash electrically erasable programmable read only memory.

5. The method of claim 1, wherein the status information includes at least one of an empty status indicating that the corresponding instance contains unused data, an allocating status indicating that the corresponding instance is being allocated, an invalidate status indicating that an invalidation is in progress on the corresponding instance, an allocated status indicating that the corresponding instance is being written, a valid status indicating that the corresponding instance holds valid data, and an invalid status indicating that the corresponding instance holds invalid data.

6. The method of claim 3, wherein the header includes a first field indicating a size of an instance of the object, and wherein the size of the instances is used to determine a location of an instance.

7. The method of claim 6, wherein the header further includes a second field indicating a number of the instances of the object currently stored within the allocated space, which is within single block of the erasable nonvolatile memory, and wherein the number of the instances currently stored is used to determined whether more instances can be stored within the same block.

8. A method comprising:

receiving data for storage in a nonvolatile memory comprising a plurality of blocks;

selecting a storage structure for the data according to a size (z) of the data, a minimum number of instances (m), a maximum single instance size (s*g), and an allocation granularity (g); and

storing the data in the selected structure within the nonvolatile memory, each of the plurality of blocks including at least one selected structures and each of the structure storing an instance of the data and the status for the respective instance within the same block.

9. The method of claim 8, wherein selecting the storage structure includes selecting a multiple instance structure, if $z\le$

g-overheadm,

wherein the overhead is an amount of space required as overhead for m instances within the multiple instance structure.

10. The method of claim 8, wherein selecting the storage structure further includes selecting a single instance structure, if z·

s*g for s expressed as a number of granular units.

11. The method of claim 8, wherein selecting the storage structure further includes fragmenting the data into a plurality of data fragments for storage, if z>

s*g for s expressed as a number of granular units.

12. The method of claim 11, wherein storing the data includes:

storing the data fragments using a sequence table indicative of an order and a location of the data fragments, if a sequence table size does not exceed a maximum sequence table size; and

storing a header for each data fragment and the sequence table, wherein the header is located in a same block as its associated data fragment and sequence table, wherein within a given block the headers are stored contiguously proceeding from a first end to a second end of the given block, wherein objects identified by the headers are stored contiguously proceeding from the second end to a first end of the given block.

13. The method of claim 11, wherein storing the data further includes:

storing the data fragments using sequence table fragments and a group table, if a sequence table size exceeds the maximum sequence table size, wherein the sequence table fragments are indicative of an order and a location of the data fragments, wherein the group table is indicative of an order and a location of the sequence table fragments; and

storing a header for each data fragment, sequence table fragment, and group table, wherein the header is located in a same block as its associated data fragment, sequence table fragment, and group table, wherein within a given block the headers are stored contiguously proceeding from a first end to a second end of the given block, wherein objects identified by the headers are stored contiguously proceeding from the second end to a first end of the given block.

14. A machine-readable medium having executable code to cause a machine to perform a method, the method comprising:

receiving data for storage in a nonvolatile memory comprising a plurality of blocks;

selecting a storage structure for the data according to a size (z) of the data, a minimum number of instances (m), a maximum single instance size (s*g), and an allocation granularity (g); and

storing the data in the selected structure within the nonvolatile memory, each of the plurality of blocks including at least one selected structures and each of the structure storing an instance of the data and the status for the respective instance within the same respective block.

15. A machine-readable medium having executable code to cause a machine to perform a method, the method comprising:

receiving data for storage in a nonvolatile memory comprising a plurality of blocks;

selecting a storage structure for the data according to a size (z) of the data, a minimum number of instances (m), a maximum single instance size (s*g), and an allocation granularity (g); and

storing the data in the selected structure within the nonvolatile memory, each of the plurality of blocks including at least one selected structures and each of the structure storing an instance of the data and the status for the respective instance within the same block.