I-nodes
| On path: Filing | 1: Filing System • 2: File Systems • 3: Files • 4: File Attributes • 5: File Types • 6: File Permissions • 7: File Access • 9: Filing System Implementation • 10: I-nodes • 11: Links • 12: File Descriptor |
|---|
| Depends on | Filing System Implementation |
|---|
Used in Unix systems, an i-node is a structure containing some file attributes and an array of pointers to blocks used by a particular file. Each i-node has a unique number and is stored in an array, managed by the O.S. An i-node is quite small and need only be kept in memory when the associated file is in use.
(As mentioned) an i-node is quite small (and a fixed size) thus it can only point to a limited number of blocks. This could limit the maximum file size rather seriously!
However, not all the blocks need to contain data. A block can, instead, be filled with pointers to other blocks. This allows considerable expansion. If that is not sufficient the ‘other blocks’ can also be pointers themselves. Some known convention can be used to determine the meaning of each item.
To zoom into a single file specifier in more detail:
In this figure a file could be up to 593 blocks long. In a ‘real’ implementation there can be far more pointers in each block, so files could be considerably bigger!
- Small files can be indexed by just the i-node.
(Up to 9 blocks in this example.) - Larger files can be indexed by the i-node plus an extra block of pointers.
(Up to 17 blocks in this example, but there would really be more pointers in a block than in the original i-node.) - Quite big files use more extra blocks:
(3 extra blocks for up to a 25 block file, 4 for up to 33 etc, up to 10 extra blocks for an 81 block long file.) - Very big files require the above 10 extra blocks plus a few more.
(10 + 3 for up to 89 block files, 14 up to 97 etc.)
In other words, using this (toy) example:
| File blocks | Extra blocks | Total blocks |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 0 | 2 |
| 3 | 0 | 3 |
| 9 | 0 | 9 |
| 10 | 1 | 11 |
| 11 | 1 | 12 |
| 12 | 1 | 13 |
| 17 | 1 | 18 |
| 18 | 3 | 21 |
| 19 | 3 | 22 |
| 25 | 3 | 28 |
| 26 | 4 | 30 |
| 27 | 4 | 31 |
| 33 | 4 | 37 |
| 34 | 5 | 39 |
| 81 | 10 | 91 |
| 82 | 13 | 95 |
| 83 | 13 | 96 |
| 90 | 14 | 104 |
| 98 | 15 | 113 |
| 145 | 20 | 165 |
| 146 | 22 | 168 |
A real example …
… may have 15 pointers in the i-node table entry (remember, this is a fixed size). Assume a 512-byte block size and 4-byte pointers, thus 128 pointers can be kept in each additional block:
- The first 12 pointers are used directly: file sizes up to 6 KiB.
- Pointer 13 is single-indirect, allowing for files up to (12 + 128) blocks – 70 KiB
- Pointer 14 is double-indirect, allowing for files up to (12 + 128+ 1282) blocks – about 8.2 MiB
- Pointer 15 is triple-indirect, allowing for files up to (12 + 128+ 1282+ 1283) blocks – about 1 GiB
Not enough? Use bigger blocks.
Note: there are some similarities in this approach to the application of multi-level page tables … and for much the same reason: it saves precious memory space in the typical cases.
Filenames
There is no mention of filenames in the description above. Files are identified by a unique, fixed size identifier which is the i-node number. These numbers are allocated by the filing system manager.
Experiment: in a Unix terminal, type
ls-ito see a directory list including the i-node numbers. More detailed explorations are available on line, e.g. this video (14 mins.) covers this quite thoroughly.
Filenames are associated with i-node numbers in the directories (files). This allows an i-node to have multiple names, something which is exploited by [Links links].
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 14.4.3, pages 575-577 |
|---|
