Operating System Project Ideas

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

#ifndef FS_LAYOUT_H
#define FS_LAYOUT_H
 
#include <stdint.h>
 
#define BLOCK_SIZE 4096
#define MAGIC_NUMBER 0xDEADBEEF
 
#define MAX_FILENAME 255
#define MAX_FILE_SIZE (12 + 1024 + 1024*1024) * BLOCK_SIZE
 
// Superblock - block 0
typedef struct {
    uint32_t magic;              // Magic number to identify filesystem
    uint32_t block_size;         // Block size in bytes
    uint32_t total_blocks;       // Total blocks on disk
    uint32_t inode_count;        // Total number of inodes
    uint32_t free_blocks;        // Number of free data blocks
    uint32_t free_inodes;        // Number of free inodes
    uint32_t inode_bitmap_start; // Block number of inode bitmap
    uint32_t data_bitmap_start;  // Block number of data bitmap
    uint32_t inode_table_start;  // Block number of inode table start
    uint32_t data_blocks_start;  // Block number of first data block
    uint32_t root_inode;         // Inode number of root directory
    uint8_t  padding[4048];      // Pad to BLOCK_SIZE
} Superblock;
 
// Inode structure - 128 bytes each, 32 per block
#define INODES_PER_BLOCK (BLOCK_SIZE / sizeof(Inode))
 
typedef struct {
    uint32_t mode;               // File type and permissions
    uint32_t uid;                // Owner user ID
    uint32_t gid;                // Owner group ID
    uint32_t size;               // File size in bytes
    uint32_t atime;              // Last access time
    uint32_t mtime;              // Last modification time
    uint32_t ctime;              // Creation time
    uint32_t link_count;         // Number of hard links
    uint32_t blocks;             // Number of blocks allocated
 
    // Block pointers
    uint32_t direct[12];         // 12 direct block pointers
    uint32_t indirect;           // Single indirect block
    uint32_t double_indirect;    // Double indirect block
 
    uint8_t  padding[28];        // Pad to 128 bytes
} Inode;
 
// Directory entry - variable length, but we use fixed for simplicity
typedef struct {
    uint32_t inode;              // Inode number (0 = unused entry)
    uint16_t rec_len;            // Record length
    uint8_t  name_len;           // Filename length
    uint8_t  file_type;          // Type: file, directory, symlink
    char     name[MAX_FILENAME + 1];
} DirEntry;
 
// File types
#define FT_UNKNOWN  0
#define FT_REG_FILE 1
#define FT_DIR      2
#define FT_SYMLINK  7
 
#endif

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

#include <string.h>
#include "fs_layout.h"
 
// Disk I/O functions (implemented elsewhere)
extern int disk_read(uint32_t block_num, void *buf);
extern int disk_write(uint32_t block_num, const void *buf);
 
static Superblock sb;  // Cached superblock
 
/**
 * Allocate a free data block.
 * Returns block number, or -1 if disk is full.
 */
int alloc_block(void) {
    uint8_t bitmap[BLOCK_SIZE];
    uint32_t bitmap_blocks = (sb.total_blocks - sb.data_blocks_start + 7) / 8 / BLOCK_SIZE + 1;
 
    for (uint32_t bm_block = 0; bm_block < bitmap_blocks; bm_block++) {
        disk_read(sb.data_bitmap_start + bm_block, bitmap);
 
        for (int byte = 0; byte < BLOCK_SIZE; byte++) {
            if (bitmap[byte] != 0xFF) {  // Has free bit
                for (int bit = 0; bit < 8; bit++) {
                    if (!(bitmap[byte] & (1 << bit))) {
                        // Found free block
                        bitmap[byte] |= (1 << bit);
                        disk_write(sb.data_bitmap_start + bm_block, bitmap);
 
                        // Update superblock
                        sb.free_blocks--;
                        disk_write(0, &sb);
 
                        uint32_t block_num = bm_block * BLOCK_SIZE * 8 + 
                                            byte * 8 + bit + sb.data_blocks_start;
                        return block_num;
                    }
                }
            }
        }
    }
    return -1;  // Disk full
}
 
