Dynamic data structures for tracking file system free space in a flash memory device
AssigneeMicrosoft Corporation
InventorsJered Aasheim, Yongqi Yang, John Kalkman
Life of this patent
Estimating the term…
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.
Claims13
A computer-readable medium having computer-executable instructions for performing steps 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;
- maintaining one or more counters associated with each of the one or more secondary data structures, respectively, to provide an indication of when each of the one or more secondary data structures reaches the predetermined capacity;
- allocating one or more additional secondary data structures if the one or more counters indicate that the one or more secondary data structures has reached the predetermined capacity;
- removing one or more additionally allocated secondary data structures if additional capacity is not needed;
- and
- maintaining a master data structure containing a pointer to each of the one or more secondary data structures, wherein the number of pointers changes according to the number of secondary data structures.
A system for tracking data in a flash medium, comprising:
- a means for 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 means for allocating a third data structure, containing logical sector address to physical sector address mappings when a count of how many logical sector address requests are issued to the secondary data structure indicates that the secondary data structure is full and for deallocating the third data structure in the event that the count indicates that the secondary data structure is sufficient;
- and
- a means for containing one or more pointers that point to the secondary data structure and the third data structure, if allocated, wherein the number of pointers changes as the third data structure is allocated and deallocated.
A system, comprising:
- a means for containing 1 to N pointers, wherein N is an integer greater than 1;
- a means for 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 L,
- a means for indicating when the secondary data structure contains K mappings of logical sector to physical addresses;
- a means for containing mappings of logical sector addresses to physical sector addresses, the one or more additional data structures being allocated when the counter indicates that the secondary data structure contains K mappings and deallocated if the secondary data structure becomes sufficient to store the topical sector address write requests issued by the file system;
- and,
- wherein the number of pointers changes as the one or more additional data structures are allocated and deallocated.
A computer-readable medium having computer-executable instructions for performing steps comprising:
- generating a master data structure containing a one or more 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 far storing the mappings;
- maintaining a counter to indicate if the secondary data structure has reached the maximum capacity;
- 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 deallocatinq the third data structure if the second data structure no longer reaches the maximum capacity;
- and
- enabling pointers from the master data structure to point to the second and third data structures, wherein the number of pointers changes as the third data structure is allocated and deallocated.
Dependencies are inferred from the claim text.