Indexed Allocation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/* Simplified index block structure for a file system */
 
#define BLOCK_SIZE          4096    /* 4KB blocks */
#define POINTER_SIZE        8       /* 64-bit pointers */
#define POINTERS_PER_BLOCK  (BLOCK_SIZE / POINTER_SIZE)  /* 512 pointers */
 
typedef uint64_t block_ptr_t;  /* Physical block address */
 
/*
 * Index Block Layout (Single-Level)
 * 
 * An index block is simply an array of block pointers.
 * Each pointer addresses one data block of the file.
 * 
 * Memory Layout:
 * +------------------+
 * | block_ptr[0]     |  → First 4KB of file data
 * +------------------+
 * | block_ptr[1]     |  → Second 4KB of file data
 * +------------------+
 * | block_ptr[2]     |  → Third 4KB of file data
 * +------------------+
 * |       ...        |
 * +------------------+
 * | block_ptr[511]   |  → 512th 4KB of file data
 * +------------------+
 */
struct index_block {
    block_ptr_t pointers[POINTERS_PER_BLOCK];
};
 
/* 
 * Maximum file size with single-level indexing:
 * 512 pointers × 4KB per block = 2MB
 * 
 * This is why real file systems use multi-level indexing!
 */
#define MAX_FILE_SIZE_SINGLE_LEVEL  (POINTERS_PER_BLOCK * BLOCK_SIZE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/*
 * Reading data from a file using indexed allocation
 * 
 * This demonstrates the O(1) random access property of
 * indexed allocation - we can jump directly to any block.
 */
 
struct file_descriptor {
    block_ptr_t     index_block_addr;   /* Location of index block */
    struct index_block *cached_index;    /* Cached in memory */
    uint64_t        file_size;           /* For bounds checking */
    uint64_t        current_position;    /* Current read/write position */
};
 
/*
 * Read 'count' bytes from file at the current position.
 * 
 * Time Complexity: O(blocks_read), NOT O(file_size)
 * This is the key advantage over linked allocation.
 */
ssize_t indexed_read(struct file_descriptor *fd, void *buffer, size_t count) {
    size_t bytes_read = 0;
    char *buf = (char *)buffer;
    
    /* Ensure index block is cached in memory */
    if (fd->cached_index == NULL) {
        fd->cached_index = read_block(fd->index_block_addr);
    }
    
    while (bytes_read < count && fd->current_position < fd->file_size) {
        /* Step 1: Calculate which logical block we need */
        uint64_t logical_block = fd->current_position / BLOCK_SIZE;
        uint64_t offset_in_block = fd->current_position % BLOCK_SIZE;
        
        /* Step 2: Direct lookup in index block - O(1) */
        block_ptr_t physical_block = fd->cached_index->pointers[logical_block];
        
        /* Step 3: Read the data block */
        char *data = read_block(physical_block);
        
        /* Step 4: Copy requested bytes */
        size_t bytes_available = BLOCK_SIZE - offset_in_block;
        size_t bytes_remaining = count - bytes_read;
        size_t bytes_to_copy = MIN(bytes_available, bytes_remaining);
        
        memcpy(buf + bytes_read, data + offset_in_block, bytes_to_copy);
        
        bytes_read += bytes_to_copy;
        fd->current_position += bytes_to_copy;
        
        free(data);  /* Release temporary buffer */
    }
    
    return bytes_read;
}
 
/*
 * Seek to a specific position - O(1) operation!
 * 
 * Unlike linked allocation where seeking requires traversal,
 * indexed allocation allows instant positioning.
 */
