File Allocation Methods

File allocation is the core technique a file system uses to manage storage space. It decides how a file is organized on a storage device and how the file is reached afterwards. The available methods each have their own strengths and weaknesses in terms of performance, space efficiency, and implementation complexity.

Basic Concepts of File Allocation

What File Allocation Is

File allocation is the way a file system hands out storage space to files. It determines the physical organization of a file’s data on the storage device.

The Basic Unit of Allocation

• Sector: the smallest unit a disk reads and writes, usually 512 bytes
• Block: the basic unit of allocation in a file system, usually 4 KB or larger
• Cluster: the allocation unit used by some file systems

Goals of an Allocation Strategy

1. Efficient access: support fast file reads and writes
2. Space utilization: make the most of the available storage space
3. Fragmentation management: minimize storage fragmentation
4. Extensibility: support dynamic changes in file size

Contiguous Allocation

Contiguous allocation is the simplest file allocation method: all of a file’s data blocks are stored consecutively on the storage device.

Basic Idea

// Data structure for contiguous allocation
struct contiguous_file {
    int start_block;    // starting block number
    int block_count;    // number of blocks
    int file_size;      // file size
    char filename[256]; // file name
};

// The file allocation table
struct allocation_table {
    struct contiguous_file files[MAX_FILES];
    int file_count;
    int free_blocks[MAX_BLOCKS];
    int free_block_count;
};

Allocation Algorithms

First Fit Algorithm

// Implementation of the first fit algorithm
int first_fit_allocate(int file_size, int block_size) {
    int blocks_needed = (file_size + block_size - 1) / block_size;
    int consecutive_blocks = 0;
    int start_block = -1;

    for (int i = 0; i < TOTAL_BLOCKS; i++) {
        if (is_block_free(i)) {
            if (consecutive_blocks == 0) {
                start_block = i;
            }
            consecutive_blocks++;

            if (consecutive_blocks >= blocks_needed) {
                // Found enough consecutive blocks
                mark_blocks_used(start_block, blocks_needed);
                return start_block;
            }
        } else {
            consecutive_blocks = 0;
        }
    }

    return -1;  // No contiguous space large enough was found
}

Best Fit Algorithm

// Implementation of the best fit algorithm
int best_fit_allocate(int file_size, int block_size) {
    int blocks_needed = (file_size + block_size - 1) / block_size;
    int best_start = -1;
    int best_size = INT_MAX;
    int current_start = -1;
    int current_size = 0;

    for (int i = 0; i < TOTAL_BLOCKS; i++) {
        if (is_block_free(i)) {
            if (current_start == -1) {
                current_start = i;
            }
            current_size++;
        } else {
            if (current_size >= blocks_needed && current_size < best_size) {
                best_start = current_start;
                best_size = current_size;
            }
            current_start = -1;
            current_size = 0;
        }
    }

    if (best_start != -1) {
        mark_blocks_used(best_start, blocks_needed);
        return best_start;
    }

    return -1;
}

Worst Fit Algorithm

// Implementation of the worst fit algorithm
int worst_fit_allocate(int file_size, int block_size) {
    int blocks_needed = (file_size + block_size - 1) / block_size;
    int worst_start = -1;
    int worst_size = 0;
    int current_start = -1;
    int current_size = 0;

    for (int i = 0; i < TOTAL_BLOCKS; i++) {
        if (is_block_free(i)) {
            if (current_start == -1) {
                current_start = i;
            }
            current_size++;
        } else {
            if (current_size >= blocks_needed && current_size > worst_size) {
                worst_start = current_start;
                worst_size = current_size;
            }
            current_start = -1;
            current_size = 0;
        }
    }

    if (worst_start != -1) {
        mark_blocks_used(worst_start, blocks_needed);
        return worst_start;
    }

    return -1;
}

Strengths and Weaknesses

Advantages

• Fast sequential access: the file’s data is stored consecutively, so sequential reads are efficient
• Simple to implement: the allocation and deallocation algorithms are straightforward
• Fast random access: the address of any position can be computed directly

Disadvantages

• External fragmentation: deleting a file leaves behind small pieces of space that are hard to reuse
• Preallocation problem: the file size has to be known in advance
• Hard to extend: growing a file means reallocating its space

