Apparatus, system, and method for efficient mapping of virtual and physical addresses

• US 8,195,912 B2
• Filed: 04/06/2008
• Issued: 06/05/2012
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Zappe, Michael, Strasser, John, Atkisson, David, Thatcher, Jonathan
• Primary Examiner(s): Elmore, Stephen
• Assistant Examiner(s): Giardino, Jr., Mark A
• Application Number:
  US12/098,434
• Publication Number:
  US 20090150641A1
• Time in Patent Office: 1,521 Days
• Field of Search: 711/103, 711/202, 711/206
• US Class Current: 711/202
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards

Abstract

An apparatus, system, and method are disclosed for efficiently mapping virtual and physical addresses. A forward mapping module uses a forward map to identify physical addresses of data of a data segment from a virtual address. The data segment is identified in a storage request. The virtual addresses include discrete addresses within a virtual address space where the virtual addresses sparsely populate the virtual address space. A reverse mapping module uses a reverse map to determine a virtual address of a data segment from a physical address. The reverse map maps the data storage device into erase regions such that a portion of the reverse map spans an erase region of the data storage device erased together during a storage space recovery operation. A storage space recovery module uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region.

Claims

1. An apparatus to efficiently map physical and virtual addresses, the apparatus comprising:

a forward mapping module that uses a forward map to identify one or more physical addresses of data using one or more virtual addresses wherein each virtual address entry of the forward map sparsely populates a virtual address space of a data storage device storing the data;

a reverse mapping module that uses a reverse map to determine the one or more virtual addresses from the one or more physical addresses of the data, the reverse map organized by erase regions of the data storage device such that reverse map entries for an erase region are identifiable in the reverse map, a storage space recovery operation recovering an erase region for future storage of data; and

a storage space recovery module that uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region based on reverse map entries for the erase region, the identified valid data moved to another erase region prior to the recovery operation, wherein the forward mapping module, the reverse mapping module, and the storage space recovery module comprise one or more of logic hardware and computer executable code stored in a computer readable storage medium.

2. The apparatus of claim 1, wherein one or more source parameters are stored with the data, the source parameters comprising at least a virtual address corresponding to the data and a data length of the stored data.

3. The apparatus of claim 2, further comprising a map rebuild module that rebuilds the forward map and the reverse map using the source parameters stored with the data.

4. The apparatus of claim 3, further comprising a checkpoint module that stores information related to the forward map and the reverse map, the checkpoint related to a point in time, the information sufficient to restore the forward map and the reverse map to a status related to the checkpoint.

5. The apparatus of claim 4, further comprising a map sync module that updates the forward map and the reverse map from the status related to the checkpoint to a current status by sequentially applying source parameters and physical addresses, the source parameters stored with data that was sequentially stored after the checkpoint, the physical addresses derived from a location of the data on the data storage device.

6. The apparatus of claim 1, wherein the forward map and the reverse map are independent of one or more of a file structure, a name space, and a directory that organize data for a requesting device transmitting the storage request.

7. The apparatus of claim 1, wherein a virtual address of the data comprises one or more of a file name, an object name, and a block storage address, the block storage address comprising at least a physical address where a requesting device transmitting a storage request corresponding to the data intends for the storage device to store the data and a length of the data.

8. The apparatus of claim 1, wherein the forward map and the reverse map comprise a first forward map and a first reverse map and wherein the first forward map and the first reverse map are stored as metadata and are stored independent of data mapped by the first forward map and the first reverse map, the metadata comprising the first forward map, the first reverse map, and timestamp data stored with the first forward map and the first reverse map, the metadata of the first forward map and the first reverse map being indexed by a second forward map and a second reverse map.

9. The apparatus of claim 8, further comprising one or more additional forward and reverse maps, each stored as metadata and indexed by additional forward and reverse maps.

