Efficient access control for distributed hierarchical file systems

To determine whether a user can access a file in a hierarchical file system a traversal of the directory hierarchy is required in order to check access control for all the parent directories. This traversal can be especially expensive in a distributed system where the files may be on separate devices. We present two approaches for representing the complete access control for a file and its parent directories such that it can be stored locally with each file in order to avoid traversal. We use the well-known CNF and DNF (conjunctive and disjunctive normal form) formats to store permission and ownership information compactly for the entire path to a file. An examination of the structure of an existing large shared file system demonstrates the efficacy of our solution.