Allocation Clusters

Files in the UOSFS are stored in extents that can exist anywhere on the store. This allows an efficient use of the store's total capacity at the expense of some overhead. Each file, unless it has zero length, has an allocation cluster chain which is simply an array of 64-bit pointers. Each non-zero pointer indicates the location of an extent for the file on the store. An entire cluster is used to store a set of extent pointers, which means the number of pointers kept in a cluster is the cluster size divided by 8. However, the last pointer in the cluster is not a pointer to a file extent, but a pointer to the next cluster in the allocation cluster chain. In this way, a file can be of any size. The process of moving from one cluster to another while reading the allocation chain is called a "turn".

Here is a diagram of an allocation cluster chain on a store with a cluster size of 512: