System and method for flexible flash file

• US 6,591,330 B2
• Filed: 06/18/2001
• Issued: 07/08/2003
• Est. Priority Date: 06/18/2001
• Status: Expired due to Term

• Current Assignee: Western Digital Israel Limited (Western Digital Corporation)
• Original Assignee: M-Systems Flash Disk Pioneers Ltd. (Western Digital Corporation)
• Inventors: Lasser, Menahem
• Primary Examiner(s): Gossage; Glenn
• Application Number:
  US09/882,056
• Publication Number:
  US 20020194438A1
• Time in Patent Office: 750 Days
• Field of Search: 711/103,5,202,203 365/185.11,185.29,185.33
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A system and method for more flexibly managing flash memory devices, such that these devices can be more efficiently used to store data as flash disks. The present invention provides an improvement by enabling erase units of different sizes to be erased. Preferably, the present invention is also operative with flash memory devices which are capable of erasing the memory in a plurality of different erase unit sizes, and more preferably, is able to select the most efficient erase unit size for erasing. The present invention is able to optionally and more preferably use a plurality of different decision rules in order to select the most efficient method for erasing and/or reading/writing data to the flash memory device. Most preferably, the present invention is able to detect the capabilities of the flash memory device, in order to be automatically operative with a plurality of different types of flash memory technologies.

Claims

1. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, the memory having a plurality of memory portions for reading or writing data, each of the plurality of memory portions for reading or writing data having a size, the method comprising:

providing a size of a memory portion of the memory for being erasable in one operation, wherein said size of the memory portion for erasing is selectable from a group of sizes which contains at least one size equal to the size of the memory portion for reading or writing data and which also contains at least one size being different from the size of the memory portion for reading or writing data;

providing a plurality of physical units of the memory, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the size of the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit, wherein a size of said physical unit is either equal in size to one of said selectable erase sizes but not to the size of the memory portion for reading or writing, or alternatively is equal to an integral multiple of one of said selectable erase sizes,

providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within said virtual unit;

mapping each virtual unit to at least one physical unit to form a virtual map; and

mapping each virtual block within said virtual unit to one physical block within said at least one physical unit.

2. The method of claim 1, further comprising:

receiving a write command to write data at a virtual block;

locating a virtual unit containing said virtual block;

locating an unwritten block within a physical unit mapped to said virtual unit; and

writing said data to said unwritten physical block.

3. The method of claim 2, further comprising the steps of:

if an unwritten physical block within a physical unit mapped to said virtual unit cannot be located for mapping said virtual block to said physical block, selecting one of the following two procedures;

a first procedure, comprising;

locating an unwritten additional physical unit;

writing said data to an unwritten physical block of said additional unwritten physical unit; and

updating said virtual map by additionally mapping said virtual unit to said additional unwritten physical unit, such that said virtual unit corresponds to said additional unwritten physical unit and to said at least one written physical unit, said additional unwritten physical unit and said at least one written physical unit forming a chain of physical units; and

a second procedure, comprising;

locating a written physical block within a physical unit mapped to said virtual unit with said virtual block being mapped to said physical block;

erasing said physical block; and

writing said data to said physical block.

4. The method of claim 3, wherein said first procedure is always selected.

5. The method of claim 3, wherein said second procedure is always selected.

6. The method of claim 3, wherein said selection is dependent on whether said additional unwritten physical unit is locatable when selecting said first procedure.

7. The method of claim 3, wherein said selection is dependent on a number of said virtual blocks within the same said virtual unit for being written substantially simultaneously.

8. The method of claim 3, wherein said selection is dependent on at least one of a time required to erase a physical block and a time required to erase a physical unit.

9. The method of claim 3, wherein said selection is dependent on said data to be written.

10. The method of claim 3, wherein said selection is dependent on a physical unit number in which said physical block resides.

11. The method of claim 3, wherein said selection is dependent on a virtual unit number in which said virtual block resides.

12. The method of claim 3, wherein said selection is dependent on a random value.

13. The method of claim 3, wherein each of said first and second procedures is selected a fixed percentage of total selections.

