Dynamic data structures for tracking file system free space in a flash memory device

• US 20060059326A1
• Filed: 11/04/2005
• Published: 03/16/2006
• Est. Priority Date: 11/21/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kalkman, John, Aasheim, Jered Donald, Yang, Yongqi
• Granted Patent: US 7,093,101 B2
• Time in Patent Office: Days
• US Class Current: 711/203
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99947 Object-oriented database structure reference

Abstract

One or more secondary data structures are maintained containing mappings of logical flash memory addresses to physical flash memory addresses. Each secondary data structure has a predetermined capacity of mappings. A master data structure is also maintained containing a pointer to each of the one or more secondary data structures. Additional secondary data structures are allocated as needed to provide capacity for additional mappings. One or more counters associated with each of the one or more secondary data structures, respectively, provides an indication of when each of the one or more secondary data structures reaches the predetermined capacity of mappings.

Claims

1. In a computer device that uses flash memory to store data, a method comprising:

maintaining one or more secondary data structures containing mappings of logical flash memory addresses to physical flash memory addresses, each secondary data structure having a predetermined capacity of mappings;

maintaining one or more counters associated with each of the one or more secondary data structures, respectively, providing an indication of when each of the one or more secondary data structures reaches the predetermined capacity of mappings; and

maintaining a master data structure containing a pointer to each of the one or more secondary data structures.

2. The method as recited in claim 1, further comprising allocating an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings.

3. The method as recited in claim 1, further comprising allocating an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings and adding a pointer to the master data structure for the additionally allocated secondary data structure.

4. The method as recited in claim 1, wherein the one or more secondary data structures, the one or more counters, and the master data structure are maintained by a file system.

5. The method as recited in claim 1, wherein the one or more secondary data structures, the one or more counters, and the master data structures are stored in a volatile memory device of the computer.

6. The method as recited in claim 1, further comprising removing one or more additionally allocated secondary data structures if the capacity of mappings is not needed.

7. A system for tracking data in a flash medium, comprising:

a secondary data structure containing logical sector address to physical sector address mappings showing a relationship between logical sector addresses, requested by a file system, to physical sector addresses in which associated data is physically stored on the flash medium;

a master data structure containing at least one pointer that points to at least one secondary data structure; and

means for allocating a third data structure, if the secondary data structure becomes full, wherein the third data structure contains logical sector address to physical sector address mappings.

8. The system as recited in claim 7, wherein the master data structure is configurable to contain a pointer that points to the third data structure, if allocated.

9. The system as recited in claim 7, wherein the means for allocating the third data structure includes a counter configured to count how many logical sector address requests are issued to the secondary data structure and provide an indication when the secondary data structure becomes full.

10. The system as recited in claim 7, wherein the means for allocating the third data structure includes a counter configured to count how many logical sector address requests are issued to the secondary data structure and provide an indication that the secondary data structure is available to receive data and has not become full.

11. The system as recited in claim 7, wherein the data structures are stored in a volatile memory device.

12. A system, comprising:

a master data structure containing 1 to N pointers, wherein N is an integer greater than 1;

a secondary data structure containing 1 to K mappings of logical sector addresses to physical sector addresses, the logical sector addresses contained in the secondary data structure being a portion of the maximum possible quantity of logical sector addresses that can be issued by the file system, wherein at least one of the pointers in the master data structure points to the secondary data structure; and

a counter configured to indicate when the secondary data structure contains K mappings of logical sector to physical addresses.

13. The system as recited in claim 12, further comprising a logical-to-physical sector manager configured to allocate a third data structure containing mappings of logical sector addresses to physical sector addresses, if the counter indicates that the secondary data structure contains K mappings of logical sector to physical addresses.

14. The system as recited in claim 12, wherein the counter is initially set to a number K and decremented each time a logical sector address to physical sector address is mapped to the secondary data structure.

15. The system as recited in claim 12, wherein the master and secondary data structures and counter are stored in a volatile memory device.

