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

Minimal Entry (Original Unix V7):
┌─────────────────────────────┐
│ inode (2 bytes)             │  ← Just the inode number
│ name (14 bytes, padded)     │  ← Just the filename
└─────────────────────────────┘
Total: 16 bytes
 
Rich Entry (NTFS):
┌─────────────────────────────┐
│ MFT Reference (8 bytes)     │  ← File locator
│ Entry size (2 bytes)        │  ← Variable length support
│ Name length (2 bytes)       │  ← For reading name
│ Flags (4 bytes)             │  ← Entry metadata
│ Parent directory (8 bytes)  │  ← For consistency checks
│ Creation time (8 bytes)     │  ← Cached timestamp
│ Modified time (8 bytes)     │  ← Cached timestamp
│ Access time (8 bytes)       │  ← Cached timestamp
│ File size (8 bytes)         │  ← Cached from MFT
│ Allocated size (8 bytes)    │  ← Cached from MFT
│ Filename (variable, UTF-16) │  ← Up to 255 chars
└─────────────────────────────┘
Total: 66+ bytes (but 'dir' doesn't need MFT reads!)
 
The trade-off:
- Minimal entries save space, but every 'ls -l' reads every inode
- Rich entries cost space, but directory listing is fast

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

// Original Unix V7: 16 bytes fixed
struct v7_direct {
    uint16_t d_ino;      // Inode number (0 = unused)
    char d_name[14];     // Filename, null-padded
};
 
// DOS FAT 8.3: 32 bytes fixed
struct fat_dirent {
    char name[8];        // Filename, space-padded
    char ext[3];         // Extension, space-padded
    uint8_t attr;        // Attributes
    uint8_t reserved[10];
    uint16_t time;       // Modification time
    uint16_t date;       // Modification date
    uint16_t cluster;    // First cluster
    uint32_t size;       // File size
};
 
// Advantages of fixed-length:
// 1. Direct indexing: entry[n] is at offset n * entry_size
// 2. Simple allocation: any empty slot works
// 3. Easy recovery: known boundaries between entries
// 4. Binary search possible (if sorted)
 
// Disadvantages:
// 1. Wasted space for short names ("a.c" uses 14 bytes)
// 2. Arbitrary name length limits (14 chars, 8.3)
// 3. Can't adapt to different needs
 
// Example: Finding entry #47 in fixed-length directory
struct v7_direct* get_entry(void* dir_data, int index) {
    return (struct v7_direct*)dir_data + index;  // O(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

// Linux ext4 directory entry
struct ext4_dir_entry_2 {
    __le32 inode;        // Inode number
    __le16 rec_len;      // Total entry length (including padding)
    __u8   name_len;     // Actual filename length
    __u8   file_type;    // File type (for quick filtering)
    char   name[];       // Filename (NOT null-terminated)
};
 
// Entry layout in memory:
// ┌────────┬────────┬────────┬────────┬─────────────────────┐
// │ inode  │rec_len │name_len│  type  │   name + padding    │
// │4 bytes │2 bytes │ 1 byte │ 1 byte │   variable bytes    │
// └────────┴────────┴────────┴────────┴─────────────────────┘
 
// rec_len is aligned to 4 bytes and includes padding
// This allows quick traversal and absorbs deleted space
 
// Example: Parsing variable-length directory block
void parse_directory_block(char* block, size_t block_size) {
    size_t offset = 0;
    
    while (offset < block_size) {
        struct ext4_dir_entry_2* entry = 
            (struct ext4_dir_entry_2*)(block + offset);
        
        if (entry->rec_len == 0) break;  // Corruption check
        
        if (entry->inode != 0) {  // Not deleted
            // entry->name is NOT null-terminated!
            printf("%.*s -> inode %u\n", 
                   entry->name_len, entry->name, entry->inode);
        }
        
        offset += entry->rec_len;  // Skip to next entry
    }
}
 
// Advantages of variable-length:
// 1. Space efficient (short names use less space)
// 2. Long names supported (255 chars typical)
// 3. Flexible for future extensions
 
// Disadvantages:
// 1. Must scan sequentially (no direct indexing)
// 2. Complex allocation (find gap large enough)
// 3. Fragmentation as entries deleted/added

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

// FAT short (8.3) directory entry - 32 bytes exactly
struct fat_short_entry {
    char     name[8];        // Filename, space-padded, uppercase
    char     ext[3];         // Extension, space-padded, uppercase
    uint8_t  attr;           // Attribute byte
    uint8_t  nt_reserved;    // Reserved for NT
    uint8_t  create_time_ms; // Creation time (10ms units)
    uint16_t create_time;    // Creation time (2-second resolution)
    uint16_t create_date;    // Creation date
    uint16_t access_date;    // Last access date (no time!)
    uint16_t cluster_hi;     // High 16 bits of cluster (FAT32)
    uint16_t modify_time;    // Modification time
    uint16_t modify_date;    // Modification date
    uint16_t cluster_lo;     // Low 16 bits of cluster
    uint32_t size;           // File size in bytes
};
 
// Attribute byte flags
#define ATTR_READ_ONLY  0x01
#define ATTR_HIDDEN     0x02
#define ATTR_SYSTEM     0x04
#define ATTR_VOLUME_ID  0x08  // Volume label, not a file
#define ATTR_DIRECTORY  0x10
#define ATTR_ARCHIVE    0x20
#define ATTR_LFN        0x0F  // Long filename marker
 
// FAT Long Filename (LFN) entry - also 32 bytes
// Used for names > 8.3 or with special characters
struct fat_lfn_entry {
    uint8_t  order;          // Sequence number (0x40 = last)
    uint16_t name1[5];       // Characters 1-5 (UCS-2)
    uint8_t  attr;           // Always 0x0F
    uint8_t  type;           // Always 0x00
    uint8_t  checksum;       // Checksum of short name
    uint16_t name2[6];       // Characters 6-11
    uint16_t cluster;        // Always 0x0000
    uint16_t name3[2];       // Characters 12-13
};
 
// Long filenames are stored BACKWARDS before short entry:
// Entry -3: LFN part 3 (chars 27-39)
// Entry -2: LFN part 2 (chars 14-26)  
// Entry -1: LFN part 1 (chars 1-13)
// Entry 0:  Short entry (8.3 name, actual metadata)

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

// ext4 directory entry (variable length)
struct ext4_dir_entry_2 {
    __le32 inode;        // 4 bytes: Inode number (0 = deleted)
    __le16 rec_len;      // 2 bytes: Entry length (aligned to 4)
    __u8   name_len;     // 1 byte: Name length (1-255)
    __u8   file_type;    // 1 byte: File type
    char   name[];       // 0-255 bytes: Filename
};
 
// File type values (set at creation time)
#define EXT4_FT_UNKNOWN   0
#define EXT4_FT_REG_FILE  1
#define EXT4_FT_DIR       2
#define EXT4_FT_CHRDEV    3
#define EXT4_FT_BLKDEV    4
#define EXT4_FT_FIFO      5
#define EXT4_FT_SOCK      6
#define EXT4_FT_SYMLINK   7
 
// Example directory block:
// Offset   inode  rec_len name_len type  name
// 0        2      12      1        2     "."
// 12       2      12      2        2     ".."
// 24       100    16      8        1     "file.txt"
// 40       101    20      10       2     "subdir"
// 60       102    4036    7        1     "data.db"
//                 ^^^^
// Last entry's rec_len extends to end of block
 
// Why file_type exists:
// Without it: readdir() reads inode for EVERY file to determine type
// With it: Can filter "show only directories" without inode reads
// Trade-off: One extra byte per entry, must keep synchronized

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

// NTFS stores directory entries as index entries in B+ trees
// Each entry contains a copy of the FILE_NAME attribute
 
struct ntfs_index_entry {
    // Index entry header
    uint64_t mft_reference;     // MFT record number + sequence
    uint16_t entry_length;      // Total size of this entry
    uint16_t key_length;        // Size of the key (FILE_NAME)
    uint32_t flags;             // INDEX_ENTRY_NODE, INDEX_ENTRY_END
    
    // FILE_NAME attribute (the key)
    uint64_t parent_directory;  // Parent's MFT reference
    uint64_t creation_time;     // 100-nanosecond intervals since 1601
    uint64_t modification_time;
    uint64_t mft_modification_time;
    uint64_t access_time;
    uint64_t allocated_size;    // Size on disk (clusters)
    uint64_t data_size;         // Logical file size
    uint32_t file_flags;        // READ_ONLY, HIDDEN, SYSTEM, etc.
    uint32_t reparse_point;     // For symlinks, mount points
    uint8_t  name_length;       // Filename length in characters
    uint8_t  name_type;         // POSIX, WIN32, DOS, WIN32_AND_DOS
    wchar_t  name[];            // UTF-16LE filename
    
    // If INDEX_ENTRY_NODE flag set:
    // uint64_t vcn;            // VCN of child node
};
 
// NTFS duplicates substantial metadata in directory entries
// This makes 'dir' incredibly fast:
// - No MFT reads needed for size, dates, attributes
// - Only need MFT for actual file access
 
// Name types:
// POSIX: Case-sensitive, full Unicode
// WIN32: Case-insensitive, most Unicode
// DOS: 8.3 short name for compatibility
// WIN32_AND_DOS: WIN32 name that's also valid DOS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// FAT deletion: First byte of name set to 0xE5
void fat_delete_entry(struct fat_short_entry* entry) {
    entry->name[0] = 0xE5;  // Magic "deleted" marker
    // Everything else unchanged!
    // Size, cluster, dates all still present
}
 
// Why 0xE5?
// - 0x00 means "never used" (end of directory)
// - 0xE5 means "was used, now deleted"
// - Originally chosen by Tim Paterson for 86-DOS/MS-DOS
// - Japanese Kanji codepage uses E5 as first byte
//   So they use 0x05 instead (converted on read)
 
// Space reclamation:
// - Deleted entries can be reused for new files
// - Scan continues past deleted entries
// - Directory shrinks only if last entries deleted
 
// Data recovery implication:
// - Undelete tools scan for 0xE5 entries
// - If cluster chain not overwritten, file recoverable
// - This is why "secure delete" overwrites data

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

// ext4 deletion: Merge deleted entry with previous
void ext4_delete_entry(struct ext4_dir_entry_2* prev,
                       struct ext4_dir_entry_2* target) {
    // Set inode to 0 (entry is now free)
    target->inode = 0;
    
    // Absorb target's space into previous entry
    if (prev != NULL) {
        prev->rec_len += target->rec_len;
        // Now prev->rec_len spans both entries
        // target is effectively "gone"
    }
    // If target is first entry, just set inode=0
    // Space reclaimed when new entry fits in this slot
}
 
// Before deletion of "b.txt":
// ┌──────────────────┬───────────────────┬──────────────────┐
// │ a.txt (rec=20)   │ b.txt (rec=20)    │ c.txt (rec=4056) │
// └──────────────────┴───────────────────┴──────────────────┘
 
// After deletion:
// ┌──────────────────┬───────────────────┬──────────────────┐
// │ a.txt (rec=40)   │ (absorbed space)  │ c.txt (rec=4056) │
// └──────────────────┴───────────────────┴──────────────────┘
 
// Space reuse:
void ext4_insert_entry(char* block, const char* name, uint32_t inode) {
    struct ext4_dir_entry_2* entry = (struct ext4_dir_entry_2*)block;
    
    while (entry->rec_len > 0) {
        // Calculate minimum space this entry needs
        size_t min_size = 8 + entry->name_len;
        min_size = (min_size + 3) & ~3;  // Align to 4
        
        // If entry has extra space (from absorbed deletions)
        size_t new_entry_size = 8 + strlen(name);
        new_entry_size = (new_entry_size + 3) & ~3;
        
        if (entry->rec_len - min_size >= new_entry_size) {
            // Split: shrink this entry, insert new after it
            // ... (insertion code)
        }
        
        entry = next_entry(entry);
    }
}

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

B-tree directory deletion (XFS, NTFS, Btrfs):
 
Unlike linear lists, B-trees actually REMOVE entries:
 
1. Locate entry in leaf node (O(log n))
2. Remove entry from leaf
3. If leaf underflows (< minimum keys):
   a. Borrow from sibling if possible
   b. Otherwise, merge with sibling
4. Recursively fix parent if needed
 
Advantages:
- No fragmentation (entries always contiguous in nodes)
- No "deleted entry" scanning overhead
- Space immediately available after node cleanup
 
Disadvantages:
- More complex than marking
- Potential for cascading rebalancing
- Harder to "undelete" (entry truly gone)
 
Data recovery with B-trees:
- Much harder than FAT/ext4
- Entry removed from index immediately
- Only hope is journaling or snapshots
- Forensic tools must reconstruct trees

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

// Every Unix/Linux directory contains:
// "."  - Points to the directory itself
// ".." - Points to the parent directory
 
// When directory "/home/alice" (inode 100) is created:
struct ext4_dir_entry_2 dot = {
    .inode = 100,       // This directory's inode
    .rec_len = 12,
    .name_len = 1,
    .file_type = EXT4_FT_DIR,
    .name = "."
};
 
struct ext4_dir_entry_2 dotdot = {
    .inode = 50,        // Parent directory's inode (/home)
    .rec_len = 4084,    // Spans rest of block
    .name_len = 2,
    .file_type = EXT4_FT_DIR,
    .name = ".."
};
 
// Root directory is special:
// ".."  points to itself (inode 2 on ext4)
// There is no parent above root
 
// Why do these entries exist?
// 1. Convenience: "cd .." works without path parsing
// 2. Link counting: "." is why directory link count starts at 2
// 3. Path resolution: Relative paths need these references
// 4. Recovery: Can reconstruct tree by following ".." pointers
 
// Hard link count for directories:
// Empty directory: 2 (parent's reference + self ".")
// With subdirectory: 3 (parent + "." + subdir's "..")
// Each subdirectory adds 1 to parent's link count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// FAT volume label entry
struct fat_volume_label {
    char name[11];       // Volume label (space-padded)
    uint8_t attr;        // 0x08 = ATTR_VOLUME_ID
    // Rest of 32-byte entry is zeros
};
// Only exists in root directory
// Not a real file - just stores the volume name
 
// FAT End-of-Directory marker
// Entry with name[0] == 0x00 means "no more entries"
// Different from 0xE5 (deleted) - stops scanning entirely
 
// NTFS "." and ".." handling:
// NTFS stores "." as special case (MFT reference to self)
// ".." is implicit from parent reference in FILE_NAME attribute
// Not stored as separate index entries like Unix
 
// Symbolic link entries:
// ext4: file_type = EXT4_FT_SYMLINK, points to inode with target path
// NTFS: Reparse point with symlink data
// FAT: Not supported (VFAT added .lnk files as workaround)