Device and method for managing a flash memory

• US 8,819,385 B2
• Filed: 07/27/2009
• Issued: 08/26/2014
• Est. Priority Date: 04/06/2009
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: DensBits Technologies Ltd. (Broadcom, Inc.)
• Inventors: Barsky, Boris, Segal, Avigdor, Maly, Igal
• Primary Examiner(s): Bansal, Gurtej
• Application Number:
  US12/509,749
• Publication Number:
  US 20100257309A1
• Time in Patent Office: 1,856 Days
• Field of Search: 711/202, 711/206
• US Class Current: 711/202
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7207 management of metadata or control data

Abstract

A method for accessing a flash memory, the method includes: receiving a read request that is associated with a logical address that is mapped to a physical address of a set of flash memory cells; accessing multiple mapping data structures of different granularity to obtain the physical address of the set of flash memory cells; wherein during at least one point in time at least one mapping data structure is stored in an erase block and wherein the erase block comprises multiple physical pages that are written in a sequential manner and are associated with logical page addresses that are assigned in a random manner; and reading a content of the set of flash memory cells.

Claims

1. A method for accessing a flash memory, the method comprises:

receiving a read request that is associated with a logical address that is mapped to a physical address of a set of flash memory cells;

accessing multiple mapping data structures of different granularity to obtain the physical address of the set of flash memory cells;

wherein the accessing comprises accessing a first mapping data structure that maps logical erase block addresses to physical erase block addresses and accessing a second mapping data structure that comprises mapping information relating to multiple physical or logical pages;

wherein the flash memory comprises multiple erase blocks, each erase block comprises multiple physical pages that are written in a sequential manner and are associated with logical page addresses that are assigned in a random manner;

reading a content of the set of flash memory cells;

writing to an erase block of the flash memory the second mapping data structure only after all the multiple physical pages of the erase block were written to the erase block;

accessing the first mapping data structure, the second mapping data structure and a third mapping data structure;

wherein the second mapping data structure maps logical page addresses to indexes into the third mapping data structure;

wherein the third mapping data structure maps the indexes to locations of sets of flash memory cells to overcome misalignments between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory; and

wherein at least one erasure block comprises at least two sets of flash memory cells that differ from each other by their size but store representations of information units of the same size.

2. The method according to claim 1 wherein a mapping data structure of a certain granularity stores only information associated with the certain granularity.

3. The method according to claim 1, wherein the second mapping data structure stores mapping information relating to all of the multiple physical pages of the erase block.

4. The method according to claim 1, wherein the set of the flash memory cells is a single flash memory cell.

5. The method according to claim 1 wherein evenly sized logical pages are stored in evenly sized physical pages.

6. The method according to claim 1 wherein during at least one period the first mapping data structure is stored in memory unit that differs from the flash memory;

and wherein the second mapping data structure maps logical inter erase block addresses to physical inter erase block addresses.

7. The method according to claim 1 wherein the at least two sets of memory cells store information that is encoded by a variable encoding process resulting in the misalignment between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory.

8. The method according to claim 1 comprising storing the third mapping data structure in an erase block that further stores the second mapping data structure.

9. The method according to claim 1 comprising receiving a write request to write content, wherein the write request is associated with a logical address;

writing the write content to a new set of flash memory cells that follow a last set of flash memory cells that were written to; and

updating at least one mapping data structure to reflect the writing to the new set of flash memory cells.

10. The method according to claim 9 comprising invalidating all entries except a last entry of a group of entries of a mapping data structure that are associated with the same logic address.

11. A system having flash memory management capabilities, the system comprises a management module that is coupled to a flash memory, another memory unit, and an interface;

wherein the interface receives a read request that is associated with a logical address that is mapped to a physical address of a set of flash memory cells;

wherein the flash memory comprises multiple erase blocks;

wherein the management module is adapted to;

access multiple mapping data structures of different granularity to obtain the physical address of the set of flash memory cells;

wherein the multiple mapping data structures comprise a first mapping data structure that maps logical erase block addresses to physical erase block addresses and a second mapping data structure that comprises mapping information relating to multiple physical or logical pages;

wherein the erase block comprises multiple physical pages that are written in a sequential manner and are associated with logical page addresses that are assigned in a random manner;

access the set of flash memory cells; and

write to an erase block of the flash memory the second mapping data structure only after all the multiple physical pages of the erase block were written to the erase block;

