Granted Patent B2

US 11,256,678 · App. 16/916,763 · Granted Feb 22, 2022

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

Assignee: EMC IP Holding Company LLC

G06F16/2272G06F16/2246

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 link between a first logical page of a plurality of logical pages of a logical address space and a second logical page of the plurality of logical pages is broken;

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 obtain the second logical page based at least in part on the first logical page;

to determine that a first address pointed to by a first pointer of the first logical page and a second address pointed to by a corresponding second pointer of the second logical page match;

to determine that the first logical page corresponds to the second logical page based at least in part on the determination that the first address and the second address match; and

to add an indication of a third address that corresponds to the first logical page to an entry associated with the second logical page based at least in part on the determination that the first logical page corresponds to the second logical page.

2. The apparatus of claim 1 wherein:

the first logical page comprises an indication of a fourth address that corresponds to the second logical page and an index that indicates which entry associated with a second data structure of the second logical page corresponds to the first logical page;

obtaining the second logical page based at least in part on the first logical page comprises obtaining the second logical page based at least in part on the indication of the fourth address that corresponds to the second logical page; and

as part of adding the indication of the third address that corresponds to the first logical page to the entry associated with second logical page, the at least one processing device is further configured:

to determine whether or not the entry associated with the second data structure that is indicated by the index is empty;

responsive to a determination that the entry associated with the second data structure that is indicated by the index is empty, to add the indication of the third address to the entry; and

responsive to a determination that the entry associated with the second data structure comprises an indication of an address corresponding to another logical page, to add the indication of the third address to another empty entry associated with the second data structure and to update the index of the first logical page to indicate the entry to which the indication of the third address was added.

3. The apparatus of claim 2 wherein:

the second data structure comprises a plurality of entries; and

as part of adding the indication of the third address to the another empty entry associated with the second data structure, the at least one processing device is further configured:

to determine that the plurality of entries of the second data structure are full;

to allocate a third data structure for storing indications of addresses associated with the second data structure;

to copy the indications of addresses stored in the plurality of entries of the second data structure to corresponding entries in the third data structure;

to add the indication of the third address to an empty entry of the third data structure; and

to add an indication of the third data structure to an entry of the second data structure.

4. The apparatus of claim 1 wherein:

the at least one processing device organizes the logical address space as a tree structure comprising a plurality of logical page levels;

a first logical page level of the plurality of logical page levels comprises the first logical page and the second logical page;

a second logical page level of the plurality of logical page levels comprises a third logical page; and

determining that the first address and the second address match comprises determining that the first address and the second address are the same address and correspond to the third logical page.

5. The apparatus of claim 1 wherein the at least one processing device is further configured to perform a file system check process, the file system check process comprising:

obtaining the first logical page;

determining a parent-child relationship between the first logical page and the second logical page based at least in part on an indication in the first logical page of a fourth address that corresponds to the second logical page;

obtaining the second logical page based at least in part on the indication in the first logical page of the fourth address that corresponds to the second logical page;

determining that the second logical page does not comprise an indication of the third address that corresponds to the first logical page;

generating the first data structure; and

adding the indication that the link between the first logical page and the second logical page is broken to the entry of the first data structure based at least in part on the determination that the second logical page does not comprise the indication of the third address that corresponds to the first logical page, the entry of the first data structure corresponding to the first logical page.

6. 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 an indication that a link between a fourth logical page of a plurality of logical pages and a fifth logical page of the plurality of logical pages is broken;

to obtain the fourth logical page based at least in part on the determination that the second entry of the first data structure comprises the indication, the fourth logical page comprising a plurality of pointers;

to obtain the fifth logical page based at least in part on address information in the fourth logical page that points to the fifth logical page;

to determine whether or not each pointer of the plurality of pointers of the fourth logical page that is a copy pointer has a corresponding source pointer or copy pointer in the fifth logical page; and

responsive to at least one of the copy pointers of the fourth logical page not having a corresponding source or copy pointer in the fifth logical page, to set the address information in the fourth logical page to point to the fourth logical page.

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

to determine whether or not each pointer of the plurality of pointers of the fourth logical page that is a source pointer has a corresponding source pointer or copy pointer in the fifth logical page; and

responsive to at least one of the source pointers of the fourth logical page having a corresponding source or copy pointer in the fifth logical page, to set the address information in the fourth logical page to point to the fourth logical page.

8. A method comprising:

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

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

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

determining that a first address pointed to by a first pointer of the first logical page and a second address pointed to by a corresponding second pointer of the second logical page match;

determining that the first logical page corresponds to the second logical page based at least in part on the determination that the first address and the second address match; and

adding an indication of a third address that corresponds to the first logical page to an entry associated with the second logical page based at least in part on the determination that the first logical page corresponds to the second 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 first logical page comprises an indication of a fourth address that corresponds to the second logical page and an index that indicates which entry associated with a second data structure of the second logical page corresponds to the first logical page;

obtaining the second logical page based at least in part on the first logical page comprises obtaining the second logical page based at least in part on the indication of the fourth address that corresponds to the second logical page; and

