Method and system for data structure management

• US 8,694,750 B2
• Filed: 12/19/2008
• Issued: 04/08/2014
• Est. Priority Date: 12/19/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Vyshetsky, Dmitry, Gyugyi, Paul
• Primary Examiner(s): Bansal, Gurtej
• Application Number:
  US12/339,664
• Publication Number:
  US 20100161876A1
• Time in Patent Office: 1,936 Days
• Field of Search: 711/1, 711/5, 711/103, 711/137, 711/170, 711/202, 711/221
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7211 Wear leveling

Abstract

Embodiments of the present invention are directed to a method and system for allowing data structures to be moved between storage locations of varying performance and cost without changing the application firmware. In one embodiment, rather than application firmware directly accessing memory, the application firmware requests a data structure by parameters, to which the implementation returns a pointer. The parameters can be, for example, the logical block address of a data sector, and the data structure can be mapping and associated information of that logical block address (LBA) to a location in the flash device.

Claims

1. A method for managing data structures in a storage device of a system, said method comprising:

receiving a request in a firmware application for data located in a storage device, said firmware application being executed in said storage device but not directly accessing said storage device;

determining a current memory configuration of said system;

determining a location of a reference data structure in a memory based on said current memory configuration, said reference data structure comprising a plurality of parameters corresponding to said data

when said reference data structure does not yet exist,

i) gathering a plurality of condensed data elements comprised in a plurality of hardware devices of said system, the plurality of condensed data elements comprising a plurality of addressing elements condensed into a binary value;

ii) processing said plurality of condensed data elements to extract said plurality of addressing elements;

iii) converting said plurality of addressing elements into a temporary data structure;

iv) storing said temporary data structure in a local memory as said reference data structure; and

returning said location of said reference data structure to said firmware application.

2. The method according to claim 1, wherein said storage device is a flash memory device.

3. The method according to claim 1, wherein said receiving said request comprises receiving a request for data stored at a logical block address in a sector of said storage device.

4. The method according to claim 1, wherein said memory is local memory and said location comprises a location of said reference data structure in said local memory.

5. The method according to claim 1, wherein said memory is an external memory and said location comprises a location of said reference data structure in said external memory.

6. The method according to claim 1, wherein said determining said location comprises transferring said reference data structure from a location in an external memory to a location in said local memory when said location of said reference data structure comprises a location in said external memory.

7. The method according to claim 1, wherein a data element from said plurality of data elements is stored in hardware offload.

8. The method according to claim 1, further comprising transferring a reference from a first location in a first memory type to a second location in a second memory type, wherein said transferring is performed prior to returning said location of said reference data structure.

9. The method according to claim 1, wherein said plurality of hardware devices comprises a network interface card (NIC).

10. The method according to claim 1, wherein said plurality of hardware devices comprises a microprocessor.

11. The method according to claim 1, further comprising:

pre-fetching a plurality of references corresponding to a plurality of speculative subsequent requests from said firmware application; and

storing said plurality of references in a cache.

12. The method according to claim 11, wherein said storing said plurality of references in a cache comprises transferring said plurality of references from a first plurality of locations in memory to a second plurality of locations in a cache in said memory.

13. The method according to claim 11, wherein said pre-fetching said plurality of references comprises:

anticipating a plurality of subsequent requests for data from said firmware application; and

determining a plurality of locations in said memory for a plurality of references corresponding to said plurality of subsequent requests.

14. The method according to claim 13, wherein said determining said plurality of locations in memory comprises:

referencing a plurality of data elements corresponding to said plurality of subsequent requests;

converting said plurality of data elements into a plurality of temporary data structures;

storing said plurality of temporary data structures in a plurality of locations in memory; and

returning said plurality of locations.

15. A method of managing the storage of data structures in a storage device, the method comprising:

mapping a logical address corresponding to a sector in a flash memory to a physical address of said flash memory;

converting said physical address to a data structure comprising a plurality of data elements;

storing said data structure in a derived location in a local memory when said data structure exists,

when said data structure does not yet exist,

i) gathering a plurality of condensed data elements comprised in a plurality of hardware devices coupled to said storage device, the plurality of condensed data elements comprising a plurality of addressing elements condensed into a binary value;

ii) processing said plurality of condensed data elements to extract said plurality of addressing elements;

iii) converting said plurality of addressing elements into a temporary data structure; and

iv) storing said temporary data structure as said data structure in said local memory.

16. The method according to claim 15 wherein said data structure comprises a plurality of parameters corresponding to said physical address of said data in said flash memory.

17. The method according to claim 15, wherein storing said data structure comprises managing storage of said data structure among a plurality of storage types.

18. The method according to claim 17, wherein said managing storage of said data structure comprises transferring said data structure from a location in said local memory to a location in a processor cache.

19. A system comprising a flash memory device, a plurality of storage components and a hardware device including a processor and a cache, the system comprising a plurality of program instructions, which when executed by the processor causes the system to implement a method of managing data structure requests in a system, said plurality of program instructions comprising:

instructions to map a logical address corresponding to a sector in a flash memory to a physical address of said flash memory;

converting said physical address to a data structure comprising a plurality of data elements;

instructions to store said data structure in a derived location in a local memory when said data structure exists,

when said data structure does not yet exist,

i) gathering a plurality of condensed data elements comprised in a plurality of hardware devices coupled to said storage device, the plurality of condensed data elements comprising a plurality of addressing elements condensed into a binary value;

ii) processing said plurality of condensed data elements to extract said plurality of addressing elements;

iii) converting said plurality of addressing elements into a temporary data structure; and

iv) storing said temporary data structure as said data structure in said local memory.

20. The system according to claim 19, said plurality of program instructions further comprising:

instructions to manage a plurality of data structures corresponding to a plurality of data sectors in said flash memory.

21. The system according to claim 20, wherein said instructions to manage a plurality of data structures comprises instructions to transfer said plurality of data structures to a location in said cache according to a heuristic to improve performance.