Granted Patent B1

US 8,996,790 · App. 13/434,083 · Granted Mar 31, 2015

Abstract

Claims (55)

1. A method of managing a flash memory device, the method comprises:

receiving multiple data sectors from an interface;

writing the multiple data sectors into a data buffer that is nonvolatile;

creating a pointer in a data management structure that is stored in a metadata buffer that is nonvolatile, for each data sector corresponding to a storage location of the data sector in the data buffer;

wherein the data management structure comprises a random mapping table and a metadata data structure;

wherein the random mapping table is partitioned to random mapping table mapping portions;

wherein each random mapping table portion comprises pointers to data sectors stored in the data buffer and a pointer to a previously written metadata data structure;

wherein the metadata data structure comprises pointers to multiple random mapping table portions; and a list of data blocks that are managed by the data management structure;

if a predefined condition is reached, merging data sectors stored in the data buffer with data sectors that are already stored in a sequential nonvolatile portion of the flash memory device, wherein the sequential nonvolatile portion differs from the data buffer and wherein the metadata buffer differs from the data buffer.

2. The method of claim 1 , wherein the predetermined condition is reached if a predefined number of new data sectors that should belong to a same erase unit are written.

3. The method of claim 1 , comprising merging (a) at least one data sector stored in the data buffer with (b) at least one data sector that is already stored in the sequential nonvolatile portion of the flash memory device and is associated with a same erase unit as the at least one data sector stored in the data buffer.

4. The method according to claim 3 , wherein the merging comprises generating a pointer for each erase unit of the sequential nonvolatile portion of the flash memory device.

5. The method of claim 1 , comprising writing the multiple data sectors into the data buffer if it is estimated that the multiple data sectors are written to the flash memory device in a random manner; and writing the multiple data sectors into the sequential nonvolatile portion of the flash memory device without writing the multiple data sectors to the data buffer if it is estimated that the multiple data sectors are written to the flash memory device in a sequential manner.

6. The method of claim 1 , further comprising compressing the data management structure before storing the data management structure in the metadata buffer.

7. The method of claim 1 , further comprising maintaining at least a portion of the data management structure in a volatile memory module of the flash memory device and retrieving the data management structure from the metadata buffer if a power failure condition occurs.

8. The method of claim 7 , comprising:

searching the data management structure stored in the metadata buffer for a most recent version of the metadata data structure;

reading from the metadata data structure pointers associated with most recent random mapping table portions;

if one of a plurality of the most recent portions of the random mapping table is found before the most recent version of the metadata data structure then reading from the most recent portion of the random mapping table a pointer to a certain metadata data structure;

if the certain metadata data structure is out of date then reconstructing the metadata data structure from the most recent portions of the random mapping table to comprise pointers contained in the random mapping table.

9. The method of claim 1 , wherein each random mapping table portion comprises a pointer to a previously written random mapping table portion.

10. A system for managing a flash memory device, the system comprises a memory controller that is arranged to: receive multiple data sectors from an interface; write the multiple data sectors into a data buffer that is nonvolatile; create a pointer in a data management structure that is stored in a metadata buffer that is nonvolatile, for each data sector corresponding to a storage location of the data sector in the data buffer; wherein the data management structure comprises a random mapping table and a metadata data structure; wherein the random mapping table is partitioned to random mapping table mapping portions; wherein each random mapping table portion comprises pointers to data sectors stored in the data buffer and a pointer to a previously written metadata data structure; wherein the metadata data structure comprises pointers to multiple random mapping table portions and a list of data blocks that are managed by the data management structure; if a predetermined condition is reached, merge data sectors stored in the data buffer with data sectors that are already stored in a sequential nonvolatile portion of the flash memory device, wherein the sequential nonvolatile portion differs from the data buffer and wherein the metadata buffer differs from the data buffer.

11. The system of claim 10 , wherein the memory controller is arranged to merge (a) at least one data sector stored in the data buffer with (b) at least one data sector that is already stored in the sequential nonvolatile portion of the flash memory device and is associated with a same erase unit as the at least one data sector stored in the data buffer.

12. The system of claim 10 , wherein the memory controller is arranged to write the multiple data sectors into the data buffer if it is estimated that the multiple data sectors are written to the flash memory device in a random manner; and write the multiple data sectors into the sequential nonvolatile portion of the flash memory device without writing the multiple data sectors to the data buffer if it is estimated that the multiple data sectors are written to the flash memory device in a sequential manner.

