File systems: allocation, inodes and links

Goals and assumptions

Compare allocation methods, calculate indexed-file capacity and access cost, and distinguish a file's identity from its names. Prerequisites: byte/block arithmetic and pointers. We use a simplified UNIX-like inode model; actual formats vary. KiB=1024 bytes. Logical block numbers begin at zero. Capacity calculations ignore independent file-size fields, disk limits and reserved pointer values unless specified. No real filesystem changes are performed by this lesson.

1. Names are labels; blocks hold contents

Imagine a warehouse catalogue. A label leads to a catalogue record, and the record lists storage locations. Multiple labels can refer to the same record. Similarly, a directory maps a filename to a file identifier such as an inode number. An inode records metadata and information used to find the file's data blocks. A pathname is resolved through directories; the name is not itself the entire file or all its storage addresses.

A file descriptor is a per-process handle for an open file, not a globally unique inode number. Separate opens may have separate current offsets; descriptors created by duplicating an open descriptor can share an open-file description and its offset. Do not infer offset sharing from equal filename strings alone.

2. Three allocation ideas

Contiguous allocation places a file in a run of neighboring blocks. If it starts at physical block s, logical block j lies at s+j, within the allocated length. Random access is simple, but growth and finding sufficiently large runs can be difficult. External fragmentation can occur in a variable-length contiguous-allocation model.

Linked allocation stores a next-block pointer in each block. Growth can use scattered free blocks, but finding a distant block from the head requires traversing the links unless extra indexing is available. Pointers consume space and a broken link can lose the remaining chain. A FAT-style table moves link information into a separate table; it is not identical to reading every on-disk data block for its pointer.

Indexed allocation stores block addresses in an index structure. Logical block number selects an address instead of requiring a data-chain walk. Index blocks cost space and may need reads. Extent-based formats store runs rather than one pointer per data block. These are tradeoffs, not a universal claim that one design wins for every workload.

3. Direct and indirect pointers

Use an inode with 6 direct pointers, one single-indirect pointer and one double-indirect pointer, no triple-indirect pointer. A block is 1024 bytes and a pointer is 4 bytes. One index block holds 1024/4=256 pointers. Direct pointers address 6 data blocks. Single-indirect addresses 256 data blocks. Double-indirect addresses 256×256=65536 data blocks, through an outer index and inner index blocks.

Maximum addressable data blocks=6+256+65536=65798. Maximum data bytes=65798×1024=67,377,152. Index blocks are metadata: do not count them as extra file data capacity. If completely populated, this structure needs 1 single-indirect index block plus 1 double-indirect outer block plus 256 inner blocks, or 258 index blocks, in addition to data blocks and the inode itself.

4. Locate a byte before counting reads

With the same format, logical blocks 0..5 use direct pointers; 6..261 use single-indirect; 262 onward use double-indirect. For byte offset 270000, division gives logical block floor(270000/1024)=263 and offset 688. Block 263 lies in double-indirect space. Subtract its start: 263−262=1. Outer index=floor(1/256)=0 and inner index=1. The final byte lies 688 bytes into the selected data block.

Assume the inode is already in RAM but no relevant index or data blocks are cached, and each referenced block requires one disk read. A direct access needs 1 data-block read; a single-indirect access needs 1 index+1 data=2 reads; a double-indirect access needs outer index+inner index+data=3 reads. Thus the offset above needs 3 reads. Directory lookup and inode reads are explicitly excluded. A cached index would change this count, so “three reads” is not a universal file-access law.

5. Hard links and symbolic links

A hard link creates another directory entry for the same file identity in the same filesystem in this model. It does not copy the data. If names a and b refer to one inode and a is unlinked, b still names the same file. A symbolic link is a separate object storing a target path. Resolving it follows that path; if the target name disappears, the symlink can remain but be dangling. Moving or removing one name does not necessarily remove all hard-link names.

