Dynamic data structures for tracking data stored in a flash memory device

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;
• 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 and for deallocating the third data structure in the event the secondary data structure is sufficient for mapping physical sector addresses containing data to logical sector addresses;
• and
• a master data structure 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 master data structure containing 1 to N pointers, wherein N is an integer greater than 1;
• a secondary data structure containing 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;
• one or more additional data structures containing mappings of logical sector addresses to physical sector addresses, the one or more additional data structures being allocated when the portion of logical sector addresses contained in the secondary data structure is insufficient to store logical sector address write requests issued by the file system and deallocated if the portion of logical sector addresses contained in the secondary data structure becomes sufficient to store the logical sector address write requests issued by the file system;
• and
• wherein the number of pointers in the master data structure changes as the one or more additional data structures are allocated and deallocated.

A computer device, comprising:

• a flash driver configured to serve as an interface between a file system and the flash memory medium;
• a waster data structure containing enough pointers to match a maximum quantity of logical sector addresses to be issued by the file system;
• a secondary data structure containing 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 to be issued by the file system, wherein ones of the pointers from the master data structure point to specific mappings of logical sector address to physical sector addresses in the secondary data structure;
• and
• one or more additional data structures containing mappings of logical sector addresses to physical sector addresses, allocated by the flash driver when the portion of logical sector addresses contained in the secondary data structure is insufficient to store logical sector address write requests issued by the file system and deallocated by the flash driver if the portion of logical sector addresses contained in the secondary data structure becomes sufficient to store the logical sector address write requests issued by the file system, wherein others of the pointers from the master data structure point to specific mappings of logical sector address to physical sector addresses in the one or more additional data structures, such that the number of pointers in the master data structure pointing to the second and additional data structures varies according to the number of data structures.

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 map logical sector addresses to physical sector addresses, wherein the secondary data structure is limited in size;
• enabling one of the plurality of pointers to point to the secondary data structure;
• allocating a third data structure used to map logical sector addresses to physical sector addresses, if the secondary data structure fills-up, and deallocating the third data structure if the second data structure is no longer filled up;
• and
• enabling one of the plurality of pointers to point to the third data structure, if allocated, such that the number of pointers pointing to data structures changes as the third data structure is allocated and deallocated.

A computer-readable medium far a Flash driver, comprising computer-executable instructions that, when executed, direct the Flash driver to:

• generate a master data structure containing one or more pointers;
• allocate a secondary data structure used to map logical sector addresses to physical sector addresses, 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 the flash medium;
• allocate a third data structure used to map logical sector addresses to physical sector addresses, if the secondary data structure fills-up, and deallocate the third data structure if the second data structure is no longer filled up;
• and
• enable 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.

A computer-readable medium for a Flash driver, comprising computer-executable instructions that, when executed, direct the Flash driver to:

• maintain one or more mapping data structures containing mappings of logical flash memory addresses to physical flash memory addresses, each mapping data structure having a predetermined capacity;
• allocate and deallocate additional mapping data structures as capacity for additional mappings changes;
• and
• maintain a master data structure containing at least one pointer to each of the mapping data structures, wherein the number of pointers changes according to the number of data structures.