All operations related to files and directories involve manipulating inodes, as we need to know the storage location of files through inodes. Therefore, operating on files always means finding the corresponding inode. Next, we implement a set of functions for handling inodes, including: locating an enode on disk, initializing an inode, loading an inode into memory, synchronizing changes from memory to disk, and removing an inode from memory.

Functions Related to inode Operations

Since files and directories are essentially inodes, any operation on files and directories requires handling inodes. It's necesary to start with inodes.

/* Structure to store inode location */
struct inode_location {
    bool cross_sector;      // Whether the inode spans across sectors
    uint32_t sector_lba;    // Sector number where the inode is located
    uint32_t offset;        // Byte offset within the sector
};

/* Locate the sector and offset for a given inode number */
static void locate_inode(struct partition* part, uint32_t inode_no, struct inode_location* loc) {
    /* inode_table is contiguous on disk */
    ASSERT(inode_no < 4096);
    uint32_t inode_table_lba = part->sb->inode_table_lba;
    uint32_t inode_size = sizeof(struct inode);
    uint32_t byte_offset = inode_no * inode_size;
    uint32_t sector_offset = byte_offset / 512;
    uint32_t offset_in_sector = byte_offset % 512;
    uint32_t remaining_in_sector = 512 - offset_in_sector;
    if (remaining_in_sector < inode_size) {
        loc->cross_sector = true;
    } else {
        loc->cross_sector = false;
    }
    loc->sector_lba = inode_table_lba + sector_offset;
    loc->offset = offset_in_sector;
}

/* Write an inode to the partition */
void sync_inode(struct partition* part, struct inode* inode, void* io_buf) {
    uint8_t inode_no = inode->i_no;
    struct inode_location loc;
    locate_inode(part, inode_no, &loc);
    ASSERT(loc.sector_lba <= (part->start_lba + part->sec_cnt));
    struct inode disk_inode;
    memcpy(&disk_inode, inode, sizeof(struct inode));
    disk_inode.i_open_cnts = 0;
    disk_inode.write_deny = false;
    disk_inode.inode_tag.prev = disk_inode.inode_tag.next = NULL;
    char* buffer = (char*)io_buf;
    if (loc.cross_sector) {
        ide_read(part->my_disk, loc.sector_lba, buffer, 2);
        memcpy(buffer + loc.offset, &disk_inode, sizeof(struct inode));
        ide_write(part->my_disk, loc.sector_lba, buffer, 2);
    } else {
        ide_read(part->my_disk, loc.sector_lba, buffer, 1);
        memcpy(buffer + loc.offset, &disk_inode, sizeof(struct inode));
        ide_write(part->my_disk, loc.sector_lba, buffer, 1);
    }
}

/* Open an inode by its number */
struct inode* open_inode(struct partition* part, uint32_t inode_no) {
    struct list_elem* elem = part->open_inodes.head.next;
    struct inode* found_inode;
    while (elem != &part->open_inodes.tail) {
        found_inode = elem2entry(struct inode, inode_tag, elem);
        if (found_inode->i_no == inode_no) {
            found_inode->i_open_cnts++;
            return found_inode;
        }
        elem = elem->next;
    }
    struct inode_location loc;
    locate_inode(part, inode_no, &loc);
    struct task_struct* cur = running_thread();
    uint32_t* saved_pgdir = cur->pgdir;
    cur->pgdir = NULL;
    found_inode = (struct inode*)sys_malloc(sizeof(struct inode));
    cur->pgdir = saved_pgdir;
    char* buffer;
    if (loc.cross_sector) {
        buffer = (char*)sys_malloc(1024);
        ide_read(part->my_disk, loc.sector_lba, buffer, 2);
    } else {
        buffer = (char*)sys_malloc(512);
        ide_read(part->my_disk, loc.sector_lba, buffer, 1);
    }
    memcpy(found_inode, buffer + loc.offset, sizeof(struct inode));
    list_push(&part->open_inodes, &found_inode->inode_tag);
    found_inode->i_open_cnts = 1;
    sys_free(buffer);
    return found_inode;
}

/* Close an inode or decrement its open count */
void close_inode(struct inode* inode) {
    enum intr_status old_status = intr_disable();
    if (--inode->i_open_cnts == 0) {
        list_remove(&inode->inode_tag);
        struct task_struct* cur = running_thread();
        uint32_t* saved_pgdir = cur->pgdir;
        cur->pgdir = NULL;
        sys_free(inode);
        cur->pgdir = saved_pgdir;
    }
    intr_set_status(old_status);
}