For a regular file in this simplified UNIX-like model, unlinking its final name reduces its link count to zero. If an open reference still exists, storage is retained until those references are released. Therefore unlink is removal of a name, not a guarantee of immediate physical reclamation. This explains why disk space can remain used by an unlinked but open file. Permission and filesystem-specific rules still apply; these are conceptual operations, not instructions to delete anything.

6. Free-space bookkeeping

A bitmap with one bit per data block records allocation status under a stated bit convention. For 32768 managed blocks, the raw bitmap needs 32768 bits=4096 bytes=4 KiB. If stored in 1 KiB blocks, it occupies four blocks. Do not allocate one byte per block unless the scheme says so. Metadata and data updates must remain consistent across failures; crash recovery/journaling is a further topic, and a successful buffered write alone should not be treated as proof of durable media completion.

Exam checklist

Separate filename, inode, open handle, index block and data block. Write pointer fan-out before calculating powers. Translate byte offset into logical block and intra-block offset, then subtract the relevant region's start. State cache assumptions before counting reads. Distinguish data capacity from metadata overhead, and name removal from file-copying or immediate reclamation.

Original practice: six single-correct MCQs

Choose exactly one option. Each question states its own required assumptions.

FS01. An inode has 6 direct pointers, one single-indirect and one double-indirect pointer. Blocks are 1024 bytes and pointers 4 bytes. Ignoring other limits, how many data blocks can it address?

A. 262 B. 65798 C. 66056 D. 65536

Answer: B

A: 262 omits the double-indirect region.

B: Fan-out=256; total=6+256+256²=65798.

C: This adds 258 index blocks to data capacity.

D: 65536 counts only the double-indirect data region.

FS02. With 6 direct pointers, 256 entries per indirect block and zero-based logical blocks, which is the first double-indirect data block number?

A. 6 B. 256 C. 261 D. 262

Answer: D

A: 6 starts the single-indirect region.

B: The six direct blocks must also be counted.

C: 261 is the final single-indirect block.

D: Direct covers 0..5 and single-indirect 6..261; next is 262.

FS03. A requested data block is double-indirect. The inode is already in RAM; neither relevant index block nor data block is cached. Each block read costs one I/O, and pathname lookup is excluded. How many reads are required?

A. 1 B. 2 C. 3 D. 4

Answer: C

A: This omits both index reads.

B: This omits one of the two index levels or the data.

C: Read outer index, inner index, then data: three.

D: The inode read is excluded because it is already resident.

FS04. Regular-file names a and b are hard links to the same inode in one filesystem. No other changes occur. After unlinking a, what is true?

A. b becomes a separate copy B. b still names the same file C. b must become dangling like a symlink D. The file data must be immediately destroyed

Answer: B

A: Unlink does not copy the remaining file.

B: The directory entry b still refers to the same inode.

C: A hard link refers to file identity, not the removed path a.

D: A remaining hard link keeps the file named.

FS05. A free-space bitmap uses exactly one bit for each of 32768 managed blocks. Ignoring headers and padding, how many bytes does it need?

A. 32768 B. 4096 C. 1024 D. 256

Answer: B

A: This allocates one byte per block instead of one bit.

B: 32768/8=4096 bytes.

C: 1024 bytes store only 8192 allocation bits.

D: 256 bytes store only 2048 allocation bits.

FS06. In the stated UNIX-like model, a regular file loses its last hard-link name while a process still has it open. What can happen?

A. Storage remains allocated until open references are released B. Every open descriptor instantly becomes an inode number C. The file is necessarily copied to another directory D. All buffered writes are guaranteed durable

Answer: A

A: Open references can keep an unlinked file alive.

B: Descriptors and inode identifiers remain distinct.

C: Removing a name does not create a copy.

D: Link removal gives no such durability guarantee.

Sources and scope

This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.

• Official GATE 2026 CS syllabus, Section 8
• OSTEP: Files and Directories
• OSTEP: File System Implementation

Sources checked 2026-10-14.