Introduction

When a new file is created in UNIX, the kernel must assign a free inode and allocate free data blocks to store the file's content. These assignment algorithms are integral to how the file system manages storage.

---

Inode Assignment (ialloc Algorithm)

The ialloc algorithm is used to allocate a free inode for a newly created file.

Steps:

1. Check the super block's free inode list. If it contains free inode numbers:

• Take the next available inode number from the list.
• Read the corresponding inode from disk.
• Initialize the inode fields (type, permissions, owner, timestamps, etc.).
• Mark the inode as in use.
• Decrement the free inode count in the super block.
• Return the inode.

1. If the free inode list is empty:

• The kernel scans the inode list on disk starting from the remembered inode (the last inode number from the previous scan).
• It fills the super block's free inode cache with newly found free inodes.
• The remembered inode is updated to the highest inode number found.
• Then, it allocates the first inode from the refreshed list.

1. If no free inodes exist on the disk:

• Return an error (ENOSPC — No space left on device).

Inode Freeing (ifree Algorithm)

When a file is deleted and its link count drops to 0:

1. The file's inode number is added to the super block's free inode list.
2. If the list is already full, and the freed inode number is less than the remembered inode, update the remembered inode.
3. Increment the free inode count in the super block.

---

Disk Block Assignment (alloc Algorithm)

The alloc algorithm is used to allocate a free data block when a file needs more storage.

Steps:

1. Check the super block's free block list. If it contains free block numbers:

• Take the next available block number from the list.
• If the block taken is not the last entry in the cached list:
• Zero out the block (clear old data).
• Decrement the free block count.
• Return the block number.
• If it IS the last entry (link pointer):
• This last block contains a pointer to the next batch of free blocks.
• Copy the contents of this block into the super block's free list.
• Then allocate this block and return it.

1. If no free blocks are available:

• Return an error (ENOSPC).

Block Freeing (free Algorithm)

When a file's data blocks are no longer needed:

1. If the super block's free list is not full:

• Add the freed block number to the list.
• Increment the free block count.

1. If the super block's free list is full:

• Copy the current free list to the freed block (making it the head of a new chain).
• Put only the freed block's number in the super block.
• This effectively extends the linked list of free blocks.

Free Block List — Linked Structure

Super Block Free List Cache:
┌─────────────────────────────┐
│ [109, 108, 107, 106, (100)] │  ← (100) is link to next batch
└──────────────────────┬──────┘
                       │
                       ▼
              Block 100 on disk:
              ┌───────────────────────────┐
              │ [215, 214, 213, 212, (200)]│ ← (200) links further
              └───────────────────────────┘

Comparison: Inode vs Block Assignment

Creating a New File — Full Flow

When a user runs touch newfile.txt in directory /home/user1:

1. Allocate an inode (ialloc): Get a free inode, say inode 150.
2. Initialize inode 150: Set type (regular), permissions, owner, timestamps, size = 0.
3. Add directory entry: In the data blocks of /home/user1's directory, add the entry: (150, "newfile.txt").
4. Increment link count: Inode 150's link count becomes 1.
5. When data is written: Allocate data blocks (alloc) and update inode 150's block pointers.

Summary

• ialloc / ifree manage inode allocation and deallocation using the super block's free inode list.
• alloc / free manage data block allocation and deallocation using a linked list of free blocks.
• The super block caches partial free lists for efficient allocation.
• When the cached list is exhausted, it is refilled from disk (for inodes) or by following the linked list (for blocks).