/* Initialize a new inode */
void init_inode(uint32_t inode_no, struct inode* new_inode) {
    new_inode->i_no = inode_no;
    new_inode->i_size = 0;
    new_inode->i_open_cnts = 0;
    new_inode->write_deny = false;
    for (uint8_t i = 0; i < 13; i++) {
        new_inode->i_sectors[i] = 0;
    }
}

Description:

• locate_inode: Calculates the sector and offset for an inode based on its number.
• sync_inode: Writes an inode to disk by reading the corresponding sector, updating it, and writing back.
• open_inode: Opens an inode by checking an in-memory list first, then loading from disk if not found, ensuring shared access across processes.
• close_inode: Closes an inode, removing it from memory if no processses have it open.
• init_inode: Initializes a new inode with default values.

File-Related Functions

/* Get a free slot in the global file table */
int32_t get_free_slot(void) {
    uint32_t idx = 3;
    while (idx < MAX_FILE_OPEN) {
        if (file_table[idx].fd_inode == NULL) {
            break;
        }
        idx++;
    }
    if (idx == MAX_FILE_OPEN) {
        return -1;
    }
    return idx;
}

/* Install a global file descriptor into the process's file descriptor table */
int32_t install_fd(int32_t global_idx) {
    struct task_struct* cur = running_thread();
    uint8_t local_idx = 3;
    while (local_idx < MAX_FILES_OPEN_PER_PROC) {
        if (cur->fd_table[local_idx] == -1) {
            cur->fd_table[local_idx] = global_idx;
            break;
        }
        local_idx++;
    }
    if (local_idx == MAX_FILES_OPEN_PER_PROC) {
        return -1;
    }
    return local_idx;
}

/* Allocate an inode from the bitmap */
int32_t allocate_inode(struct partition* part) {
    int32_t bit_idx = bitmap_scan(&part->inode_bitmap, 1);
    if (bit_idx == -1) return -1;
    bitmap_set(&part->inode_bitmap, bit_idx, 1);
    return bit_idx;
}

/* Allocate a sector from the block bitmap */
int32_t allocate_block(struct partition* part) {
    int32_t bit_idx = bitmap_scan(&part->block_bitmap, 1);
    if (bit_idx == -1) return -1;
    bitmap_set(&part->block_bitmap, bit_idx, 1);
    return (part->sb->data_start_lba + bit_idx);
}

/* Synchronize a bitmap sector to disk */
void sync_bitmap(struct partition* part, uint32_t bit_idx, uint8_t bmp_type) {
    uint32_t sec_offset = bit_idx / 4096;
    uint32_t byte_offset = sec_offset * 512;
    uint32_t sec_lba;
    uint8_t* bmp_ptr;
    switch (bmp_type) {
        case INODE_BITMAP:
            sec_lba = part->sb->inode_bitmap_lba + sec_offset;
            bmp_ptr = part->inode_bitmap.bits + byte_offset;
            break;
        case BLOCK_BITMAP:
            sec_lba = part->sb->block_bitmap_lba + sec_offset;
            bmp_ptr = part->block_bitmap.bits + byte_offset;
            break;
    }
    ide_write(part->my_disk, sec_lba, bmp_ptr, 1);
}

Description:

• get_free_slot: Finds an empty entry in the global file table.
• install_fd: Maps a global file descriptor to a process's local descriptor table.
• allocate_inode: Allocates an inode by marking a bit in the inode bitmap.
• allocate_block: Allocates a sector by marking a bit in the block bitmap.
• sync_bitmap: Writes a bitmap sector to disk.

Directory-Related Functions

/* Open the root directory */
void open_root(struct partition* part) {
    root_dir.inode = open_inode(part, part->sb->root_inode_no);
    root_dir.dir_pos = 0;
}

/* Open a directory by its inode number */
struct dir* open_directory(struct partition* part, uint32_t inode_no) {
    struct dir* dir_ptr = (struct dir*)sys_malloc(sizeof(struct dir));
    dir_ptr->inode = open_inode(part, inode_no);
    dir_ptr->dir_pos = 0;
    return dir_ptr;
}

