Granted Patent B1

US 11,099,940 · App. 16/917,090 · Granted Aug 24, 2021

Inventors: Dixitkumar Vishnubhai Patel (Monroe, NJ); James H. Shimer (Georgetown, MA); James O. Owens (Nashua, NH)

Assignee: EMC IP Holding Company LLC

G06F11/1451G06F11/1469G06F11/3037G06F12/0238G06F12/0808G06F12/0882G06F2201/84G06F2212/1032G06F2212/7201

Abstract

Claims (103)

1. An apparatus comprising at least one processing device comprising a processor coupled to a memory, the at least one processing device being configured:

to determine that an entry of a first data structure comprises an indication that a first logical page of an address space comprising a plurality of logical pages is an orphan;

to obtain the first logical page based at least in part on the determination that the entry of the first data structure comprises the indication;

to identify a pointer to a second logical page from a second data structure of the first logical page;

to determine a data offset within a volume of the logical address space that corresponds to the pointer;

to determine a snapshot group that corresponds to the first logical page;

to identify a candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page and the pointer;

to determine that the candidate logical page is a match for the first logical page; and

to link the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page.

2. The apparatus of claim 1 wherein the at least one processing device is further configured:

to identify a second candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer; and

to determine that the second candidate logical page is not a match for the first logical page, wherein the identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer responsive to the determination that the second candidate logical page is not a match.

3. The apparatus of claim 1 wherein linking the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page comprises adding a third pointer that points to the first logical page to a given entry in a third data structure of the second logical page, adding a fourth pointer that points to the second logical page to a parent page address value of the first logical page and adding index information corresponding to the given entry in the third data structure to an index-in-parent value of the first logical page.

4. The apparatus of claim 1 wherein the at least one processing device is further configured:

to determine that a second entry of the first data structure comprises a second indication that a third logical page of the address space is an orphan;

to obtain the third logical page based at least in part on the determination that the second entry of the first data structure comprises the indication that the third logical page of the address space is an orphan;

to identify a second pointer to a fourth logical page from a third data structure of the third logical page;

to determine a second data offset within a second volume of the logical address space that corresponds to the second pointer;

to determine a second snapshot group that corresponds to the third logical page;

to identify a plurality of candidate logical pages based at least in part on the second data offset, the second snapshot group, and the second pointer;

to determine that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page; and

to invalidate all copy pointers in the third data structure based at least in part on determining that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page.

5. The apparatus of claim 1 wherein the at least one processing device is further configured:

to determine that an entry of a third data structure comprises an indication that a link between the first logical page and a third logical page of the address space is broken;

to obtain the first logical page based at least in part on the determination that the entry of the third data structure comprises the indication that the link between the first logical page and a third logical page of the address space is broken;

to obtain the third logical page based at least in part on the first logical page;

to determine that the pointer to the second logical page does not match any pointers of the third logical page; and

to add the indication that the first logical page is an orphan to the first data structure based at least in part on the determination that the pointer to the second logical page does not match any pointers of the third logical page.

6. The apparatus of claim 1 wherein:

the pointer comprises a first pointer;

identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises determining that the candidate logical page comprises a second pointer; and

determining that the candidate logical page is a match for the first logical page comprises determining that both the first pointer and the second pointer point to the second logical page.

7. The apparatus of claim 6 wherein:

the second data structure comprises a plurality of copy pointers, the first pointer being one of the copy pointers; and

determining that the candidate logical page is a match for the first logical page comprises determining that each copy pointer in the second data structure comprises a corresponding source or copy pointer in a third data structure of the candidate logical page.

8. A method comprising:

determining that an entry of a first data structure comprises an indication that a first logical page of an address space comprising a plurality of logical pages is an orphan;

obtaining the first logical page based at least in part on the determination that the entry of the first data structure comprises the indication;

identifying a pointer to a second logical page from a second data structure of the first logical page;

determining a data offset within a volume of the logical address space that corresponds to the pointer;

determining a snapshot group that corresponds to the first logical page;

identifying a candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page and the pointer;

determining that the candidate logical page is a match for the first logical page; and

linking the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page;

wherein the method is performed by at least one processing device comprising a processor coupled to a memory.

9. The method of claim 8 wherein the method further comprises:

identifying a second candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer; and

determining that the second candidate logical page is not a match for the first logical page, wherein the identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer responsive to the determination that the second candidate logical page is not a match.

10. The method of claim 8 wherein linking the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page comprises adding a third pointer that points to the first logical page to a given entry in a third data structure of the second logical page, adding a fourth pointer that points to the second logical page to a parent page address value of the first logical page and adding index information corresponding to the given entry in the third data structure to an index-in-parent value of the first logical page.

11. The method of claim 8 wherein method further comprises:

determining that a second entry of the first data structure comprises a second indication that a third logical page of the address space is an orphan;