as part of adding the indication of the third address that corresponds to the first logical page to the entry associated with second logical page, the method further comprises:

determining whether or not the entry associated with the second data structure that is indicated by the index is empty;

responsive to a determination that the entry associated with the second data structure that is indicated by the index is empty, adding the indication of the third address to the entry; and

responsive to a determination that the entry associated with the second data structure comprises an indication of an address corresponding to another logical page, adding the indication of the third address to another empty entry associated with the second data structure and to update the index of the first logical page to indicate the entry to which the indication of the third address was added.

10. The method of claim 9 wherein:

the second data structure comprises a plurality of entries; and

as part of adding the indication of the third address to the another empty entry associated with the second data structure, the method further comprises:

determining that the plurality of entries of the second data structure are full;

allocating a third data structure for storing indications of addresses associated with the second data structure;

copying the indications of addresses stored in the plurality of entries of the second data structure to corresponding entries in the third data structure;

adding the indication of the third address to an empty entry of the third data structure; and

adding an indication of the third data structure to an entry of the second data structure.

11. The method of claim 8 wherein:

the logical address space is organized as a tree structure comprising a plurality of logical page levels;

a first logical page level of the plurality of logical page levels comprises the first logical page and the second logical page;

a second logical page level of the plurality of logical page levels comprises a third logical page; and

determining that the first address and the second address match comprises determining that the first address and the second address are the same address and correspond to the third logical page.

12. The method of claim 8 wherein the method further comprises performing a file system check process, the file system check process comprising:

obtaining the first logical page;

determining a parent-child relationship between the first logical page and the second logical page based at least in part on an indication in the first logical page of a fourth address that corresponds to the second logical page;

obtaining the second logical page based at least in part on the indication in the first logical page of the fourth address that corresponds to the second logical page;

determining that the second logical page does not comprise an indication of the third address that corresponds to the first logical page;

generating the first data structure; and

adding the indication that the link between the first logical page and the second logical page is broken to the entry of the first data structure based at least in part on the determination that the second logical page does not comprise the indication of the third address that corresponds to the first logical page, the entry of the first data structure corresponding to the first logical page.

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

determining that a second entry of the first data structure comprises an indication that a link between a fourth logical page of a plurality of logical pages and a fifth logical page of the plurality of logical pages is broken;

obtaining the fourth logical page based at least in part on the determination that the second entry of the first data structure comprises the indication, the fourth logical page comprising a plurality of pointers;

obtaining the fifth logical page based at least in part on address information in the fourth logical page that points to the fifth logical page;

determining whether or not each pointer of the plurality of pointers of the fourth logical page that is a copy pointer has a corresponding source pointer or copy pointer in the fifth logical page; and

responsive to at least one of the copy pointers of the fourth logical page not having a corresponding source or copy pointer in the fifth logical page, setting the address information in the fourth logical page to point to the fourth logical page.

14. The method of claim 13 wherein the method further comprises:

determining whether or not each pointer of the plurality of pointers of the fourth logical page that is a source pointer has a corresponding source pointer or copy pointer in the fifth logical page; and

responsive to at least one of the source pointers of the fourth logical page having a corresponding source or copy pointer in the fifth logical page, setting the address information in the fourth logical page to point to the fourth logical page.

15. 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 link between a first logical page of a plurality of logical pages of a logical address space and a second logical page of the plurality of logical pages is broken;

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, the first logical page comprising a second data structure comprising a plurality of entries, a given entry of the plurality of entries corresponding to the second logical page;

to obtain the second logical page based at least in part on the given entry;

to determine whether or not a first address pointed to by a first pointer of the first logical page and a second address pointed to by a corresponding second pointer of the second logical page match; and

responsive to the first address and the second address matching, to set parent information in the second logical page to point to the first logical page.

16. The apparatus of claim 15 wherein setting parent information in the second logical page to point to the first logical page comprises setting a parent page address in the second logical page to point to the first logical page and setting an index-in-parent value in the second logical page to indicate an index of the given entry in the second data structure.

17. The apparatus of claim 15 wherein the at least one processing device is further configured, responsive to the first address not matching the second address, to set the given entry to invalid.

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

to determine that an entry that corresponds to the second logical page in a third data structure comprises an indication that multiple logical pages are linked to the second logical page;

to determine whether or not an entry that corresponds to the second logical page in a fourth data structure comprises an indication that the second logical page is owned by another logical page; and

responsive to determining that the second logical page is owned by another logical page, to set the given entry to invalid.

19. The apparatus of claim 18 wherein the at least one processing device is further configured, responsive to determining that the second logical page is not owned by another logical page, to set the entry that corresponds to the second logical page in the fourth data structure to indicate that the second logical page is owned by another logical page.

20. The apparatus of claim 15 wherein obtaining the second logical page based at least in part on the given entry comprises:

determining that a third data structure comprises an indication that a link between the second logical page and the first logical page is broken; and

obtaining the second logical page based at last in part on the determination that the third data structure comprises the indication that the link between the second logical page and the first logical page is broken.

Assignments (9)

Continuity (1)

Cited By (1)

US 12,360,707