File System Exercises

Approach

Group the functions by the stage of a file’s life they serve: the space a file occupies, the name it is known by, the rights it carries, and the guarantee that it survives a crash.

Steps

1. Ask how the file system decides where a file’s bytes go on disk.
2. Ask how a user refers to the file and how the system keeps its metadata.
3. Ask how the system keeps unauthorized users out.
4. Ask what happens to the data when the machine dies unexpectedly.

Answer

The main functions of a file system are:

1. Space management: allocate and reclaim storage space, manage the free space, and deal with storage fragmentation
2. File organization and naming: provide a naming mechanism, organize files into a hierarchical structure, and maintain file metadata
3. File access control: provide the read and write interfaces for files, enforce access permissions, and ensure the security of the files
4. Data persistence: make sure data is stored durably, provide backup and recovery facilities, and keep the data consistent when the system crashes

Approach

Start from the purpose of attributes in general — they are the metadata the file system keeps about every file — and then list the attributes that the operating system itself relies on.

Steps

1. Explain what the attributes are and why the file system records them.
2. Pick the attributes the system uses to find, size, and protect a file.
3. Add the attributes that record the history of the file.

Answer

What file attributes are for:

• They give a complete description of a file
• They support file management and access control
• They let the file system optimize its behaviour and improve performance

Important file attributes:

1. File name: the identifier a user recognizes and uses to reach the file
2. File size: the number of data bytes the file contains
3. File type: regular file, directory, device file, and so on
4. Creation time: the timestamp of when the file was first created
5. Modification time: the time the contents of the file were last changed
6. Access time: the time the file was last accessed
7. Owner: the creator or the current owner of the file
8. Permissions: the read, write, and execute rights that are set

Approach

Compare the three structures along the same three axes: how easy it is to find a file, how easy it is to give files unique names, and how well the structure supports sharing and protection.

Steps

1. Describe the single-level directory, where every file sits directly in one flat namespace.
2. Describe the two-level directory, where each user has a own directory.
3. Describe the tree directory, where directories can contain other directories.
4. Fill in the table for each structure.

Answer

Approach

Split the path into components and walk the directory tree one component at a time, starting at the root. Every step checks that the current node really is a directory before looking up the next component.

Steps

1. Reject the path if it does not start with /, since only absolute paths are handled here.
2. Start from the root directory.
3. For each component separated by /, look up the matching child of the current directory.
4. Fail if the current node is not a directory, or if no child matches the component.
5. The node reached after the last component is the answer.

Answer

struct directory_node* resolve_path(const char* path) {
    if (path[0] != '/') return NULL;  // must be an absolute path

    struct directory_node* current = root_directory;
    char* path_copy = strdup(path);
    char* token = strtok(path_copy, "/");

    while (token != NULL) {
        if (current->type != DIRECTORY) {
            free(path_copy);
            return NULL;  // the current node is not a directory
        }

        struct directory_node* next = find_child(current, token);
        if (next == NULL) {
            free(path_copy);
            return NULL;  // no matching component was found
        }

        current = next;
        token = strtok(NULL, "/");
    }

    free(path_copy);
    return current;
}

Time complexity: O(n), where n is the number of components in the path.

Approach

Scan the blocks in address order and keep a counter of how many free blocks have been seen in a row. As soon as the run is long enough for the file, claim it and return its first block.

Steps

1. Work out how many blocks the file needs, rounding the size up.
2. Scan the blocks from the lowest address upwards.
3. Extend the current run whenever the block is free, and reset the run whenever it is not.
4. Remember the address of the first block of the run.
5. Mark the blocks as used and return the starting block; return -1 if no run was long enough.

Answer

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
}

Approach

Compare the three methods along the same four axes: how fast sequential access is, how fast random access is, what happens to space utilization, and how hard the method is to implement.

Steps

1. Consider what happens when the file is read from the beginning to the end.
2. Consider what happens when a single byte in the middle of the file is needed.
3. Consider how the blocks are handed out and how fragments appear over time.
4. Consider how much extra bookkeeping the method needs.

Answer

Contiguous allocation:

• Advantages: fast sequential access, simple to implement, fast random access
• Disadvantages: external fragmentation, the preallocation problem, hard to extend

Linked allocation:

• Advantages: no external fragmentation, dynamic growth, high space utilization
• Disadvantages: slow random access, poor reliability, space overhead