Where It Fits

• Systems where file sizes are relatively fixed
• Workloads dominated by sequential access
• Environments with plenty of free storage space

Linked Allocation

Linked allocation organizes a file’s data as a linked list: every data block holds a pointer to the next block.

Basic Idea

// Data block structure for linked allocation
struct linked_block {
    char data[BLOCK_SIZE - 4];  // the data part
    int next_block;             // pointer to the next block
    int is_last;                // whether this is the last block
};

// The file control block
struct linked_file {
    int first_block;    // the first data block
    int last_block;     // the last data block
    int file_size;      // file size
    char filename[256]; // file name
};

Implementing the Allocation

// Creating a file with linked allocation
int create_linked_file(const char* filename, int file_size) {
    int blocks_needed = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    int first_block = -1;
    int current_block = -1;
    int prev_block = -1;

    // Allocate the first block
    first_block = allocate_free_block();
    if (first_block == -1) return -1;

    current_block = first_block;

    // Allocate the blocks that follow
    for (int i = 1; i < blocks_needed; i++) {
        int next_block = allocate_free_block();
        if (next_block == -1) {
            // Allocation failed, release the blocks already taken
            free_linked_blocks(first_block);
            return -1;
        }

        // Point the previous block forward
        set_next_block(current_block, next_block);
        prev_block = current_block;
        current_block = next_block;
    }

    // Mark the last block
    set_next_block(current_block, -1);
    set_last_block_flag(current_block, 1);

    // Create the file control block
    struct linked_file* file = create_file_control_block(filename, first_block, current_block, file_size);

    return file->file_id;
}

Accessing a File

// Reading a file with linked allocation
int read_linked_file(int file_id, char* buffer, int offset, int size) {
    struct linked_file* file = get_file_control_block(file_id);
    if (file == NULL) return -1;

    int current_block = file->first_block;
    int bytes_read = 0;
    int current_offset = 0;

    // Walk forward to the starting block
    while (current_offset < offset && current_block != -1) {
        current_block = get_next_block(current_block);
        current_offset += BLOCK_SIZE;
    }

    // Read the data
    while (bytes_read < size && current_block != -1) {
        int bytes_to_read = min(BLOCK_SIZE, size - bytes_read);
        int block_offset = (offset + bytes_read) % BLOCK_SIZE;

        read_block_data(current_block, buffer + bytes_read, block_offset, bytes_to_read);

        bytes_read += bytes_to_read;
        current_block = get_next_block(current_block);
    }

    return bytes_read;
}

Strengths and Weaknesses

Advantages

• No external fragmentation: every block can be allocated on its own
• Dynamic growth: a file can grow at run time
• High space utilization: every free block can be put to use

Disadvantages

• Slow random access: reaching a given position means walking the whole list
• Poor reliability: a single damaged block affects the entire file
• Space overhead: every block has to carry pointer information

Variant: The File Allocation Table (FAT)

The FAT is a refinement of linked allocation that collects all of the pointer information in a single file allocation table.

// Structure of the FAT
struct fat_entry {
    int next_block;     // the next block number
    int is_free;        // whether the cluster is free
    int is_bad;         // whether the cluster is bad
    int is_eof;         // whether this is the end of the file
};

struct fat_file_system {
    struct fat_entry fat_table[MAX_BLOCKS];
    int root_directory_start;
    int free_block_count;
};

Indexed Allocation

Indexed allocation gives every file an index block that stores the addresses of all of the file’s data blocks.

Basic Idea

// Data structures for indexed allocation
struct index_block {
    int block_addresses[MAX_BLOCKS_PER_INDEX];  // data block addresses
    int block_count;                            // number of blocks
    int next_index_block;                       // the next index block
};

struct indexed_file {
    int index_block;    // the index block number
    int file_size;      // file size
    char filename[256]; // file name
};

Single-Level Index

