Methods and a processing system directed to a file system checker are described. A file system checker performs file system validation by validating a file system's nodes. Each node is associated with two kinds of data: metadata and referenced data. A file system checker may validate one node at a time or a group of nodes contemporaneously (e.g., in parallel). The file system checker uses a dual phase procedure. The first phase includes validating metadata. The second phase includes validating, as appropriate, node type or link count. Dual phase file system checking allows validation of a node without validating referenced data associated with downstream nodes. Where validation of a given node requires validating a downstream node, performing a first phase test on the downstream node is sufficient to validate the given node. Upon completion, the given node may be unlocked for access by external devices and users.