Indexed allocation:

• Advantages: fast random access, no external fragmentation, supports large files
• Disadvantages: space overhead, complex implementation, index block limits

Approach

Resolve the request against the three classes of user in turn: the owner, the members of the owning group, and everyone else. The first class that matches decides the answer.

Steps

1. Load the DAC record of the file and the record of the requesting user; deny the request if either is missing.
2. If the user is the owner, consult the owner permission bits.
3. Otherwise, if the user belongs to the owning group, consult the group permission bits.
4. Otherwise, consult the permission bits for other users.
5. Return 0 for any operation that is not read, write, or execute.

Answer

int check_dac_permission(const char* file_path, int user_id, int operation) {
    struct file_dac* dac = get_file_dac(file_path);
    if (dac == NULL) return 0;

    // Look up the user
    struct user_info* user = get_user_info(user_id);
    if (user == NULL) return 0;

    // Check whether the user is the owner
    if (user_id == dac->owner_id) {
        switch (operation) {
            case READ_OP:
                return dac->permissions.owner_read;
            case WRITE_OP:
                return dac->permissions.owner_write;
            case EXECUTE_OP:
                return dac->permissions.owner_execute;
            default:
                return 0;
        }
    }

    // Check whether the user belongs to the group
    if (is_user_in_group(user_id, dac->group_id)) {
        switch (operation) {
            case READ_OP:
                return dac->permissions.group_read;
            case WRITE_OP:
                return dac->permissions.group_write;
            case EXECUTE_OP:
                return dac->permissions.group_execute;
            default:
                return 0;
        }
    }

    // Permissions for everyone else
    switch (operation) {
        case READ_OP:
            return dac->permissions.other_read;
        case WRITE_OP:
            return dac->permissions.other_write;
        case EXECUTE_OP:
            return dac->permissions.other_execute;
        default:
            return 0;
    }
}

Approach

Derive an encryption key from the password, encrypt the file contents with a random initialization vector, and store the information needed to decrypt the file again alongside it.

Steps

1. Derive a key of the required length from the password.
2. Generate a fresh initialization vector so that the same plaintext never encrypts to the same ciphertext.
3. Read the contents of the file into memory.
4. Encrypt the contents with AES-256.
5. Record the algorithm, the key hash, the key length, and the initialization vector, and write the encrypted file out.

Answer

int encrypt_file(const char* file_path, const char* password) {
    // Generate the key
    unsigned char key[32];
    generate_key_from_password(password, key, 32);

    // Generate the initialization vector
    unsigned char iv[16];
    generate_random_iv(iv, 16);

    // Read the contents of the file
    char* file_content = read_file_content(file_path);
    int content_length = strlen(file_content);

    // Encrypt the contents of the file
    char* encrypted_content = malloc(content_length + 16);
    int encrypted_length = encrypt_aes256(file_content, content_length, key, iv, encrypted_content);

    // Store the encryption information
    struct file_encryption* enc_info = malloc(sizeof(struct file_encryption));
    enc_info->algorithm = AES256;
    hash_key(key, 32, enc_info->key_hash);
    enc_info->key_length = 32;
    memcpy(enc_info->iv, iv, 16);

    // Write the encrypted file
    write_encrypted_file(file_path, encrypted_content, encrypted_length, enc_info);

    free(file_content);
    free(encrypted_content);
    free(enc_info);

    return 0;
}

Approach

Walk through the four regions of the volume in the order they appear on disk, then weigh the simplicity of that layout against the performance it costs.

Steps

1. Identify the four regions of the volume.
2. For each region, state what it is used for.
3. List the advantages that follow from the simple layout.
4. List the disadvantages that follow from the fixed cluster size and the flat chain structure.

Answer

The structure of the FAT file system:

• Boot sector: holds the basic information about the file system
• FAT table: stores the file allocation information
• Root directory: stores the file and directory entries
• Data area: stores the actual file data

Advantages:

• Simplicity: the structure is simple and easy to understand and implement
• Compatibility: almost every operating system supports it
• Lightweight: little system overhead, which suits embedded systems

Disadvantages:

• Performance limits: large files are accessed inefficiently
• Wasted space: the cluster size is fixed, so small files waste space
• Fragmentation: file fragmentation appears easily
• Limited features: it does not support advanced features