14. The method of claim 3, further comprising:

allocating a counter associated with each physical block, to count a number of times said physical block is erased; and

if said second procedure is selected, incrementing said counter associated with said physical block to be written.

15. The method of claim 13, wherein said selection is dependent on said counter associated with said physical block.

16. The method of claim 1, wherein said physical block within said at least one physical unit has a physical block offset, and said physical block offset is always equal to said virtual block offset of said mapped virtual block.

17. The method of claim 1, wherein said physical block within said at least one physical unit has a physical block offset, and said physical block offset may be different than said virtual block offset of said mapped virtual block.

18. The method of claim 3, further comprising the steps of:

if said first procedure is selected and if an unwritten additional physical unit cannot be located, locating a second virtual unit corresponding to a plurality of physical units in a chain;

locating last physical unit in said chain;

moving data from each written physical block of each of said physical units of said chain, with the exception of said last physical unit, to a writable physical block of said last physical unit;

updating said virtual map by mapping said virtual unit to said last physical unit, such that said virtual unit corresponds only to said last physical unit; and

erasing all of said written physical units in said chain, with the exception of said last physical unit.

19. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion that can be erased in one operation differs from the size of the memory portion for reading or writing data, the method comprising:

providing a plurality of physical units of the memory, each of said physical units having a size equal to an integral multiple of the smallest memory portion for erasing, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the size of the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit;

providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within said virtual unit;

mapping each virtual unit to at least one physical unit to form a virtual map; and

mapping each virtual block within said virtual unit to one physical block within said at least one physical unit according to said virtual map.

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

receiving a write command to write data at a virtual block;

locating a virtual unit containing said virtual block;

locating an unwritten block within a physical unit mapped to said virtual unit; and

writing said data to said unwritten physical block.

21. The method of claim 20, further comprising the steps of:

if an unwritten physical block within a physical unit mapped to said virtual unit cannot be located in a way that will result in said virtual block being mapped to said physical block, locating an unwritten additional physical unit;

writing said data to an unwritten physical block of said additional unwritten physical unit; and

updating said virtual map by additionally mapping said virtual unit to said additional unwritten physical unit, such that said virtual unit corresponds to said additional unwritten physical unit and to said at least one written physical unit, said additional unwritten physical unit and said at least one written physical unit forming a chain of physical units.

22. The method of claim 19, wherein said physical block within said at least one physical unit has a physical block offset, and said physical block offset is always equal to said virtual block offset of said mapped virtual block.

23. The method of claim 19, wherein said physical block within said at least one physical unit has a physical block offset, and said physical block offset may be different than said virtual block offset of said mapped virtual block.

24. The method of claim 21, further comprising the steps of:

if an unwritten additional physical unit cannot be located, locating a second virtual unit corresponding to a plurality of physical units in a chain;

locating last physical unit in said chain;

moving data from each written physical block of each of said physical units of said chain, with the exception of said last physical unit, to a writable physical block of said last physical unit;

updating said virtual map by mapping said virtual unit to said last physical unit, such that said virtual unit corresponds only to said last physical unit; and

erasing all of said written physical units in said chain, with the exception of said last physical unit.

25. A memory organization method for a memory in which data can only be written to an unwritten portion of the memory, such that a written portion of the memory must be erased to become unwritten, and in which the size of the memory portion that can be erased in one operation is selectable from a group of sizes which contains at least one size equal to the size of the memory portion for reading or writing data and which also contains at least one size larger than the size of the memory portion for reading or writing data, the method comprising the steps of:

providing a plurality of physical units of the memory, each of said physical units being either equal in size to one of said selectable erase sizes but not to the size of the memory portion for reading or writing or equal to an integral multiple of any of said selectable erase sizes, each of said physical units being designated by a physical unit number and each of said physical units being divided into a plurality of physical blocks, each of said plurality of physical blocks being the size of the memory portion for reading or writing data and each of said physical blocks being designated by a physical block offset within said physical unit;

providing a plurality of virtual units of the memory, each virtual unit being designated by a virtual unit number and each of said virtual units featuring a plurality of virtual blocks being designated by a virtual block offset within said virtual unit;