wherein the management module accesses the first mapping data structure, the second mapping data structure and a third mapping data structure;

wherein the second mapping data structure maps logical page addresses to indexes into the third mapping data structure to overcome misalignments between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory;

wherein the third data structure maps the indexes to locations of sets of flash memory cells;

wherein at least one erasure block comprises two sets of flash memory cells that differ from each other by their size but store representations of information units of the same size.

12. The system according to claim 11 wherein a mapping data structure of a certain granularity store only information associated with the certain granularity.

13. The system according to claim 11, wherein the second mapping data structure stores mapping information relating to all of the multiple physical pages of the erase block.

14. The system according to claim 11, wherein the flash memory cells are eight bit per cell flash memory cells.

15. The system according to claim 11 wherein evenly sized logical pages are stored in evenly sized physical pages.

16. The system according to claim 11 wherein during at least one period the first mapping data structure is stored in memory unit that differs from the flash memory and wherein the second mapping data structure maps logical inter erase block addresses to physical inter erase block addresses.

17. The system according to claim 11 wherein the at least two sets of memory cells store information that is encoded by a variable encoding process resulting in the misalignment between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory.

18. The system according to claim 11 wherein the management module is arranged to store the third mapping data structure in an erase block that further stores the second mapping data structure.

19. The system according to claim 11 wherein the interface is adapted to receive a write request to write content, wherein the write request is associated with a logical address;

wherein the management module writes the write content to a new set of flash memory cells that follow a last set of flash memory cells that were written to; and

to update at least one mapping data structure to reflect the writing to the new set of flash memory cells.

20. The system according to claim 19 wherein the management module invalidates all entries except a last entry of a group of entries of a mapping data structure that are associated with the same logic address.

21. A system having flash memory management capabilities, the system comprises a management module that is coupled to a flash memory, another memory unit, and an interface;

wherein the interface receives a write request to write content, wherein the write request is associated with a logical address;

wherein the logical address comprises a logical erase block address and a logical inter erase block address;

wherein the flash memory comprises multiple erase blocks;

wherein the management module is adapted to;

write the write content to a new set of flash memory cells that follow a last set of flash memory cells that were written to; and

update at least one mapping data structure out of multiple mapping data structures to reflect the writing to the new set of flash memory cells;

wherein the multiple mapping data structures are of different granularity;

wherein the multiple mapping data structures comprise a first mapping data structure that maps logical erase block addresses to physical erase block addresses and a second mapping data structure that maps inter erase block addresses to physical inter erase block addresses of an entire erase block; and

write to an erase block of the flash memory the second mapping data only after all the multiple physical pages of the erase block were written to the erase block;

wherein the erase block comprises multiple physical pages that are written in a sequential manner and are associated with logical page addresses that are assigned in a random manner;

wherein the management module accesses the first mapping data structure, the second mapping data structure and a third mapping data structure;

wherein the second mapping data structure maps logical page addresses to indexes into the third mapping data structure to overcome misalignments between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory;

wherein the third data structure maps the indexes to locations of sets of flash memory cells;

wherein at least one erasure block comprises two sets of flash memory cells that differ from each other by their size but store representations of information units of the same size.

22. A method for writing to a flash memory, the method comprises:

receiving a write request to write content, wherein the write request is associated with a logical address;

writing the write content to a new set of flash memory cells that follow a last set of flash memory cells that were written to;

updating at least one mapping data structure out of multiple mapping data structures to reflect the writing to the new set of flash memory cells;

wherein the multiple mapping data structures are of different granularity;

wherein the multiple mapping data structures comprise a first mapping data structure that maps logical erase block addresses to physical erase block addresses and a second mapping data structure that comprises mapping information relating to multiple physical or logical pages;

writing to an erase block of the flash memory the second mapping data structure only after all the multiple physical pages of the erase block were written to the erase block;

wherein the erase block comprises multiple physical pages that are written in a sequential manner and are associated with logical page addresses that are assigned in a random manner; and

accessing the first mapping data structure, the second mapping data structure and a third mapping data structure;

wherein the second mapping data structure maps logical page addresses to indexes into the third mapping data structure;

wherein the third mapping data structure maps the indexes to locations of sets of flash memory cells to overcome misalignments between information unit representations stored in the physical pages of the flash memory and physical page boundaries of the flash memory;

wherein at least one erasure block comprises at least two sets of flash memory cells that differ from each other by their size but store representations of information units of the same size.