Flash management system using only sequential write

• US 6,678,785 B2
• Filed: 09/28/2001
• Issued: 01/13/2004
• Est. Priority Date: 09/28/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): MOAZZAMI, NASSER G
• Application Number:
  US09/964,606
• Publication Number:
  US 20030065876A1
• Time in Patent Office: 837 Days
• Field of Search: 711/103, 711/202-203, 711/205-206, 707/100, 714/805, 365/185.29, 365/185.23
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G11C 16/10 Programming or data input circuits

Abstract

A system and method for managing flash devices that are limited to performing only sequential write operations. After a write request has been received, a physical portion of the flash device is located for writing the data, according to the location of a previously written physical portion which was the last such portion to be written in the same block, such that the physical portion is physically at a higher address within the block than the previously written physical portion. In other words, the write operation is performed in a place that does not violate the sequential write limitation, rather than being performed at a randomly chosen location. This portion is preferably a location in a block, such as a page for example, such that if a page is available for writing in the same block, the data is written to that page. Again, this page is preferably at a higher address than any previously written page in that block.

Claims

1. A system comprising:

(a) a flash memory system comprising at least one flash device, said flash device featuring memory comprising a plurality of blocks, each block comprising a plurality of pages;

(b) a flash management system for managing page write requests from outside of said flash memory system and said flash management system regardless of an order in which said page write requests are received; and

(c) a module for converting said order of receiving said page write requests into a writing order, such that data in said page write requests alone with associated control data are written as physically sequential pages within each block, regardless of said order of receiving said page write requests, and such that, in fulfilling each said page write request, copying previously written pages to a new location is optional.

2. The system of claim 1, wherein said flash management system contains a plurality of virtual addresses and wherein said flash device contains a plurality of physical addresses, such that said flash management system maps said virtual addresses to said physical addresses by mapping each virtual block into one or more physical blocks.

3. The system of claim 2, wherein each page write request is to a virtual address and wherein said flash management system maps virtual address to a physical address, such that within each block, pages are written to a next higher physical address for each subsequent page write operation.

4. The system of claim 3, wherein said control data that is written to each physically written page includes a corresponding virtual page number within a corresponding virtual block.

5. The system of claim 4, wherein said virtual page number identifies most recently written data corresponding to a requested virtual page when reading data from the flash memory system.

6. The system of claim 5, wherein if a plurality of physical pages are associated with an identical virtual page number, said physical page corresponding to said requested virtual page is said physical page to which data has been most recently written.

7. The system of claim 3, wherein a physical block corresponds to a virtual block and said physical block does not have a free page, such that if a write request is received for said virtual block, a new physical block is allocated for said virtual block and data from said write request is written into a first page of said new physical block.

8. The system of claim 7, wherein at a certain time, a group of physical blocks corresponding to a virtual block is compacted by copying at least a portion of data corresponding to virtual pages of said virtual block to a single block if necessary, thereby freeing at least one physical block.

9. The system of claim 8, wherein said single block is a newly allocated block or a most recently allocated block of said virtual block.

10. The system of claim 9, wherein said blocks are compacted when a new physical block is required by said flash management system and a number of free blocks is below a preset number.

11. The system of claim 9, wherein said blocks are compacted when a size of said group of physical blocks corresponding to said virtual block would become larger than a preset number if not compacted.

12. The system of claim 11, wherein said preset number is one, such that said virtual blocks are mapped one-to-one to said physical blocks.

13. The system of claim 1, wherein said flash management system contains a plurality of virtual addresses and wherein said flash device contains a plurality of physical addresses, such that said flash management system maps said virtual addresses to said physical addresses by mapping each virtual page into one or more physical pages.

14. The system of claim 13, wherein each page write request is to a virtual address and wherein said flash management system maps virtual address to a physical address, such that pages are written to a next higher physical address for each subsequent page write operation within at least a portion of said flash device.

15. The system of claim 14, wherein each physically written page is accompanied by a corresponding virtual page number.

16. The system of claim 15 wherein said virtual page number identifies most recently written data corresponding to a requested virtual page when reading data from the flash memory system.

17. The system of claim 16, wherein if a plurality of physical pages are associated with an identical virtual page number, said physical page corresponding to said requested virtual page is said physical page to which data has been most recently written.

18. The system of claim 14, wherein if at least a portion of said flash device does not have a free page to write, and another write request is received for said portion, an additional portion of said flash device is allocated for increasing a size of said portion, and data from said write request is written into a first page of said additional portion.

19. The system of claim 18, wherein at a certain time, said portion of said flash device is compacted by copying data corresponding to at least one virtual page into a new location if necessary, thereby freeing at least one physical page.

20. The system of claim 19, wherein said portion of said flash device is compacted when a new physical page is required by said flash management system and a number of free pages is below a preset number.

21. The system of claim 19, wherein said portion of said flash device is compacted when a size of said portion would become larger than a preset number if not compacted.

22. A method for performing write operations to a flash device which allows only sequential write operations within a block, regardless of an order of receiving write requests for performing said write operations, the method comprising:

receiving a write request from outside the flash device to write data of a predetermined fixed length to a portion of the flash device, said portion containing a plurality of addresses;

locating an address in said portion to write said data from said write request and associated control data according to a previously written address within said portion, such that said address is physically sequential to said previously written address; and

writing said data from said write request and said control data to said portion.

