Granted Patent B2

US 10,254,963 · App. 15/995,945 · Granted Apr 9, 2019

Abstract

Claims (66)

1. A method comprising:

receiving a request to copy a plurality of data blocks from a first range of logical address to a second range of logical address;

determining a size of the plurality of data blocks;

determining a number of references the plurality of data blocks occupy based on the size of the plurality of data blocks;

determining a forward pointer based on a dynamically sized reverse map for the plurality of data blocks; and

updating the dynamically sized reverse map with an extra entry with the forward pointer and the number of references.

2. The method of claim 1 , wherein a size of the dynamically sized reverse map corresponds to a variable number of mappings for different physical blocks depending on a size of one or more data blocks stored in a physical block.

3. The method of claim 1 , wherein the extra entry extends the dynamically sized reverse map beyond a maximum number of mappings.

4. The method of claim 1 , further comprising:

generating the dynamically sized reverse map including:

determining a number of mappings based on a size of one or more data blocks and a size of a physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks stored in the physical block;

retrieving the dynamically sized reverse map, a size of the dynamically sized reverse map corresponding to the variable number of mappings for different physical blocks; and

creating an entry for the physical block in the dynamically sized reverse map, the entry including the number of mappings of the physical block.

5. The method of claim 4 , wherein generating the dynamically sized reverse map further includes:

determining a starting location in the dynamically sized reverse map for mappings of the one or more data blocks; and

wherein the entry includes the starting location for the one or more data blocks, the entry being an index of the numbers of mappings for the physical block.

6. The method of claim 4 , wherein the number of mappings of the physical block represents a number of buffer entries a physical block consumes.

7. The method of claim 1 , wherein the dynamically sized reverse map includes a dynamic tree structure having an extensible node for a plurality of buffer entries, one buffer entry for each of the plurality of data blocks.

8. The method of claim 7 , wherein the one buffer entry for each of the plurality of data blocks includes a logical block number, a physical block number, a starting sector in a physical block, and a number of sectors occupied in the physical block.

9. The method of claim 8 , wherein the one buffer entry for each of the plurality of data blocks is persisted to a storage device.

10. The method of claim 1 , further comprising:

retrieving information of a map segment from a segment header;

determining a use count of write blocks of the map segment;

determining whether the map segment satisfies dynamically sized reverse map updating criteria based on the use count;

responsive to the map segment satisfying the dynamically sized reverse map updating criteria, performing dynamically sized reverse map updating on the map segment; and

updating the information of the map segment in the segment header.

11. A system comprising:

a dynamically sized reverse map; and

a processor coupled to the dynamically sized reverse map, the processor configured to:

receive a request to copy a plurality of data blocks from a first range of logical address to a second range of logical address;

determine a size of the plurality of data blocks;

determine a number of references the plurality of data blocks occupy based on the size of the plurality of data blocks;

determine a forward pointer based on the dynamically sized reverse map for the plurality of data blocks; and

update the dynamically sized reverse map with an extra entry with the forward pointer and the number of references.

12. The system of claim 11 , wherein a size of the dynamically sized reverse map corresponds to a variable number of mappings for different physical blocks depending on a size of one or more data blocks stored in a physical block.

13. The system of claim 11 , wherein the extra entry extends the dynamically sized reverse map beyond a maximum number of mappings.

14. The system of claim 11 , wherein the processor is further configured to:

generate the dynamically sized reverse map by:

determining a number of mappings based on a size of one or more data blocks and a size of a physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks stored in the physical block;

retrieving the dynamically sized reverse map, a size of the dynamically sized reverse map corresponding to the variable number of mappings for different physical blocks; and

creating an entry for the physical block in the dynamically sized reverse map, the entry including the number of mappings of the physical block.

15. The system of claim 11 , wherein the processor is further configured to:

retrieve information of a map segment from a segment header;

determine a use count of write blocks of the map segment;

determine whether the map segment satisfies dynamically sized reverse map updating criteria based on the use count;

responsive to the map segment satisfying the dynamically sized reverse map updating criteria, perform dynamically sized reverse map updating on the map segment; and

update the information of the map segment in the segment header.

16. A system comprising:

means for receiving a request to copy a plurality of data blocks from a first range of logical address to a second range of logical address;

means for determining a size of the plurality of data blocks;

means for determining a number of references the plurality of data blocks occupy based on the size of the plurality of data blocks;

means for determining a forward pointer based on a dynamically sized reverse map for the plurality of data blocks; and

means for updating the dynamically sized reverse map with an extra entry with the forward pointer and the number of references.

17. The system of claim 16 , wherein a size of the dynamically sized reverse map corresponds to a variable number of mappings for different physical blocks depending on a size of one or more data blocks stored in a physical block.

18. The system of claim 16 , wherein the extra entry extends the dynamically sized reverse map beyond a maximum number of mappings.

19. The system of claim 16 , further comprising:

means for generating the dynamically sized reverse map including:

means for determining a number of mappings based on a size of one or more data blocks and a size of a physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks stored in the physical block;

means for retrieving the dynamically sized reverse map, a size of the dynamically sized reverse map corresponding to the variable number of mappings for different physical blocks; and

means for creating an entry for the physical block in the dynamically sized reverse map, the entry including the number of mappings of the physical block.

20. The system of claim 16 , further comprising:

means for retrieving information of a map segment from a segment header;

means for determining a use count of write blocks of the map segment;

means for determining whether the map segment satisfies dynamically sized reverse map updating criteria based on the use count;

means for, responsive to the map segment satisfying the dynamically sized reverse map updating criteria, performing dynamically sized reverse map updating on the map segment; and

means for updating the information of the map segment in the segment header.

Assignments (11)