Patent ID: 8112465
Filing Date: 2012-02-07
Classification: G06F

Abstract:
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.