/**
 * Free a data block.
 */
void free_block(uint32_t block_num) {
    if (block_num < sb.data_blocks_start) return;
 
    uint32_t relative = block_num - sb.data_blocks_start;
    uint32_t bm_block = relative / (BLOCK_SIZE * 8);
    uint32_t byte = (relative % (BLOCK_SIZE * 8)) / 8;
    uint32_t bit = relative % 8;
 
    uint8_t bitmap[BLOCK_SIZE];
    disk_read(sb.data_bitmap_start + bm_block, bitmap);
 
    bitmap[byte] &= ~(1 << bit);  // Clear bit
    disk_write(sb.data_bitmap_start + bm_block, bitmap);
 
    sb.free_blocks++;
    disk_write(0, &sb);
}
 
/**
 * Allocate a free inode.
 * Returns inode number, or -1 if none available.
 */
int alloc_inode(void) {
    uint8_t bitmap[BLOCK_SIZE];
    disk_read(sb.inode_bitmap_start, bitmap);
 
    for (int byte = 0; byte < BLOCK_SIZE; byte++) {
        if (bitmap[byte] != 0xFF) {
            for (int bit = 0; bit < 8; bit++) {
                if (!(bitmap[byte] & (1 << bit))) {
                    bitmap[byte] |= (1 << bit);
                    disk_write(sb.inode_bitmap_start, bitmap);
 
                    sb.free_inodes--;
                    disk_write(0, &sb);
 
                    return byte * 8 + bit;
                }
            }
        }
    }
    return -1;
}

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

#include "fs_layout.h"
 
#define PTRS_PER_BLOCK (BLOCK_SIZE / sizeof(uint32_t))
 
/**
 * Read an inode from disk.
 */
int read_inode(uint32_t inum, Inode *inode) {
    uint32_t block = sb.inode_table_start + inum / INODES_PER_BLOCK;
    uint32_t offset = (inum % INODES_PER_BLOCK) * sizeof(Inode);
 
    uint8_t buf[BLOCK_SIZE];
    disk_read(block, buf);
    memcpy(inode, buf + offset, sizeof(Inode));
    return 0;
}
 
/**
 * Write an inode to disk.
 */
int write_inode(uint32_t inum, const Inode *inode) {
    uint32_t block = sb.inode_table_start + inum / INODES_PER_BLOCK;
    uint32_t offset = (inum % INODES_PER_BLOCK) * sizeof(Inode);
 
    uint8_t buf[BLOCK_SIZE];
    disk_read(block, buf);
    memcpy(buf + offset, inode, sizeof(Inode));
    disk_write(block, buf);
    return 0;
}
 
/**
 * Get the data block number for a given file offset.
 * Handles direct, indirect, and double indirect blocks.
 */
uint32_t get_block_num(const Inode *inode, uint32_t file_block) {
    uint32_t ptrs[PTRS_PER_BLOCK];
 
    // Direct blocks (0-11)
    if (file_block < 12) {
        return inode->direct[file_block];
    }
    file_block -= 12;
 
    // Single indirect (12 to 12+1023)
    if (file_block < PTRS_PER_BLOCK) {
        if (inode->indirect == 0) return 0;
        disk_read(inode->indirect, ptrs);
        return ptrs[file_block];
    }
    file_block -= PTRS_PER_BLOCK;
 
    // Double indirect
    if (file_block < PTRS_PER_BLOCK * PTRS_PER_BLOCK) {
        if (inode->double_indirect == 0) return 0;
        disk_read(inode->double_indirect, ptrs);
 
        uint32_t idx1 = file_block / PTRS_PER_BLOCK;
        uint32_t idx2 = file_block % PTRS_PER_BLOCK;
 
        if (ptrs[idx1] == 0) return 0;
        disk_read(ptrs[idx1], ptrs);
        return ptrs[idx2];
    }
 
    return 0;  // File too large
}
 