/* Search for a directory entry by name */
bool find_dir_entry(struct partition* part, struct dir* dir_ptr, const char* name, struct dir_entry* entry) {
    uint32_t block_count = 140;
    uint32_t* all_blocks = (uint32_t*)sys_malloc(48 + 512);
    if (all_blocks == NULL) return false;
    uint32_t idx = 0;
    while (idx < 12) {
        all_blocks[idx] = dir_ptr->inode->i_sectors[idx];
        idx++;
    }
    if (dir_ptr->inode->i_sectors[12] != 0) {
        ide_read(part->my_disk, dir_ptr->inode->i_sectors[12], all_blocks + 12, 1);
    }
    uint8_t* buffer = (uint8_t*)sys_malloc(512);
    struct dir_entry* de_ptr = (struct dir_entry*)buffer;
    uint32_t entry_size = part->sb->dir_entry_size;
    uint32_t entries_per_sec = 512 / entry_size;
    idx = 0;
    while (idx < block_count) {
        if (all_blocks[idx] == 0) {
            idx++;
            continue;
        }
        ide_read(part->my_disk, all_blocks[idx], buffer, 1);
        uint32_t entry_idx = 0;
        while (entry_idx < entries_per_sec) {
            if (!strcmp(de_ptr->filename, name)) {
                memcpy(entry, de_ptr, entry_size);
                sys_free(buffer);
                sys_free(all_blocks);
                return true;
            }
            entry_idx++;
            de_ptr++;
        }
        de_ptr = (struct dir_entry*)buffer;
        memset(buffer, 0, 512);
        idx++;
    }
    sys_free(buffer);
    sys_free(all_blocks);
    return false;
}

/* Close a directory */
void close_directory(struct dir* dir_ptr) {
    if (dir_ptr == &root_dir) return;
    close_inode(dir_ptr->inode);
    sys_free(dir_ptr);
}

/* Initialize a directory entry */
void init_dir_entry(char* filename, uint32_t inode_no, uint8_t file_type, struct dir_entry* entry) {
    ASSERT(strlen(filename) <= MAX_FILE_NAME_LEN);
    memcpy(entry->filename, filename, strlen(filename));
    entry->i_no = inode_no;
    entry->f_type = file_type;
}

/* Write a directory entry to the parent directory */
bool write_dir_entry(struct dir* parent, struct dir_entry* entry, void* io_buf) {
    struct inode* dir_inode = parent->inode;
    uint32_t dir_size = dir_inode->i_size;
    uint32_t entry_size = cur_part->sb->dir_entry_size;
    ASSERT(dir_size % entry_size == 0);
    uint32_t entries_per_sec = 512 / entry_size;
    int32_t block_lba = -1;
    uint32_t all_blocks[140] = {0};
    uint8_t idx = 0;
    while (idx < 12) {
        all_blocks[idx] = dir_inode->i_sectors[idx];
        idx++;
    }
    if (dir_inode->i_sectors[12] != 0) {
        ide_read(cur_part->my_disk, dir_inode->i_sectors[12], all_blocks + 12, 1);
    }
    struct dir_entry* de_ptr = (struct dir_entry*)io_buf;
    int32_t bitmap_idx = -1;
    idx = 0;
    while (idx < 140) {
        if (all_blocks[idx] == 0) {
            block_lba = allocate_block(cur_part);
            if (block_lba == -1) return false;
            bitmap_idx = block_lba - cur_part->sb->data_start_lba;
            sync_bitmap(cur_part, bitmap_idx, BLOCK_BITMAP);
            if (idx < 12) {
                dir_inode->i_sectors[idx] = all_blocks[idx] = block_lba;
            } else if (idx == 12) {
                dir_inode->i_sectors[12] = block_lba;
                block_lba = allocate_block(cur_part);
                if (block_lba == -1) {
                    bitmap_idx = dir_inode->i_sectors[12] - cur_part->sb->data_start_lba;
                    bitmap_set(&cur_part->block_bitmap, bitmap_idx, 0);
                    dir_inode->i_sectors[12] = 0;
                    return false;
                }
                bitmap_idx = block_lba - cur_part->sb->data_start_lba;
                sync_bitmap(cur_part, bitmap_idx, BLOCK_BITMAP);
                all_blocks[12] = block_lba;
                ide_write(cur_part->my_disk, dir_inode->i_sectors[12], all_blocks + 12, 1);
            } else {
                all_blocks[idx] = block_lba;
                ide_write(cur_part->my_disk, dir_inode->i_sectors[12], all_blocks + 12, 1);
            }
            memset(io_buf, 0, 512);
            memcpy(io_buf, entry, entry_size);
            ide_write(cur_part->my_disk, all_blocks[idx], io_buf, 1);
            dir_inode->i_size += entry_size;
            return true;
        }
        ide_read(cur_part->my_disk, all_blocks[idx], io_buf, 1);
        uint8_t entry_idx = 0;
        while (entry_idx < entries_per_sec) {
            if ((de_ptr + entry_idx)->f_type == FT_UNKNOWN) {
                memcpy(de_ptr + entry_idx, entry, entry_size);
                ide_write(cur_part->my_disk, all_blocks[idx], io_buf, 1);
                dir_inode->i_size += entry_size;
                return true;
            }
            entry_idx++;
        }
        idx++;
    }
    return false;
}