obtaining the third logical page based at least in part on the determination that the second entry of the first data structure comprises the indication that the third logical page of the address space is an orphan;

identifying a second pointer to a fourth logical page from a third data structure of the third logical page;

determining a second data offset within a second volume of the logical address space that corresponds to the second pointer;

determining a second snapshot group that corresponds to the third logical page;

identifying a plurality of candidate logical pages based at least in part on the second data offset, the second snapshot group, and the second pointer;

determining that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page; and

invalidating all copy pointers in the third data structure based at least in part on determining that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page.

12. The method of claim 8 wherein the method further comprises:

determining that an entry of a third data structure comprises an indication that a link between the first logical page and a third logical page of the address space is broken;

obtaining the first logical page based at least in part on the determination that the entry of the third data structure comprises the indication that the link between the first logical page and a third logical page of the address space is broken;

obtaining the third logical page based at least in part on the first logical page;

determining that the pointer to the second logical page does not match any pointers of the third logical page; and

adding the indication that the first logical page is an orphan to the first data structure based at least in part on the determination that the pointer to the second logical page does not match any pointers of the third logical page.

13. The method of claim 8 wherein:

the pointer comprises a first pointer;

identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises determining that the candidate logical page comprises a second pointer; and

determining that the candidate logical page is a match for the first logical page comprises determining that both the first pointer and the second pointer point to the second logical page.

14. The method of claim 13 wherein:

the second data structure comprises a plurality of copy pointers, the first pointer being one of the copy pointers; and

determining that the candidate logical page is a match for the first logical page comprises determining that each copy pointer in the second data structure comprises a corresponding source or copy pointer in a third data structure of the candidate logical page.

15. A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes the at least one processing device:

to determine that an entry of a first data structure comprises an indication that a first logical page of an address space comprising a plurality of logical pages is an orphan;

to obtain the first logical page based at least in part on the determination that the entry of the first data structure comprises the indication;

to identify a pointer to a second logical page from a second data structure of the first logical page;

to determine a data offset within a volume of the logical address space that corresponds to the pointer;

to determine a snapshot group that corresponds to the first logical page;

to identify a candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page and the pointer;

to determine that the candidate logical page is a match for the first logical page; and

to link the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page.

16. The computer program product of claim 15 wherein:

the second data structure comprises a plurality of copy pointers, the pointer being one of the copy pointers;

identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises determining that the candidate logical page comprises a second pointer; and

determining that the candidate logical page is a match for the first logical page comprises determining that both the first pointer and the second pointer point to the second logical page and that each copy pointer in the second data structure comprises a corresponding source or copy pointer in a third data structure of the candidate logical page.

17. The computer program product of claim 15 wherein the program code further causes the at least one processing device:

to identify a second candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer; and

to determine that the second candidate logical page is not a match for the first logical page, wherein the identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer comprises identifying the candidate logical page based at least in part on the data offset, the snapshot group corresponding to the first logical page, and the pointer responsive to the determination that the second candidate logical page is not a match.

18. The computer program product of claim 15 wherein linking the candidate logical page and the first logical page together in a parent-child relationship based at least in part on the identification that the candidate logical page is a match for the first logical page comprises adding a third pointer that points to the first logical page to a given entry in a third data structure of the second logical page, adding a fourth pointer that points to the second logical page to a parent page address value of the first logical page and adding index information corresponding to the given entry in the third data structure to an index-in-parent value of the first logical page.

19. The computer program product of claim 15 wherein the program code further causes the at least one processing device:

to determine that a second entry of the first data structure comprises a second indication that a third logical page of the address space is an orphan;

to obtain the third logical page based at least in part on the determination that the second entry of the first data structure comprises the indication that the third logical page of the address space is an orphan;

to identify a second pointer to a fourth logical page from a third data structure of the third logical page;

to determine a second data offset within a second volume of the logical address space that corresponds to the second pointer;

to determine a second snapshot group that corresponds to the third logical page;

to identify a plurality of candidate logical pages based at least in part on the second data offset, the second snapshot group, and the second pointer;

to determine that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page; and

to invalidate all copy pointers in the third data structure based at least in part on determining that none of the candidate logical pages in the plurality of candidate logical pages are a match for the third logical page.

20. The computer program product of claim 15 wherein the program code further causes the at least one processing device:

to determine that an entry of a third data structure comprises an indication that a link between the first logical page and a third logical page of the address space is broken;

to obtain the first logical page based at least in part on the determination that the entry of the third data structure comprises the indication that the link between the first logical page and a third logical page of the address space is broken;

to obtain the third logical page based at least in part on the first logical page;

to determine that the pointer to the second logical page does not match any pointers of the third logical page; and

to add the indication that the first logical page is an orphan to the first data structure based at least in part on the determination that the pointer to the second logical page does not match any pointers of the third logical page.

Assignments (9)