13. The system of claim 10 , wherein the memory controller is arranged to maintain at least a portion of the data management structure in a volatile memory module of the flash memory device and retrieve the data management structure from the metadata buffer if a power failure condition occurs.

14. The system of claim 13 , wherein the memory controller is arranged to read, if a power failure condition occurs, most recent pointers from the data management structure stored in the metadata by: searching the data management structure stored in the metadata buffer for a most recent version of the metadata data structure; reading from the metadata data structure pointers associated with most recent random mapping table portions; if one of a plurality of the most recent portions of the random mapping table is found before the most recent version of the metadata data structure then reading from the most recent portion of the random mapping table a pointer to a certain metadata data structure; if the certain metadata data structure is out of date then reconstructing the metadata data structure from the most recent portions of the random mapping table to comprise pointers contained in the random mapping table.

15. The system of claim 10 , wherein the memory controller is arranged to:

write a first pointer to a first portion of a random mapping table stored in the data management structure, said pointer contains the location of the data sector;

if the first portion of the random mapping table is preceded by another random mapping table portion, then writing a second pointer to the first portion of the random mapping table, said second pointer contains the location of the preceding portion of the random mapping table;

write a third pointer to a metadata data structure stored in the data management structure, said third pointer contains the location of the first portion of the random mapping table; and

write a fourth pointer in the first portion of the random mapping table, said fourth pointer contains the location of the latest version of the metadata data structure.

16. The system of claim 10 , wherein each random mapping table portion comprises a previously written random mapping table portion.

17. A computer readable medium that is not transitory and stores instructions for:

receiving multiple data sectors from an interface;

writing the multiple data sectors into a data buffer that is nonvolatile;

creating a pointer in a data management structure that is stored in a metadata buffer that is nonvolatile, for each data sector corresponding to a storage location of the data sector in the data buffer;

wherein the data management structure comprises a random mapping table and a metadata data structure;

wherein the random mapping table is partitioned to random mapping table mapping portions;

wherein each random mapping table portion comprises pointers to data sectors stored in the data buffer and a pointer to a previously written metadata data structure;

wherein the metadata data structure comprises pointers to multiple random mapping tale portions and a list of data blocks that are managed by the data management structure;

if a predetermined condition is reached, merging data sectors stored in the data buffer with data sectors that are already stored in a sequential nonvolatile portion of the flash memory device, wherein the sequential nonvolatile portion differs from the data buffer and wherein the metadata buffer differs from the data buffer.

18. The computer readable medium of claim 17 , wherein the predetermined condition is reached if the data management structure exceeds a predefined size limit.

19. The computer readable medium of claim 17 , storing instructions for merging (a) at least one data sector stored in the data buffer with (b) at least one data sector that is already stored in the sequential nonvolatile portion of the flash memory device and is associated with a same erase unit as the at least one data sector stored in the data buffer.

20. The computer readable medium of claim 17 , further storing instructions for compressing the data management structure before storing the data management structure in the metadata buffer.

21. The computer readable medium of claim 17 , further storing instructions for maintaining at least a portion of the data management structure in a volatile memory module of the flash memory device and retrieving the data management structure from the metadata buffer if a power failure condition occurs.

22. The computer readable medium of claim 21 , storing instructions for:

searching the data management structure stored in the metadata buffer for a most recent version of the metadata data structure; reading from the metadata data structure pointers associated with most recent random mapping table portions; if one of a plurality of the most recent portions of the random mapping table is found before the most recent version of the metadata data structure then reading from the most recent portion of the random mapping table a pointer to a certain metadata data structure; if the certain metadata data structure is out of date then

reconstructing the metadata data structure from the most recent portions of the random mapping table to comprise pointers contained in the random mapping table.

23. The computer readable medium of claim 17 , storing instructions for writing a first pointer to a first portion of a random mapping table of the data management structure;

if the first portion of the random mapping table is preceded by another portion of the random mapping table, then writing a second pointer to the first portion of the random mapping table, the second pointer points to a location of the other portion of the random mapping table;

writing a third pointer to a metadata data structure stored in the data management structure, the third pointer points to a location of the first portion of the random mapping table; and

writing a fourth pointer in the first portion of the random mapping table, the fourth pointer points to a location of a latest version of the metadata data structure.

24. The computer readable medium of claim 17 , wherein each random mapping table portion comprises a pointer to a previously written random mapping table portion.

25. The method according to claim 1 , wherein the predetermined condition is reached if the data management structure exceeds a predefined size limit.

26. The system according to claim 10 , wherein the predetermined condition is reached if the data management structure exceeds a predefined size limit.

Assignments (9)