/**
 * Read data from a file.
 */
int fs_read(uint32_t inum, void *buf, size_t size, off_t offset) {
    Inode inode;
    read_inode(inum, &inode);
 
    if (offset >= inode.size) return 0;
    if (offset + size > inode.size) {
        size = inode.size - offset;
    }
 
    size_t bytes_read = 0;
    uint8_t block_buf[BLOCK_SIZE];
 
    while (bytes_read < size) {
        uint32_t file_block = (offset + bytes_read) / BLOCK_SIZE;
        uint32_t block_offset = (offset + bytes_read) % BLOCK_SIZE;
        uint32_t to_read = BLOCK_SIZE - block_offset;
        if (to_read > size - bytes_read) {
            to_read = size - bytes_read;
        }
 
        uint32_t block_num = get_block_num(&inode, file_block);
        if (block_num == 0) {
            memset((char *)buf + bytes_read, 0, to_read);
        } else {
            disk_read(block_num, block_buf);
            memcpy((char *)buf + bytes_read, block_buf + block_offset, to_read);
        }
 
        bytes_read += to_read;
    }
 
    return bytes_read;
}

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

#include <string.h>
#include "fs_layout.h"
 
/**
 * Look up a name in a directory.
 * Returns inode number, or -1 if not found.
 */
int dir_lookup(uint32_t dir_inum, const char *name) {
    Inode dir_inode;
    read_inode(dir_inum, &dir_inode);
 
    if (!(dir_inode.mode & S_IFDIR)) {
        return -1;  // Not a directory
    }
 
    uint8_t buf[BLOCK_SIZE];
    uint32_t offset = 0;
 
    while (offset < dir_inode.size) {
        uint32_t block = offset / BLOCK_SIZE;
        uint32_t block_num = get_block_num(&dir_inode, block);
        if (block_num == 0) break;
 
        disk_read(block_num, buf);
 
        DirEntry *entry = (DirEntry *)(buf + (offset % BLOCK_SIZE));
        while ((uint8_t *)entry < buf + BLOCK_SIZE) {
            if (entry->inode != 0 && 
                entry->name_len == strlen(name) &&
                strncmp(entry->name, name, entry->name_len) == 0) {
                return entry->inode;
            }
 
            if (entry->rec_len == 0) break;
            entry = (DirEntry *)((char *)entry + entry->rec_len);
        }
 
        offset += BLOCK_SIZE;
    }
 
    return -1;  // Not found
}
 
/**
 * Resolve a path to an inode number.
 * Path must be absolute (start with /).
 */
int path_lookup(const char *path) {
    if (path[0] != '/') return -1;
 
    uint32_t inum = sb.root_inode;
    char path_copy[256];
    strncpy(path_copy, path + 1, sizeof(path_copy));
 
    char *component = strtok(path_copy, "/");
    while (component != NULL) {
        inum = dir_lookup(inum, component);
        if (inum < 0) return -1;
 
        component = strtok(NULL, "/");
    }
 
    return inum;
}
 
/**
 * Add a directory entry.
 */
int dir_add_entry(uint32_t dir_inum, const char *name, 
                  uint32_t new_inum, uint8_t file_type) {
    Inode dir_inode;
    read_inode(dir_inum, &dir_inode);
 
    // Calculate entry size (align to 4 bytes)
    size_t name_len = strlen(name);
    size_t entry_size = sizeof(DirEntry) - MAX_FILENAME - 1 + name_len;
    entry_size = (entry_size + 3) & ~3;
 
    // Find space or allocate new block
    // ... (scan existing entries for gap, or extend directory)
 
    DirEntry new_entry;
    new_entry.inode = new_inum;
    new_entry.rec_len = entry_size;
    new_entry.name_len = name_len;
    new_entry.file_type = file_type;
    strncpy(new_entry.name, name, name_len);
 
    // Write entry to directory
    // ... (implementation details)
 
    return 0;
}