16. In a computer device that uses flash memory to store data, a method comprising:

generating a master data structure containing a plurality of pointers;

allocating a secondary data structure used to store mappings of logical sector addresses to physical sector addresses, wherein the secondary data structure has a maximum capacity for storing the mappings;

maintaining a counter to indicate if the secondary data structure has reached the maximum capacity;

enabling one of the plurality of pointers to point to the secondary data structure;

checking whether the counter indicates the secondary data structure has reached the maximum capacity;

allocating a third data structure used to store mappings of logical sector addresses to physical sector addresses, if the counter indicates that the secondary data structure has reached the maximum capacity; and

enabling one of the plurality of pointers point to the third data structure, if allocated.

17. The method as recited in claim 16, wherein the logical sector addresses are issued by a file system and the physical sector addresses indicate where data associated with the logical sector addresses is physically stored on a flash medium.

18. The method as recited in claim 16, wherein the computer device is portable processing device.

19. The method as recited in claim 16, wherein the method is managed by a file system.

20. One or more computer-readable media comprising computer executable instructions that, when executed, direct a computer to:

generate a master data structure containing a plurality of pointers;

allocate a secondary data structure used to store mappings of logical sector addresses to physical sector addresses, wherein the secondary data structure has a maximum capacity for storing the mappings;

maintain a counter to indicate if the secondary data structure has reached the maximum capacity;

enable one of the plurality of pointers to point to the secondary data structure;

check whether the counter indicates the secondary data structure has reached the maximum capacity;

allocate a third data structure used to store mappings of logical sector addresses to physical sector addresses, if the counter indicates that the secondary data structure has reached the maximum capacity; and

enable one of the plurality of pointers point to the third data structure, if allocated.

21. One or more computer-readable media comprising computer executable instructions that, when executed, direct a computer to:

maintain one or more secondary data structures containing mappings of logical flash memory addresses to physical flash memory addresses, each secondary data structure having a predetermined capacity of mappings;

maintain one or more counters associated with each of the one or more secondary data structures, respectively, providing an indication of when each of the one or more secondary data structures reaches the predetermined capacity of mappings; and

maintain a master data structure containing a pointer to each of the one or more secondary data structures.

22. The one or more computer-readable media comprising computer executable instructions as recited in claim 21, that when executed, further direct a computer to allocate an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings.

23. The one or more computer-readable media comprising computer executable instructions as recited in claim 21, that when executed, further direct a computer to allocate an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings and adding a pointer to the master data structure for the additionally allocated secondary data structure.

24. The one or more computer-readable media comprising computer executable instructions as recited in claim 21, wherein the one or more secondary data structures, the one or more counters, and the master data structure are part of a file system.

25. The one or more computer-readable media comprising computer executable instructions as recited in claim 21, wherein the one or more secondary data structures, the one or more counters, and the master data structures are stored in a volatile memory device of the computer.

26. A computer, comprising:

a processor;

memory and a flash memory device;

a software system configured to run on the processor and store data structures in the memory by;

(a) maintaining one or more secondary data structures containing mappings of logical flash memory addresses to physical flash memory addresses associated with storing data on the flash memory device, each secondary data structure having a predetermined capacity of mappings;

(b) maintaining one or more counters associated with each of the one or more secondary data structures, respectively, providing an indication of when each of the one or more secondary data structures reaches the predetermined capacity of mappings; and

(c) maintaining a master data structure containing a pointer to each of the one or more secondary data structures.

27. The computer as recited in claim 26, wherein the system is further configured to allocate an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings.

28. The computer as recited in claim 26, further the system is further configured to allocate an additional secondary data structure, if the one or more counters indicates that the one or more secondary data structures has reached the predetermined capacity of mappings and adding a pointer to the master data structure for the additionally allocated secondary data structure.

29. The computer as recited in claim 26, wherein the system is a file system.

30. The computer as recited in claim 26, wherein the memory is a volatile memory device.