// Single-level indexed allocation
int create_indexed_file(const char* filename, int file_size) {
    int blocks_needed = (file_size + BLOCK_SIZE - 1) / BLOCK_SIZE;

    // Allocate the index block
    int index_block = allocate_free_block();
    if (index_block == -1) return -1;

    struct index_block* index = get_index_block(index_block);
    index->block_count = 0;
    index->next_index_block = -1;

    // Allocate the data blocks
    for (int i = 0; i < blocks_needed; i++) {
        int data_block = allocate_free_block();
        if (data_block == -1) {
            // Allocation failed, release the blocks already taken
            free_indexed_blocks(index_block);
            return -1;
        }

        index->block_addresses[i] = data_block;
        index->block_count++;
    }

    // Create the file control block
    struct indexed_file* file = create_indexed_file_control_block(filename, index_block, file_size);

    return file->file_id;
}

Multi-Level Index

// Structure of a multi-level index
struct multi_level_index {
    int primary_index;      // the primary index block
    int secondary_indexes[MAX_SECONDARY_INDEXES];  // secondary index blocks
    int secondary_count;    // number of secondary index blocks
    int tertiary_indexes[MAX_TERTIARY_INDEXES];    // tertiary index blocks
    int tertiary_count;     // number of tertiary index blocks
};

// Accessing a file with a multi-level index
int read_multi_level_file(int file_id, char* buffer, int offset, int size) {
    struct indexed_file* file = get_indexed_file_control_block(file_id);
    if (file == NULL) return -1;

    struct multi_level_index* index = get_multi_level_index(file->index_block);
    int bytes_read = 0;
    int current_offset = offset;

    while (bytes_read < size && current_offset < file->file_size) {
        int block_number = current_offset / BLOCK_SIZE;
        int data_block = get_data_block_address(index, block_number);

        if (data_block == -1) break;

        int bytes_to_read = min(BLOCK_SIZE, size - bytes_read);
        int block_offset = current_offset % BLOCK_SIZE;

        read_block_data(data_block, buffer + bytes_read, block_offset, bytes_to_read);

        bytes_read += bytes_to_read;
        current_offset += bytes_to_read;
    }

    return bytes_read;
}

Strengths and Weaknesses

Advantages

• Fast random access: the index leads straight to any block
• No external fragmentation: blocks are allocated dynamically
• Supports large files: a multi-level index can describe very large files

Disadvantages

• Space overhead: the index blocks take up space of their own
• Complex implementation: a multi-level index is fairly involved to build
• Index block limits: a single-level index can only address so many blocks

Hybrid Allocation

The Unix inode Structure

Unix systems use a hybrid method that combines direct blocks, indirect blocks, and multi-level indirect blocks.

// The Unix inode structure
struct inode {
    int file_size;
    int direct_blocks[12];     // direct blocks
    int single_indirect;       // single indirect block
    int double_indirect;       // double indirect block
    int triple_indirect;       // triple indirect block
    int link_count;
    int access_time;
    int modify_time;
    int create_time;
};

// Computing the address of a file block
int get_block_address(struct inode* inode, int block_number) {
    if (block_number < 12) {
        // Direct block
        return inode->direct_blocks[block_number];
    } else if (block_number < 12 + BLOCKS_PER_INDEX) {
        // Single indirect block
        int index_block = inode->single_indirect;
        int offset = block_number - 12;
        return get_index_block_entry(index_block, offset);
    } else if (block_number < 12 + BLOCKS_PER_INDEX + BLOCKS_PER_INDEX * BLOCKS_PER_INDEX) {
        // Double indirect block
        int index_block = inode->double_indirect;
        int offset = block_number - 12 - BLOCKS_PER_INDEX;
        int secondary_index = get_index_block_entry(index_block, offset / BLOCKS_PER_INDEX);
        return get_index_block_entry(secondary_index, offset % BLOCKS_PER_INDEX);
    } else {
        // Triple indirect block
        // Handled in the same way as the double indirect case
        return -1;
    }
}

Performance Analysis

// Comparing the performance of the different allocation methods
struct allocation_performance {
    char method[32];
    int sequential_read_speed;    // sequential read speed
    int random_read_speed;        // random read speed
    int space_efficiency;         // space efficiency
    int implementation_complexity; // implementation complexity
};

struct allocation_performance performance_table[] = {
    {"Contiguous", 100, 100, 70, 10},
    {"Linked", 60, 20, 95, 30},
    {"Indexed", 80, 90, 85, 60},
    {"Hybrid", 90, 85, 90, 80}
};

---

Glossary