Inode pointer structure: Difference between revisions
→Structure: ce as per MOS:NUMERAL and simplify definition |
|||
| (38 intermediate revisions by 31 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Hierarchy/layout for directing inodes in a Unix File System}} |
|||
{{lowercase|inode pointer structure}} |
|||
{{Lowercase title}} |
|||
[[Image:Ext2-inode.gif|right]] |
|||
{{no footnotes|date = February 2012}} |
|||
| ⚫ | The '''inode pointer structure''' is a structure adopted by the [[inode]] of a file in the [[Unix File System]] (UFS) |
||
[[File:Ext2-inode.svg|thumb|Example of structure]] |
|||
| ⚫ | The '''inode pointer structure''' is a structure adopted by the [[inode]] of a file in the [[Unix File System]] (UFS) to list the addresses of a file's [[block (data storage)|data blocks]]. It is also adopted by many related file systems, including the [[ext3]] file system, popular with Linux users. |
||
==Structure== |
|||
| ⚫ | |||
In the past, the structure may have consisted of about twelve pointers, but most modern file systems use fifteen pointers. These pointers consist of (assuming 15 pointers in the inode):<ref>https://inst.eecs.berkeley.edu/~cs162/sp20/enwiki/static/sections/section9-sol.pdf</ref> |
|||
* One singly indirect pointer (a pointer that points to a block of pointers that then point to blocks of the file's data) |
|||
* One doubly indirect pointer (a pointer that points to a block of pointers that point to other blocks of pointers that then point to blocks of the file's data) |
|||
* One triply indirect pointer (a pointer that points to a block of pointers that point to other blocks of pointers that point to other blocks of pointers that then point to blocks of the file's data) |
|||
| ⚫ | |||
| ⚫ | The structure is partially illustrated in the diagram accompanying this article. The structure allows for inodes to describe very large files in |
||
* 1 '''singly indirect pointer''' (pointing to a block of direct pointers) |
|||
* 1 '''doubly indirect pointer''' (pointing to a block of single indirect pointers) |
|||
* 1 '''triply indirect pointer''' (pointing to a block of doubly indirect pointers) |
|||
The levels of indirection indicate the number of pointer that must be followed before reaching actual file data. |
|||
| ⚫ | The inode pointer structure not only allows for files to easily be allocated to non-contiguous blocks, it also allows the data at a particular location inside a file to be easily located. This is possible because the logical block size is fixed. For example, if each block is 8 kB, file data at |
||
==Key features== |
|||
| ⚫ | Unlike |
||
===Fixed logical block size=== |
|||
| ⚫ | |||
| ⚫ | The structure is partially illustrated in the diagram accompanying this article. The structure allows for inodes to describe very large files in file systems with a fixed logical block size. Central to the mechanism is that blocks of addresses (also called ''indirect blocks'') are only allocated as needed. For example, a 12-block file would be described using just the inode because its blocks fit into the number of direct pointers available. However, a 13-block file needs an indirect block to contain the thirteenth address. |
||
===Ease of data location=== |
|||
| ⚫ | |||
| ⚫ | The inode pointer structure not only allows for files to easily be allocated to non-contiguous blocks, it also allows the data at a particular location inside a file to be easily located. This is possible because the logical block size is fixed. For example, if each block is 8 kB, file data at 112 kB to 120 kB would be pointed to by the third pointer of the first indirect block (assuming twelve direct pointers in the inode pointer structure). |
||
* [http://www.angelfire.com/myband/binusoman/Unix.html Unix File System], Binu, accessed May 24, 2011. |
|||
* [http://www.apl.jhu.edu/Misc/Unix-info/workshop/fstour.html A Basic UNIX Tutorial], Idaho State University, January 9, 1996. |
|||
===Indirect blocks=== |
|||
| ⚫ | |||
| ⚫ | Unlike inodes, which are fixed in number and allocated in a special part of the file system, the indirect blocks may be of any number and are allocated in the same part of the file system as data blocks. The number of pointers in the indirect blocks is dependent on the block size and size of block pointers. Example: with a 512-byte block size, and 4-byte block pointers, each indirect block can consist of 128 (512 / 4) pointers. |
||
| ⚫ | |||
{{Reflist}} |
|||
| ⚫ | |||
| ⚫ | * {{cite journal | author1=[[Marshall Kirk McKusick]]|author2=[[Bill Joy|William N. Joy]]|author3=[[Samuel J Leffler]]|author4=Robert S. Fabry | title=A Fast File System for UNIX | date=February 18, 1984 | url=http://www.cs.berkeley.edu/~brewer/cs262/FFS.pdf |journal=[[Computer Systems Research Group]] }} |
||
[[Category: |
[[Category:Unix file system technology]] |
||
Latest revision as of 23:00, 20 May 2024
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (February 2012) |
The inode pointer structure is a structure adopted by the inode of a file in the Unix File System (UFS) to list the addresses of a file's data blocks. It is also adopted by many related file systems, including the ext3 file system, popular with Linux users.
Structure
[edit]In the past, the structure may have consisted of about twelve pointers, but most modern file systems use fifteen pointers. These pointers consist of (assuming 15 pointers in the inode):[1]
- 12 direct pointers that directly point to blocks of the file's data
- 1 singly indirect pointer (pointing to a block of direct pointers)
- 1 doubly indirect pointer (pointing to a block of single indirect pointers)
- 1 triply indirect pointer (pointing to a block of doubly indirect pointers)
The levels of indirection indicate the number of pointer that must be followed before reaching actual file data.
Key features
[edit]Fixed logical block size
[edit]The structure is partially illustrated in the diagram accompanying this article. The structure allows for inodes to describe very large files in file systems with a fixed logical block size. Central to the mechanism is that blocks of addresses (also called indirect blocks) are only allocated as needed. For example, a 12-block file would be described using just the inode because its blocks fit into the number of direct pointers available. However, a 13-block file needs an indirect block to contain the thirteenth address.
Ease of data location
[edit]The inode pointer structure not only allows for files to easily be allocated to non-contiguous blocks, it also allows the data at a particular location inside a file to be easily located. This is possible because the logical block size is fixed. For example, if each block is 8 kB, file data at 112 kB to 120 kB would be pointed to by the third pointer of the first indirect block (assuming twelve direct pointers in the inode pointer structure).
Indirect blocks
[edit]Unlike inodes, which are fixed in number and allocated in a special part of the file system, the indirect blocks may be of any number and are allocated in the same part of the file system as data blocks. The number of pointers in the indirect blocks is dependent on the block size and size of block pointers. Example: with a 512-byte block size, and 4-byte block pointers, each indirect block can consist of 128 (512 / 4) pointers.
References
[edit]- Ext3 for large file systems, LWN.net, June 12, 2006.
- Marshall Kirk McKusick; William N. Joy; Samuel J Leffler; Robert S. Fabry (February 18, 1984). "A Fast File System for UNIX" (PDF). Computer Systems Research Group.