Allocator – The process Disk Operating System uses to assign specific region or portion of the hard drive in a computer device.
When we are talking about allocator in data recovery field, it is usually block allocator. The logic inside file system which decides where to place newly allocated blocks in order to maintain several constraints (like data locality, low fragmentation).
Block allocation is the heart of a ﬁle system design. A block allocator (aka pool allocator) allocates medium to large memory blocks and provides a service to allocate/deallocate smaller, fixed-size blocks. It allows high allocation/deallocation speed, low memory fragmentation and efficient use of data caches and of virtual memory.
The Ext3 ﬁle system is partitioned into 128 MB block group chunks. Each block group maintains a single block bitmap to describe data block availability inside this block group. This way allocation on different block groups can be done in parallel. When allocating a block for a ﬁle, the Ext3 block allocator always starts from the block group where the inode structure is stored to keep the meta-data and data blocks close to each other. When there are no free blocks available in the target block group it will search for a free block from the rest of the block groups. Ext3 always tries to keep the ﬁles under the same directory close to each other until the parent block group is ﬁlled.
The Ext4 multiple block allocator tries to address the Ext3 block allocator limitation discussed above. The main goal is to provide better allocation for small and large ﬁles. This is achieved by using a different strategy for different allocation requests.