Methods, systems and computer readable medium for writing and reading data

• US 8,838,937 B1
• Filed: 05/23/2012
• Issued: 09/16/2014
• Est. Priority Date: 05/23/2012
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Katz, Michael, Weingarten, Hanan
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): Dersarkissian, Daniel A
• Application Number:
  US13/478,706
• Time in Patent Office: 846 Days
• Field of Search: 711/103
• US Class Current: 711/216
• 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/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks

Abstract

A flash memory controller, a computer readable medium and a method for writing to a flash memory device, the method may include receiving multiple logical pages, each logical page having a logical address; determining to write a logical page into a selected physical page of the flash memory device; calculating a hash value for each logical page of the multiple logical pages in response to (a) a logical address of the logical page and (b) a physical page index, to provide multiple hash values of the multiple logical pages.

Claims

1. A method for writing to a flash memory device, the method comprising:

receiving multiple logical pages, each logical page having a logical address;

determining to write a logical page into a selected physical page of the flash memory device, the selected physical page has a selected physical page address that is represented by a physical page index, a set index and a block index;

the physical page index being indicative of an order of the selected physical page within a selected set of physical pages, the selected set of physical pages is being identified by the set index, the block index is indicative of a block of the flash memory device that comprises the selected set of physical pages;

calculating a hash value for each logical page of the multiple logical pages in response to (a) a logical address of the logical page and (b) the physical page index, to provide multiple hash values of the multiple logical pages;

searching for a matching logical page that is associated with a hash value that matches the set index;

writing the matching logical page to the selected physical page and updating a first data structure to be indicative of a mapping between a logical address of the matching logical page and the selected physical address; and

writing a mismatch logical page to the selected physical page, updating the first data structure and the second data structure to be indicative of a mapping between a logical address of the mismatch logical page and the selected physical address, if neither one of the multiple logical pages is associated with a hash value that matches the set index.

2. The method according to claim 1, wherein the updating of the first data structure and the second data structure comprises writing the physical page index of the selected physical page to the first data structure and writing the set index to the second data structure.

3. The method according to claim 1, comprising selecting a matching logical page out of a plurality of matching logical pages.

4. The method according to claim 3, comprising selecting the matching logical page in response to an age of each of the plurality of matching logical pages.

5. The method according to claim 1, comprising electing the mismatch logical page based upon a distribution of hash values of the multiple logical pages.

6. The method according to claim 5, comprising selecting the mismatch logical page out of a largest group of logical pages that share a same hash value.

7. The method according to claim 1, wherein the selected set of physical pages comprises a consecutive sequence of physical pages.

8. The method according to claim 1, wherein the selected set of physical pages comprises non-consecutive physical pages that are located at a same relative position in sub-blocks of the selected block.

9. The method according to claim 1, comprising storing the multiple logical pages in a buffer before writing to the selected physical page.

10. The method according to claim 9, wherein the multiple logical pages fill the buffer.

11. The method according to claim 9, wherein the multiple logical pages partially fill the buffer.

12. The method according to claim 1, comprising:

receiving a request to read a requested logical page from the flash memory device, the requested logical page has a requested logical address;

searching the second data structure for a logical address of a mismatch logical page that equals the requested logical address;

retrieving the requested logical page based upon the first and second data structures if it is determined that the second data structure comprises a logical address of a mismatch logical page that equals the requested logical address; and

retrieving the requested logical page based upon the first data structures and not upon the second data structure if it is determined that the second data structure does not comprise a logical address of a mismatch logical page that equals the requested logical address.

13. The method according to claim 12, comprising calculating a physical address of a physical page that stores the requested logical page based upon (a) the requested logical address, (b) a set index that is stored in the second data structure and is associated with the requested logical address, and (c) a physical page index stored in the first data structure and is associated with the requested logical page address, if it is determined that the second data structure comprises the logical address of the mismatch logical page that equals the requested logical address.

14. The method according to claim 12, comprising calculating a physical address of a physical page that stores the requested logical page based upon (a) the requested logical address, and (b) a physical page index stored in the first data structure and is associated with the requested logical address, if it is determined that the second data structure does not comprise a logical address of a mismatch logical page that equals the requested logical address.

15. A non-transitory computer readable medium that stores instructions comprising:

receiving multiple logical pages, each logical page having a logical address;

determining to write a logical page into a selected physical page of the flash memory device, the selected physical page has a selected physical page address that is represented by a physical page index, a set index and a block index;

the physical page index being indicative of an order of the selected physical page within a selected set of physical pages, the selected set of physical pages is being identified by the set index, the block index is indicative of a block of the flash memory device that comprises the selected set of physical pages;

calculating a hash value for each logical page of the multiple logical pages in response to (a) a logical address of the logical page and (b) the physical page index, to provide multiple hash values of the multiple logical pages;

searching for a matching logical page that is associated with a hash value that matches the set index;

writing the matching logical page to the selected physical page and updating a first data structure to be indicative of a mapping between a logical address of the matching logical page and the selected physical address; and

writing a mismatch logical page to the selected physical page, updating the first data structure and the second data structure to be indicative of a mapping between a logical address of the mismatch logical page and the selected physical address—

if neither one of the multiple logical pages is associated with a hash value that matches the set index.

16. The non-transitory computer readable medium according to claim 15, wherein the updating of the first data structure and the second data structure comprises writing the physical page index of the selected physical page to the first data structure and writing the set index to the second data structure.

17. The non-transitory computer readable medium according to claim 15 that stores instructions for selecting a matching logical page out of a plurality of matching logical pages.

18. The non-transitory computer readable medium according to claim 17 that stores instructions for comprising selecting the matching logical page in response to an age of each of the plurality of matching logical pages.

19. The non-transitory computer readable medium according to claim 15 that stores instructions for electing the mismatch logical page based upon a distribution of hash values of the multiple logical pages.

20. The non-transitory computer readable medium according to claim 19 that stores instructions for selecting the mismatch logical page out of a largest group of logical pages that share a same hash value.

21. The non-transitory computer readable medium according to claim 15, wherein the selected set of physical pages comprises a consecutive sequence of physical pages.

22. The non-transitory computer readable medium according to claim 15, wherein the selected set of physical pages comprises non-consecutive physical pages that are located at a same relative position in sub-blocks of the selected block.

23. The non-transitory computer readable medium according to claim 15 that stores instructions for storing the multiple logical pages in a buffer before writing to the selected physical page.

24. The non-transitory computer readable medium according to claim 23, wherein the multiple logical pages fill the buffer.

25. The non-transitory computer readable medium according to claim 23 wherein the multiple logical pages partially fill the buffer.

26. The non-transitory computer readable medium according to claim 15, that stores instructions comprising:

receiving a request to read a requested logical page from the flash memory device, the requested logical page has a requested logical address;

searching the second data structure for a logical address of a mismatch logical page that equals the requested logical address;

retrieving the requested logical page based upon the first and second data structures if it is determined that the second data structure comprises a logical address of a mismatch logical page that equals the requested logical address; and

retrieving the requested logical page based upon the first data structures and not upon the second data structure if it is determined that the second data structure does not comprise a logical address of a mismatch logical page that equals the requested logical address.

27. The non-transitory computer readable medium according to claim 26 that stores instructions for calculating a physical address of a physical page that stores the requested logical page based upon (a) the requested logical address, (b) a set index that is stored in the second data structure and is associated with the requested logical address, and (c) a physical page index stored in the first data structure and is associated with the requested logical page address, if it is determined that the second data structure comprises the logical address of the mismatch logical page that equals the requested logical address.

28. The non-transitory computer readable medium according to claim 26, that stores instructions for calculating a physical address of a physical page that stores the requested logical page based upon (a) the requested logical address, and (b) a physical page index stored in the first data structure and is associated with the requested logical address, if it is determined that the second data structure does not comprise a logical address of a mismatch logical page that equals the requested logical address.

29. A flash memory controller, comprising:

a buffer arranged to receive and store multiple logical pages, each logical page having a logical address;

a write circuit arranged to determine to write a logical page into a selected physical page of a flash memory device that is coupled to the flash memory controller, the selected physical page has a selected physical page address that is represented by a physical page index, a set index and a block index;

the physical page index being indicative of an order of the selected physical page within a selected set of physical pages, the selected set of physical pages is being identified by the set index, the block index is indicative of a block of the flash memory device that comprises the selected set of physical pages;

a hash circuit arranged to calculate a hash value for each logical page of the multiple logical pages in response to (a) a logical address of the logical page and (b) the physical page index, to provide multiple hash values of the multiple logical pages;

a search circuit arranged to search for a matching logical page that is associated with a hash value that matches the set index;

wherein the write circuit is arranged to

write the matching logical page to the selected physical page and updating a first data structure to be indicative of a mapping between a logical address of the matching logical page and the selected physical address; and

write a mismatch logical page to the selected physical page, updating the first data structure and the second data structure to be indicative of a mapping between a logical address of the mismatch logical page and the selected physical address—

if neither one of the multiple logical pages is associated with a hash value that matches the set index.