Approach

Take each feature in turn and split it into what it is for and how NTFS implements it, so the answer shows both the purpose and the mechanism.

Steps

1. Start with the feature that keeps the file system consistent after a crash.
2. Move on to the features that save space and protect data.
3. Finish with the features that control who may do what.

Answer

Advanced features of NTFS:

1. Journaling:
   • Purpose: guarantees data consistency and enables fast recovery
   • Implementation: file system operations are recorded in a log file
2. Compression:
   • Purpose: saves storage space
   • Implementation: file data is compressed transparently
3. Encryption:
   • Purpose: protects the file against unauthorized reading
   • Implementation: EFS (Encrypting File System)
4. Permission control:
   • Purpose: provides fine-grained access control
   • Implementation: ACL (Access Control List)
5. Disk quotas:
   • Purpose: limits how much storage a user may consume
   • Implementation: the usage of each user’s files is tracked

Approach

Build the system out of three parts — a superblock that describes the volume, an inode table that describes the files, and the data blocks themselves — and then implement file creation and file reading on top of them.

Steps

1. Lay out the three parts of the file system.
2. To create a file, allocate an inode and then the data blocks it needs, and roll back if either allocation fails.
3. Fill in the inode with the name, the size, and the list of block numbers.
4. To read a file, work out which blocks the requested range of bytes falls in and copy them out.
5. Remember to clamp the read to the size of the file.

Answer

// The file system structure
struct simple_fs {
    struct super_block super;      // the superblock
    struct inode* inode_table;     // the inode table
    char* data_blocks;            // the data blocks
    int free_blocks_count;        // the number of free blocks
};

// The file operation functions
int fs_create_file(const char* name, int size) {
    // 1. Allocate an inode
    int inode_num = allocate_inode();
    if (inode_num == -1) return -1;

    // 2. Allocate the data blocks
    int blocks_needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE;
    int* block_numbers = allocate_blocks(blocks_needed);
    if (block_numbers == NULL) {
        free_inode(inode_num);
        return -1;
    }

    // 3. Initialize the inode
    struct inode* inode = &fs.inode_table[inode_num];
    strcpy(inode->name, name);
    inode->size = size;
    inode->block_count = blocks_needed;
    memcpy(inode->block_numbers, block_numbers, blocks_needed * sizeof(int));

    free(block_numbers);
    return inode_num;
}

int fs_read_file(int inode_num, char* buffer, int offset, int size) {
    struct inode* inode = &fs.inode_table[inode_num];
    if (offset >= inode->size) return 0;
    if (offset + size > inode->size) {
        size = inode->size - offset;
    }

    int start_block = offset / BLOCK_SIZE;
    int end_block = (offset + size - 1) / BLOCK_SIZE;
    int bytes_read = 0;

    for (int block = start_block; block <= end_block; block++) {
        int block_number = inode->block_numbers[block];
        int block_offset = (block == start_block) ? (offset % BLOCK_SIZE) : 0;
        int bytes_to_read = min(BLOCK_SIZE - block_offset, size - bytes_read);

        memcpy(buffer + bytes_read,
               fs.data_blocks + block_number * BLOCK_SIZE + block_offset,
               bytes_to_read);
        bytes_read += bytes_to_read;
    }

    return bytes_read;
}

Approach

Treat optimization as a trade-off: every technique buys speed or capacity at the price of something else, and the analysis should name that price.

Steps

1. Start with the techniques that cut the number of disk accesses.
2. Move on to the techniques that make the accesses themselves cheaper.
3. Finish with the techniques that change how the data is laid out, and note what each one costs.

Answer

Ways to optimize file system performance:

1. Buffering:
   • Method: use an in-memory cache to cut down on disk I/O
   • Effect: markedly improves read performance
2. Read-ahead:
   • Method: predictively read the data that follows
   • Effect: improves sequential access performance
3. Write buffering:
   • Method: delay the writes and process them in batches
   • Effect: improves write performance, but may affect consistency
4. Index optimization:
   • Method: use an efficient index structure such as a B-tree
   • Effect: improves random access performance
5. Compression:
   • Method: compress file data transparently
   • Effect: saves storage space, but may affect I/O performance
6. RAID technology:
   • Method: access several disks in parallel
   • Effect: raises I/O throughput