System, device, and method for validating data structures in a storage system

1. A method of validating a data structure in a storage system, the data structure comprising a table having a sequence of table entries, each table entry including a type field and a pointer field, the type field indicating whether the table entry is used or free, the pointer field including a reference to a next free table entry if the table entry is free such that the data structure includes at least one list of free table entries linked using pointer fields, the method comprising:

(a) maintaining a tracking structure in a memory, the tracking structure including a corresponding status field for each table entry, the status fields having an unmarked state and a marked state;

(b) processing the table entries sequentially and tracking the used and free table entries using the tracking structure, such tracking including marking the status fields corresponding to used table entries and marking the status fields corresponding to the next free table entries referenced in the pointer fields of free table entries; and

(c) determining validity of the data structure based on the tracking structure.

2. A method according to claim 1 , wherein the tracking structure includes one of:

a bitmap;

an array; and

a table.

3. A method according to claim 1 , wherein processing the table entries sequentially and tracking the used and free table entries using the tracking structure comprises, for each table entry:

(b1) determining whether the table entry is used or free based on the type field;

(b2) if the table entry is used and the corresponding status field in the tracking structure is marked, outputting an error indication indicating that the data structure is corrupted;

(b3) if the table entry is used and the corresponding status field in the tracking structure is unmarked, marking such status field in the tracking structure;

(b4) if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is marked, outputting an error indication indicating that the data structure is corrupted; and

(b5) if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is unmarked, marking such status field in the tracking structure.

4. A method according to claim 3 , further comprising:

outputting an error indication if the tracking structure includes any erroneous unmarked status entries after the sequential processing of the table entries.

5. A method according to claim 1 , wherein the list of free table entries is non-circular.

6. A method according to claim 1 , wherein the list of free table entries is circular such that a last free table entry includes a reference to a first free table entry.

7. A method according to claim 1 , wherein the data structure includes a plurality of free table entries lists.

8. A method according to claim 1 , wherein the data structure is a filesystem indirection object.

9. Apparatus providing for validation of a data structure in a storage system, the data structure comprising a table having a sequence of table entries, each table entry including a type field and a pointer field, the type field indicating whether the table entry is used or free, the pointer field including a reference to a next free table entry if the table entry is free such that the data structure includes a list of free table entries linked using pointer fields, the apparatus comprising:

table entry processing logic configured to process the table entries sequentially and track the used and free table entries using a tracking structure, the tracking structure including a corresponding status field for each table entry, the status fields having an unmarked state and a marked state, such processing and tracking including marking the status fields corresponding to used table entries and marking the status fields corresponding to the next free table entries referenced in the pointer fields of free table entries; and

validation logic configured to determine validity of the data structure based on the tracking structure.

10. Apparatus according to claim 9 , wherein the tracking structure includes at least one of:

a bitmap;

and array; and

a table.

11. Apparatus according to claim 9 , wherein, for each table entry, the table entry processing logic is configured to:

determine whether the table entry is used or free based on the type field;

if the table entry is used and the corresponding status field in the tracking structure is marked, output an error indication indicating that the data structure is corrupted;

if the table entry is used and the corresponding status field in the tracking structure is unmarked, mark such status field in the tracking structure;

if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is marked, output an error indication indicating that the data structure is corrupted; and

if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is unmarked, mark such status field in the tracking structure.

12. Apparatus according to claim 11 , wherein the validation logic is configured to output an error indication if the tracking structure includes any erroneous unmarked status entries after the sequential processing of the table entries by the table entry processing logic.

13. Apparatus according to claim 9 , wherein the list of free table entries is non-circular.

14. Apparatus according to claim 9 , wherein the list of free table entries is circular such that a last free table entry includes a reference to a first free table entry.

15. Apparatus according to claim 9 , wherein the data structure includes a plurality of free table entries lists.

16. Apparatus according to claim 9 , wherein the data structure is a filesystem indirection object.

17. A system providing for validation of a data structure, the data structure comprising a table having a sequence of table entries, each table entry including a type field and a pointer field, the type field indicating whether the table entry is used or free, the pointer field including a reference to a next free table entry if the table entry is free such that the data structure includes a list of free table entries linked using pointer fields, the system comprising:

a memory in which a tracking structure is maintained, the tracking structure including a corresponding status field for each table entry, the status fields having an unmarked state and a marked state; and

a validator configured to process the table entries sequentially and track the used and free table entries using the tracking structure, such processing and tracking including marking the status fields corresponding to used table entries and marking the status fields corresponding to the next free table entries referenced in the pointer fields of free table entries, the validator further configured to determine validity of the data structure based on the tracking structure.

18. A system according to claim 17 , wherein the tracking structure includes at least one of:

a bitmap;

an array; and

a table.

19. A system according to claim 17 , wherein, for each table entry, the validator is configured to:

determine whether the table entry is used or free based on the type field;

if the table entry is used and the corresponding status field in the tracking structure is marked, output an error indication indicating that the data structure is corrupted;

if the table entry is used and the corresponding status field in the tracking structure is unmarked, mark such status field in the tracking structure;

if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is marked, output an error indication indicating that the data structure is corrupted; and

if the table entry is free and the status field corresponding to the next free table entry referenced in the pointer field of the table entry is unmarked, mark such status field in the tracking structure.

20. A system according to claim 19 , wherein the validator is further configured to output an error indication if the tracking structure includes any erroneous unmarked status entries after the sequential processing of the table entries by the table entry processing logic.

21. A system according to claim 17 , wherein the list of free table entries is non-circular.

22. A system according to claim 17 , wherein the list of free table entries is circular such that a last free table entry includes a reference to a first free table entry.

23. A system according to claim 17 , wherein the data structure includes a plurality of free table entries lists.

24. A system according to claim 17 , wherein the data structure is a filesystem indirection object.