10. The apparatus of claim 1, wherein the forward map comprises information for valid data stored in the data storage device and the reverse map comprises information for valid data and invalid data stored on the data storage device.

11. The apparatus of claim 1, further comprising an invalidate module that marks an entry for data in the reverse map indicating that data referenced by the entry is invalid in response to an operation resulting in the data being invalidated.

12. The apparatus of claim 11, wherein the storage space recovery module further comprises determining a quantity of invalid data in an erase region by scanning the reverse map for the erase region to determine a quantity of invalid data in relation to a storage capacity of the erase region, the storage space recovery module using the quantity of invalid data in an erase region to select an erase region for recovery.

13. The apparatus of claim 12, wherein the storage space recovery module further comprises selecting an erase region for recovery, writing valid data from the selected erase region to a new location in the data storage device where data is currently being written, updating the reverse map to indicate that the valid data written to the new location is invalid in the selected erase region, and updating the forward map and the reverse map based on the valid data written to the new location.

14. The apparatus of claim 1, wherein the apparatus emulates a random access, block storage device storing data as directed by a storage request corresponding to the data.

15. The apparatus of claim 1, wherein the forward map comprises one or more of a B-tree, a content addressable memory (“

CAM”

), a binary tree, and a hash table.

16. The apparatus of claim 1, further comprising a map update module that updates one or more of the forward map and the reverse map in response to altering contents of the data storage device, the map update module receiving information linking a physical address of stored data to a virtual address from the data storage device based on a location where the data storage device stored the data.

17. The apparatus of claim 1, wherein the apparatus receives a storage request corresponding to the data without the data.

18. The apparatus of claim 17, wherein the apparatus initiates one or more of a direct memory access (“

DMA”

) process and a remote DMA (“

RDMA”

) process to transfer the data to the data storage device in response to the storage request.

19. The apparatus of claim 1, wherein at least a portion of one or more of the forward mapping module, the reverse mapping module, and the storage space recovery module is located within one or more of a requesting device that transmits a storage request corresponding to the data, the data storage device, the storage device controller, and a computing device separate from the requesting device, the data storage device, and the storage device controller.

20. A system to efficiently map physical and virtual addresses, the system comprising:

a data storage device;

a storage controller controlling data storage on the data storage device, the storage controller comprising

a forward mapping module that uses a forward map to identify one or more physical addresses of data using one or more virtual addresses wherein each virtual address entry of the forward map sparsely populates a virtual address space of a data storage device storing the data;

a reverse mapping module that uses a reverse map to determine the one or more virtual addresses from the one or more physical addresses of the data, the reverse map organized by erase regions of the data storage device such that reverse map entries for an erase region are identifiable in the reverse map, a storage space recovery operation recovering an erase region for future storage of data; and

a storage space recovery module that uses the reverse map to identify valid data in an erase region prior to an operation to recover the erase region based on reverse map entries for the erase region, the identified valid data moved to another erase region prior to the recovery operation.

21. The system of claim 20, wherein a storage request corresponding to the data is received from a client in communication with the storage controller over a computer network.

22. The system of claim 20, further comprising a server, wherein one or more of the storage controller and the data storage device are within the server.

23. The system of claim 20, wherein the storage device comprises a solid-state storage device and wherein the data is stored in the solid-state storage.

24. A method for efficiently mapping physical and virtual addresses, the method comprising:

using a forward map to identify one or more physical addresses of data using one or more virtual addresses wherein each virtual address entry of the forward map sparsely populates a virtual address space of a data storage device storing the data;

using a reverse map to determine the one or more virtual addresses from the one or more physical addresses of the data, the reverse map organized by erase regions of the data storage device such that reverse map entries for an erase region are identifiable in the reverse map, a storage space recovery operation recovering an erase region for future storage of data; and

using the reverse map to identify valid data in an erase region prior to an operation to recover the erase region based on reverse map entries for the erase region, the identified valid data moved to another erase region prior to the recovery operation.