Directory Structure

The directory structure is the main way a file system organizes and manages files. With a sensible directory structure, users can organize, find, and manage their files efficiently. This chapter walks through the major types of directory structure and their characteristics.

The Basic Concept of a Directory

What Is a Directory

A directory is a special file in a file system used to organize and classify files; it holds reference information about other files and subdirectories. A directory is itself a file, but one with a special structure and a special role.

The Role of Directories

1. File organization: groups related files together so they are easier to manage
2. Namespace management: avoids collisions between file names
3. Access control: sets consistent access permissions for a directory and its contents
4. Path navigation: provides the path information used to locate a file

Types of Directory Structure

1. Single-Level Directory Structure

The single-level directory structure is the simplest way of organizing files: every file lives in the same directory.

Characteristics

• Simplicity: the structure is simple and easy to understand
• Fast access: all files sit at the same level, so access is quick
• Easy to implement: the file system is relatively simple to build

Drawbacks

• Name collisions: different users may pick the same file name
• Hard to manage: with many files, the directory becomes unwieldy
• Poor security: no way to isolate one user from another

Example

Where It Fits

• Simple embedded systems
• Early operating systems
• Systems that hold only a small number of files

2. Two-Level Directory Structure

The two-level directory structure gives every user a directory of their own under the root, which solves the name collision problem of the single-level design.

Characteristics

• User isolation: each user has a directory space of their own
• Safe naming: files belonging to different users can never collide
• Permission management: each user directory can carry its own permissions

Structure Example

Implementation

// A simplified implementation of a two-level directory structure
struct directory_entry {
    char name[32];
    int user_id;
    int file_type;
    int file_size;
    int first_block;
};

struct user_directory {
    int user_id;
    struct directory_entry entries[MAX_FILES];
    int file_count;
};

Advantages and Drawbacks

Advantages:

• Solves the name collision problem
• Provides basic isolation between users
• Relatively simple to implement

Drawbacks:

• Lacks hierarchical organization
• Makes it hard for users to share files
• Offers limited extensibility

3. Tree-Structured Directory

The tree-structured directory is the organization used by most modern operating systems, and it supports directories nested many levels deep.

Characteristics

• Hierarchical organization: supports directory nesting of unlimited depth
• Great flexibility: users can build directory trees of any depth they need
• Path navigation: a path pinpoints a file exactly
• Sharing: supports sharing files between different directories

Structure Example

Path Notation

• Absolute path: the complete path, starting at the root directory
  • Example: /home/user1/documents/work/report1.doc
• Relative path: a path that starts at the current directory
  • Example: ./documents/work/report1.doc
  • Example: ../user2/projects/

Implementation

// Node representation of a tree-structured directory
struct directory_node {
    char name[256];
    int type;  // 0: file, 1: directory
    struct directory_node *parent;
    struct directory_node *children[MAX_CHILDREN];
    int child_count;
    struct file_metadata *file_info;
};

// Path resolution function
struct directory_node* find_path(const char* path) {
    char* path_copy = strdup(path);
    char* token = strtok(path_copy, "/");
    struct directory_node* current = root_directory;

    while (token != NULL) {
        current = find_child(current, token);
        if (current == NULL) {
            free(path_copy);
            return NULL;
        }
        token = strtok(NULL, "/");
    }

    free(path_copy);
    return current;
}

Directory Operations

// Create a directory
int mkdir(const char* path) {
    struct directory_node* parent = get_parent_directory(path);
    char* dir_name = get_last_component(path);

    if (parent == NULL || find_child(parent, dir_name) != NULL) {
        return -1;  // the parent directory does not exist, or the directory already exists
    }

    struct directory_node* new_dir = create_directory_node(dir_name);
    add_child(parent, new_dir);
    return 0;
}

// Remove a directory
int rmdir(const char* path) {
    struct directory_node* dir = find_path(path);
    if (dir == NULL || dir->type != 1 || dir->child_count > 0) {
        return -1;  // the directory does not exist, is not a directory, or is not empty
    }

    remove_child(dir->parent, dir);
    free_directory_node(dir);
    return 0;
}

Advantages and Drawbacks

Advantages:

• Supports complex file organization
• Provides flexible path navigation
• Supports file sharing and links
• Makes permission management easy

Drawbacks:

• More complex to implement
• Costs time on path resolution
• Circular references have to be handled

4. Acyclic-Graph Structure

The acyclic-graph structure lets a file or directory be referenced by several directories, which creates sharing, but it does not allow circular references.

Characteristics

• File sharing: a single file can be referenced by several directories
• Space saving: a shared file is stored only once
• Consistency: a change to a shared file is visible through every reference
• No cycles: circular references are not allowed

Implementation

Hard Link

// Implementation of a hard link
struct inode {
    int inode_number;
    int link_count;  // reference count
    int file_size;
    int blocks[12];
    // other metadata...
};