Description:

• open_root: Loads the root directory's inode into memory.
• open_directory: Opens a directory by creating a directory structure and loading its inode.
• find_dir_entry: Searches for a file or directory entry by name within a directory.
• close_directory: Closes a directory by releasing its inode and memory.
• init_dir_entry: Initializes a directory entry with a filename and inode number.
• write_dir_entry: Writes a directory entry to its parent directory, allocating new sectors if necessary.

Path Parsing Functions

/* Parse the top-level path name */
static char* parse_path(char* pathname, char* name_store) {
    if (pathname[0] == '/') {
        while (*(++pathname) == '/');
    }
    while (*pathname != '/' && *pathname != 0) {
        *name_store++ = *pathname++;
    }
    if (pathname[0] == 0) {
        return NULL;
    }
    return pathname;
}

/* Count the depth of a path */
int32_t count_path_depth(char* pathname) {
    ASSERT(pathname != NULL);
    char* p = pathname;
    char name[MAX_FILE_NAME_LEN];
    uint32_t depth = 0;
    p = parse_path(p, name);
    while (name[0]) {
        depth++;
        memset(name, 0, MAX_FILE_NAME_LEN);
        if (p) {
            p = parse_path(p, name);
        }
    }
    return depth;
}

Description:

• parse_path: Extracts the top-level name from a path and returns the remaining subpath.
• count_path_depth: Calculates the number of levels in a path by iteratively parsing it.

File Search Function

/* Structure to record search progress */
struct search_record {
    char searched_path[MAX_PATH_LEN];
    struct dir* parent_dir;
    enum file_types file_type;
};

/* Search for a file by path and return its inode number */
static int search_file(const char* pathname, struct search_record* record) {
    if (!strcmp(pathname, "/") || !strcmp(pathname, "/.") || !strcmp(pathname, "/..")) {
        record->parent_dir = &root_dir;
        record->file_type = FT_DIRECTORY;
        record->searched_path[0] = 0;
        return 0;
    }
    uint32_t path_len = strlen(pathname);
    ASSERT(pathname[0] == '/' && path_len > 1 && path_len < MAX_PATH_LEN);
    char* sub_path = (char*)pathname;
    struct dir* parent_dir = &root_dir;
    struct dir_entry entry;
    char name[MAX_FILE_NAME_LEN] = {0};
    record->parent_dir = parent_dir;
    record->file_type = FT_UNKNOWN;
    uint32_t parent_inode_no = 0;
    sub_path = parse_path(sub_path, name);
    while (name[0]) {
        ASSERT(strlen(record->searched_path) < 512);
        strcat(record->searched_path, "/");
        strcat(record->searched_path, name);
        if (find_dir_entry(cur_part, parent_dir, name, &entry)) {
            memset(name, 0, MAX_FILE_NAME_LEN);
            if (sub_path) {
                sub_path = parse_path(sub_path, name);
            }
            if (entry.f_type == FT_DIRECTORY) {
                parent_inode_no = parent_dir->inode->i_no;
                close_directory(parent_dir);
                parent_dir = open_directory(cur_part, entry.i_no);
                record->parent_dir = parent_dir;
                continue;
            } else if (entry.f_type == FT_REGULAR) {
                record->file_type = FT_REGULAR;
                return entry.i_no;
            }
        } else {
            return -1;
        }
    }
    close_directory(record->parent_dir);
    record->parent_dir = open_directory(cur_part, parent_inode_no);
    record->file_type = FT_DIRECTORY;
    return entry.i_no;
}

Description:

• search_record: Tracks the parent directory and path during file search.
• search_file: Searches for a file by recursively parsing the path and checking directory entries, returning the inode number if found.