mapping each virtual unit to at least one physical unit to form a virtual map; and

mapping each virtual block within said virtual unit to one physical block within said at least one physical unit.

26. A memory management method for a memory in which data can be written only in unwritten physical memory locations and in which a zone of contiguous memory locations can be simultaneously erased, comprising the steps of:

organizing the memory into a plurality of units;

organizing each unit into a plurality of blocks, each of said blocks made up of a plurality of contiguous physical memory locations;

establishing an allocation map for each unit which indicates the status of each block in said unit as written, unwritten or deleted;

establishing a virtual map to map virtual addresses to physical addresses;

in writing data to said memory at a virtual address;

mapping said virtual address to a physical address using said virtual map;

examining said allocation map for the physical unit into which said virtual address has been mapped to determine the status of the physical block into which said virtual address has been mapped as written, unwritten or deleted;

if said physical block is in written or deleted status, selecting one of the following two procedures;

a first procedure, comprising;

examining said allocation map for at least one of said units to identify an unwritten physical block;

writing said data into said memory to said unwritten physical block;

changing said allocation map for said unit into which said data have been written to indicate as written said previously unwritten block where said data have been written;

changing said virtual map so that said virtual map maps said virtual address to the physical address of said previously unwritten block in which said data have been written; and

a second procedure, comprising;

erasing said physical block into which said virtual address has been mapped;

writing said data into said physical block;

if said physical block was previously marked as deleted in said unit allocation map, changing said allocation map for said unit into which said data have been written to indicate as written said previously deleted block where said data have been written.

27. The method of claim 26, wherein said first procedure is always selected.

28. The method of claim 26, wherein said second procedure is always selected.

29. The method of claim 26, wherein said selection is dependent on whether said unwritten physical block is locatable when selecting said first procedure.

30. The method of claim 26, wherein one of said first and said second procedures is selected according to an amount of said data for being written substantially simultaneously within said physical unit into which said virtual address has been mapped.

31. The method of claim 26, wherein one of said first and said second procedures is selected according to at least one of an amount of time required for erasing a physical block and an amount of time required for erasing a physical unit.

32. The method of claim 26, wherein one of said first and said second procedures is selected according to said data to be written.

33. The method of claim 26, wherein one of said first and said second procedures is selected according to a physical unit number of the unit into which said virtual address has been mapped.

34. The method of claim 26, wherein one of said first and said second procedures is selected according to said virtual address.

35. The method of claim 26, wherein one of said first and said second procedures is selected according to a random value.

36. The method of claim 26, wherein each one of said first and said second procedures is selected a fixed percentage of total selections.

37. The method of claim 26, further comprising:

allocating a counter associated with each physical block, to count erasures of said physical block with a counter; and

when selecting said second procedure, incrementing said counter associated with said physical block being written.

38. The method of claim 37, wherein one of said first and said second procedures is selected according to said counter associated with said physical block into which said virtual address has been mapped.

39. The method of claim 26, further comprising:

establishing a transfer unit in said memory in which all blocks are in unwritten status, said transfer unit having an allocation map;

if said first procedure is selected and if an unwritten physical block cannot be located, locating a selected unit, other than said transfer unit, to be erased;

reading each written block in said selected unit;

writing each written block in said selected unit into said transfer unit;

updating said transfer unit allocation map to indicate a status of said written blocks as written;

erasing said selected unit; and

updating said virtual map to show said new locations of said written blocks.

40. The method of claim 26, further comprising:

establishing a transfer unit in said memory in which all blocks are in unwritten status, said transfer unit having an allocation map;

periodically locating a selected unit, other than said transfer unit, to be erased;

reading each written block in said selected unit;

writing each written block in said selected unit into said transfer unit;

updating said transfer unit allocation map to indicate a status of said written blocks as written;

erasing said selected unit; and

updating said virtual map to show said new locations of said written blocks.

41. The method of claim 26, further comprising:

in reading data from said memory at a virtual address;

mapping said virtual address to a physical address using said virtual map; and

reading said data from said memory at said physical address.