23. The method of claim 22, wherein said previously written address is at a previously written page in a block, Such that if an additional page is available in said block, said data from said write request is written to said additional page, wherein said additional page is at a higher physical address to said previously written page.

24. The method of claim 23, wherein a plurality of write requests is received and wherein said page is located in said block for each write request such that said data from said each write request is written for said each write request to a page at a higher physical address.

25. The method of claim 24, wherein each physical address corresponds to a physical page in a physical block, and wherein said write request is to write data to at least one of a plurality of virtual addresses, each virtual address corresponding to a virtual page in a virtual block, wherein said virtual addresses are mapped to said physical addresses.

26. The method of claim 25, wherein said virtual addresses are mapped to said physical addresses by mapping each virtual block into at least one physical block.

27. The method of claim 26, wherein said plurality of write requests for a plurality of virtual addresses is received in a random order, and wherein data for plurality of write requests is written sequentially by writing each newly written page into a first free physical page of a physical block into which said virtual address to be written is mapped.

28. The method of claim 27, wherein said control data that is written to each physically written page includes a corresponding virtual page number within said virtual block of said virtual page.

29. The method of claim 28, wherein said virtual page number identifies most recently written data corresponding to a requested virtual page for reading data from the flash device.

30. The method of claim 29, wherein if a physical of physical pages have an identical virtual page number, said physical page to be read is said physical page containing the most recently written data.

31. The method of claim 27, wherein if a physical block does not have an available physical page for writing, and a write request is received for a virtual block corresponding to said physical block, a new physical block is allocated for said virtual block and data from said write request is written into a first physical page of said new physical block.

32. The method of claim 31, further comprising:

copying at least one physical page into a new physical location if necessary to free at least one physical block.

33. The method of claim 32, wherein said new physical location is in a newly allocated physical block or a most recently allocated block of said virtual block.

34. The method of claim 32, wherein said at least one physical page is copied when a new physical block is required and a number of free physical blocks is below some preset number.

35. The method of claim 32, wherein said at least one physical page is copied when a size of the group of physical blocks corresponding to a virtual block would become larger than a preset number if not compacted.

36. The method of claim 35, wherein said preset number is one, such that said group of physical blocks contains only one block, such that said virtual blocks map to said physical blocks according to one-la-one mapping.

37. The method of claim 25, wherein said virtual addresses are mapped to said physical addresses by mapping each virtual page into one or more physical pages.

38. The method of claim 37, wherein said plurality of write requests for a plurality of virtual addresses is received in a random order, and wherein data for said plurality of write requests is written sequentially by writing each newly written page into a next free physical page within at least a portion of said physical addresses, regardless of a virtual address to be written.

39. The method of claim 38, wherein said at least a portion of said physical addresses includes at least two non-contiguous physical addresses.

40. The method of claim 38, in which each physically written page is accompanied by a corresponding virtual page number.

41. The method of claim 40, wherein said virtual page number identifies most recently written data corresponding to a requested virtual page.

42. The method of claim 41, wherein if two physical pages have an identical virtual page number, said physical page corresponding to said requested virtual page is said physical page to which data has been most recently written.

43. The method of claim 38, wherein said at least a portion of said physical addresses does not have an available page for writing data from a write request, such that a new portion is allocated for being added to said portion, wherein said data is written to a first page of said new portion.

44. The method of claim 43, further comprising:

copying at least one physical page into a new physical location if necessary to free at least one physical page.

45. The method of claim 44, wherein said new physical location is in a newly allocated physical block or in a block already contained in said portion.

46. The method of claim 45, wherein said at least one physical page is copied when a new physical page is required and a number of free physical pages is below some preset number.

47. The method of claim 45, wherein said at least one physical page is copied when a size of said portion would become larger than a preset number if not compacted.

48. The method of claim 22, wherein data from at least one write request is written without copying previously written data in order to maintain a sequential order of said physical locations of written data.

49. The method of claim 22, wherein, in said writing of said data from said write request and said control data to said portion, copying previously written pages to a new location is optional.

51. The method of claim 22, wherein, in said writing of said data from said write request to said portion, no previously written pages are copied to a new location.

50. A system comprising:

(a) a flash memory system comprising at least one flash device, said flash device featuring memory comprising a plurality of blocks, each block comprising a plurality of pages;

(b) a flash management system for managing page write requests from outside of said flash memory system and said flash management system regardless of an order in which said page write requests are received; and

(c) a module for converting said order of receiving said page write requests into a writing order, such that data in said page write requests along with associated control data are written as physically sequential pages within each block, regardless of said order of receiving said page write requests, and such that, in fulfilling each said page write request, previously written pages of a block are copied to a new location only if said block, in which said previously written pages are written, and in which said data in said each page write request would otherwise be written, lacks a page available for writing.

52. A method for performing write operations to a flash device which allows only sequential write operations within a block, regardless of an order of receiving write requests for performing said write operations, the method comprising:

receiving a write request from outside the flash device to write data of a predetermined fixed length to a portion of the flash device, said portion containing a plurality of addresses;

seeking an address in said portion to write said data from said write request and associated control data according to a previously written address within said portion, such that said address is physically sequential to said previously written address; and

if said address is found;

writing said data from said write request and said control data to said portion;

otherwise;

writing said data from said write request and said control data to a different portion of the flash device.

53. The method of claim 52, wherein previously written pages are copied to a new location only if said data from said write request and said control data are written to said different portion of the flash device.