int indexed_seek(struct file_descriptor *fd, uint64_t position) {
    if (position > fd->file_size) {
        return -1;  /* Beyond end of file */
    }
    
    /* No disk I/O required - just update the position */
    fd->current_position = position;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/*
 * Directory Entry Structure
 * 
 * Directories are special files that contain mappings from
 * file names to index block addresses (inode numbers in Unix).
 */
 
#define MAX_FILENAME_LENGTH 255
 
struct directory_entry {
    char            filename[MAX_FILENAME_LENGTH + 1];
    uint64_t        index_block_number;  /* Also called inode number */
    uint8_t         entry_type;          /* File, directory, symlink, etc. */
    uint8_t         padding[6];          /* Alignment padding */
};
 
/*
 * Opening a file: The journey from path to index block
 */
struct index_block* path_to_index_block(const char *path) {
    /* Start at root directory's index block */
    struct index_block *current_dir_index = get_root_index_block();
    
    char *path_copy = strdup(path);
    char *component = strtok(path_copy, "/");
    
    while (component != NULL) {
        /* Search directory for this component */
        struct directory_entry *entry = search_directory(
            current_dir_index, 
            component
        );
        
        if (entry == NULL) {
            free(path_copy);
            return NULL;  /* File not found */
        }
        
        /* Load the index block for this component */
        current_dir_index = read_index_block(entry->index_block_number);
        
        component = strtok(NULL, "/");
    }
    
    free(path_copy);
    return current_dir_index;  /* Index block of the target file */
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

/*
 * Complete File Creation Example with Indexed Allocation
 * 
 * Scenario: User creates /home/user/report.txt and writes 10KB of data
 * Assumptions: 4KB block size, 512 pointers per index block
 */
 
/* Step 1: System call - create("report.txt", mode) */
int create_file_indexed(const char *path, mode_t mode) {
    
    /* Step 2: Allocate a new index block (inode) */
    uint64_t inode_num = allocate_inode();
    if (inode_num == 0) {
        return -ENOSPC;  /* No free inodes */
    }
    
    /* Step 3: Initialize the index block */
    struct inode *new_inode = get_inode(inode_num);
    new_inode->mode = mode;
    new_inode->size = 0;
    new_inode->link_count = 1;
    new_inode->uid = current_user();
    new_inode->gid = current_group();
    new_inode->atime = new_inode->mtime = new_inode->ctime = now();
    
    /* All block pointers initially NULL */
    for (int i = 0; i < POINTERS_PER_INODE; i++) {
        new_inode->direct_blocks[i] = 0;
    }
    new_inode->indirect_block = 0;
    new_inode->double_indirect = 0;
    
    /* Step 4: Add entry to parent directory */
    struct inode *parent_dir = get_parent_directory(path);
    const char *filename = get_filename(path);
    add_directory_entry(parent_dir, filename, inode_num);
    
    /* Step 5: Write the inode and directory to disk */
    write_inode(new_inode);
    write_inode(parent_dir);
    
    return open_file(inode_num);  /* Return file descriptor */
}
 
/* Step 6: User writes 10KB of data - write(fd, buffer, 10240) */
ssize_t write_file_indexed(struct file_descriptor *fd, 
                           const void *buffer, 
                           size_t count) {
    struct inode *inode = get_inode(fd->inode_num);
    const char *data = (const char *)buffer;
    size_t bytes_written = 0;
    
    while (bytes_written < count) {
        /* Calculate which logical block we're writing to */
        uint64_t logical_block = fd->position / BLOCK_SIZE;
        uint64_t offset_in_block = fd->position % BLOCK_SIZE;
        
        /* Allocate a data block if this logical block is empty */
        if (inode->direct_blocks[logical_block] == 0) {
            uint64_t new_block = allocate_data_block();
            if (new_block == 0) {
                break;  /* Disk full */
            }
            inode->direct_blocks[logical_block] = new_block;
        }
        
        /* Write data to the block */
        uint64_t physical_block = inode->direct_blocks[logical_block];
        size_t bytes_to_write = MIN(BLOCK_SIZE - offset_in_block, 
                                    count - bytes_written);
        
        write_partial_block(physical_block, 
                           offset_in_block, 
                           data + bytes_written, 
                           bytes_to_write);
        
        bytes_written += bytes_to_write;
        fd->position += bytes_to_write;
    }
    
    /* Update file size and timestamps */
    if (fd->position > inode->size) {
        inode->size = fd->position;
    }
    inode->mtime = now();
    write_inode(inode);
    
    return bytes_written;
}
 
/*
 * Disk State After Writing 10KB:
 * 
 * Inode (Index Block):
 * +------------------+
 * | mode, size=10240 |
 * | uid, gid         |
 * | timestamps       |
 * | direct[0] → 500  |  ← Block 500: bytes 0-4095
 * | direct[1] → 501  |  ← Block 501: bytes 4096-8191
 * | direct[2] → 502  |  ← Block 502: bytes 8192-10239
 * | direct[3-11] = 0 |  ← Unused
 * | indirect = 0     |
 * | double_ind = 0   |
 * +------------------+
 */