// Create a hard link
int link(const char* old_path, const char* new_path) {
    struct inode* inode = get_inode(old_path);
    if (inode == NULL) return -1;

    // Create a new directory entry in the target directory
    struct directory_entry* entry = create_directory_entry(new_path, inode->inode_number);
    if (entry == NULL) return -1;

    // Increment the reference count
    inode->link_count++;
    return 0;
}

Symbolic Link

// Implementation of a symbolic link
struct symlink_data {
    char target_path[256];
    int target_inode;
};

// Create a symbolic link
int symlink(const char* target, const char* link_path) {
    // Create the symbolic link file
    struct inode* link_inode = create_file(link_path);
    if (link_inode == NULL) return -1;

    // Store the target path
    struct symlink_data* data = malloc(sizeof(struct symlink_data));
    strcpy(data->target_path, target);
    link_inode->data = data;
    link_inode->type = SYMLINK;

    return 0;
}

Structure Example

Differences Between Hard Links and Symbolic Links

The Implementation of Directories

The Structure of a Directory Entry

// The basic structure of a directory entry
struct directory_entry {
    char name[256];        // file name
    int inode_number;      // the inode number it refers to
    int file_type;         // file type
    int name_length;       // length of the file name
    char padding[4];       // padding bytes
};

// The contents of a directory file
struct directory_content {
    struct directory_entry entries[MAX_ENTRIES];
    int entry_count;
    int free_space;
};

Implementing Directory Operations

1. Creating a Directory

int create_directory(const char* path) {
    // 1. Resolve the path and find the parent directory
    struct inode* parent_inode = get_parent_inode(path);
    if (parent_inode == NULL) return -1;

    // 2. Create a new inode
    struct inode* new_inode = allocate_inode();
    if (new_inode == NULL) return -1;

    // 3. Initialize the directory inode
    new_inode->type = DIRECTORY;
    new_inode->size = 0;
    new_inode->link_count = 2;  // . and ..

    // 4. Add the directory entry to the parent directory
    char* dir_name = get_last_component(path);
    add_directory_entry(parent_inode, dir_name, new_inode->number);

    // 5. Create the . and .. directory entries
    create_dot_entries(new_inode, parent_inode->number);

    return 0;
}

2. Traversing a Directory

// Traverse the contents of a directory
int list_directory(const char* path) {
    struct inode* dir_inode = get_inode(path);
    if (dir_inode == NULL || dir_inode->type != DIRECTORY) {
        return -1;
    }

    struct directory_content* content = read_directory_content(dir_inode);
    if (content == NULL) return -1;

    printf("Directory: %s\n", path);
    printf("Total entries: %d\n", content->entry_count);
    printf("\n");

    for (int i = 0; i < content->entry_count; i++) {
        struct directory_entry* entry = &content->entries[i];
        struct inode* entry_inode = get_inode_by_number(entry->inode_number);

        printf("%s\t", entry->name);
        if (entry_inode->type == DIRECTORY) {
            printf("DIR\t");
        } else {
            printf("FILE\t");
        }
        printf("%d bytes\n", entry_inode->size);
    }

    free(content);
    return 0;
}

3. Resolving a Path

// Resolve an absolute path
struct inode* resolve_path(const char* path) {
    if (path[0] != '/') return NULL;  // it has to be an absolute path

    struct inode* current = root_inode;
    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 inode* next = find_in_directory(current, token);
        if (next == NULL) {
            free(path_copy);
            return NULL;  // the next component cannot be found
        }

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

    free(path_copy);
    return current;
}

Optimizing the Directory Structure

1. Hash Table Optimization

// Speed up directory lookup with a hash table
struct directory_hash {
    char name[256];
    int inode_number;
    struct directory_hash* next;
};

struct directory_cache {
    struct directory_hash* hash_table[HASH_SIZE];
    int entry_count;
};

// The hash lookup function
struct inode* hash_find(struct directory_cache* cache, const char* name) {
    int hash = hash_function(name);
    struct directory_hash* entry = cache->hash_table[hash];

    while (entry != NULL) {
        if (strcmp(entry->name, name) == 0) {
            return get_inode_by_number(entry->inode_number);
        }
        entry = entry->next;
    }

    return NULL;
}

2. B-Tree Optimization

// Organize directory entries with a B-tree
struct btree_node {
    char* keys[MAX_KEYS];
    int inode_numbers[MAX_KEYS];
    struct btree_node* children[MAX_KEYS + 1];
    int key_count;
    int is_leaf;
};

// B-tree lookup
struct inode* btree_find(struct btree_node* root, const char* key) {
    if (root == NULL) return NULL;

    int i = 0;
    while (i < root->key_count && strcmp(key, root->keys[i]) > 0) {
        i++;
    }

    if (i < root->key_count && strcmp(key, root->keys[i]) == 0) {
        return get_inode_by_number(root->inode_numbers[i]);
    }

    if (root->is_leaf) {
        return NULL;
    }

    return btree_find(root->children[i], key);
}

---

Glossary