Unit 2 55406o

THE DESIGN OF THE UNIX OPERATING SYSTEM Maurice J. bach Prentice Hall

Internal representation of files

1

Table of Contents          

Introduction Inodes Structure of a Regular File Directories Conversion of a Path Name to an Inode Super Block Inode Assignment to a New File Allocation of Disk Blocks Other File Types Summary

Internal representation of files

2

Introduction (1)

 The inode contains information necessary for a

process to access a file.  File ownership  Access rights  File size  Location of file data

 Process access a file by a well defined set of system

calls by specifying the path name  Kernel converts the path name to the file’s inode.

Internal representation of files

3

Introduction (2) Gives insight into

 How the kernel manipulates the inode  The internal structure of regular files and how the    

kernel reads and writes their data Structure of the directory Structure of the superblock Assignment of disk inodes and disk block to file file types : pipes and device file

Internal representation of files

4

File System Algorithms Lower Level File system Algorithms namei alloc free

ialloc ifree

iget iput bmap Buffer allocation algorithms getblk

brelse

bread breada

Internal representation of files

bwrite

5

Table of Contents          

Introduction Inodes Structure of a Regular File Directories Conversion of a Path Name to an Inode Super Block Inode Assignment to a New File Allocation of Disk Blocks Other File Types Summary

Internal representation of files

6

Definition of Inodes  Every file has a unique inode  Contain the information necessary for a

process to access a file  Exist in a static form on disk  Kernel reads them into an in-core inode to manipulate them.

Internal representation of files

7

Contents of Disk Inodes  File owner identifier (individual/group owner)     

File type (regular, directory,..) File access permission (owner,group,other) File access time Number of links to the file Table of contents for the disk address of data in a file  Kernel saves the data in discontiguous disk blocks  The Inodes identifies the disk blocks

 File size  1 greater than the highest byte offset of data  Byte offset 1000 -> the size of the file : 1001 byte

Internal representation of files

8

Sample Disk Inode      

File owner identifier File type File access permission File access time Number of links to the file Table of contents for the disk address of data in a file  File size

Internal representation of files

Owner mjb Group os Type regular file Perms rwxr-xr-x Accessed Oct 23 1984 1:45 P.M Modified Oct 22 1984 10:3 A.M Inode Oct 23 1984 1:30 P.M Size 6030 bytes Disk addresses

9

Distinction Between Writing Inode and File  File change only when writing it.  Inode change when changing the file, or when changing its owner, permisson,or link settings.

 Changing a file implies a change to the inode,  But, changing the inode does not imply that the file change.

Internal representation of files

10

Contents of The In-core copy of The Inode(1)  Fields of the disk inode  Status of the in-core inode, indicating whether  Inode is locked  Process is waiting for the inode to become unlocked  Differ from the disk copy as a result of a change to

the data in the inode  Differ from the disk copy as a result of a change to the file data  File is a mount point

Internal representation of files

11

Contents of The In-core copy of The Inode (2)  Logical device number of the file system  Inode number (linear array on disk, disk inode not

need this field)  Pointers to other in-core inodes  Reference count

Internal representation of files

12

In-core Inode Vs Buffer Header  In-core Inode  An inode is on the free list only if its reference count is 0  Kernel can reallocate the in-core inode to another disk inode  Buffer header  No reference count  It is on the free list if and only if it is unlocked

Internal representation of files

13

Algorithm for Allocation of In-Core Inodes (1) algorithm iget input: file system inode number output: locked inode { while(not done){ if (inode in inode cache){ if (inode locked){ sleep(event inode becomes unlocked); continue; } if (inode on inode free list) remove from free list; increment inode reference count; return (inode); }

Internal representation of files

14

Algorithm for Allocation of In-Core Inodes (2) /*inode not in inode cache*/ if(no inodes on free list) return(error); remove new inode from free list; reset inode number and file system; remove inode from old hash queue,place on new one; read inode from disk(algorithm bread); initialize inode (e.g. reference count to 1); return (inode);

} }

Internal representation of files

15

Accessing Inodes  Kernel identifies inodes by their file system and

inode number  Allocate in-core inodes at the request of higherlevel algorithms (in-core inode, by iget algorithm)  Kernel maps the device number & inode number into a hash queue  Search the queue for the inode …

Internal representation of files

16

Block Number  Computing logical disk block number  Block number

= ((inode number –1) / number of inodes per block) + start block inode list  Example 1    

Block 2 : beginning of the inode list 8 inodes per block Inode number 8 is in disk block ? Inode number 9 is ?

 Example 2  Block 2 : beginning of the inode list  16 inodes per block  Inode number 8 is in disk block ?  Inode number 9 is ?  Inode number 17 is ? Internal representation of files

17

Byte Offset  Read the block using bread

 Computing byte offset of the inode in the block  ((inode number –1) mod (number of inodes per block))* size of disk inode  Example   

Each disk inode 64 bytes 1 block : 8 inodes Inode 8 starts at byte offset 448 in the disk block

Internal representation of files

18

Inode Lock and Reference Count  Kernel manipulates them independently  Inode lock  Set during execution of a system call to prevent other processes

from accessing the inode while it is in use.  Kernel releases the lock at the conclusion of the system call  Inode is never locked across system calls.

 Reference count  Kernel increase/decrease when reference is active/inactive  Prevent the kernel from reallocating an active in-core inode

Thus kernel can lock and unlock an allocated inode independent of the value of the reference count.

Internal representation of files

19

Releasing an Inodes(1)  Using algorithm iput  decrements in-core reference count  Write the inode to disk  Reference count is 0  The in-core copy differs from the disk copy  Add the inode on the free list of inodes  For caching

Internal representation of files

20

Releasing an Inode (2) algorithm iput /* release (put) access to in-core inode */ input: pointer to in-core inode output: none { lock inode if not already locked; decrement inode reference count; if(reference count ==0){ if(inode link count ==0){ free disk blocks for file (algorithm free, section 4.7); set file type to 0; free inode (algorithm ifree, section 4.6); } if(file accessed or inode changed or file changed) update disk inode; put inode on free list; } release inode lock; } Internal representation of files

21

Table of Contents          

Introduction Inodes Structure of a Regular File Directories Conversion of a Path Name to an Inode Super Block Inode Assignment to a New File Allocation of Disk Blocks Other File Types Summary

Internal representation of files

22

Structure of a Regular File  Table of contents in an inode  Location of a file’s data on disk  A set of disk block # 

Each block on a disk is addressable by number

 Not contiguous file allocation strategy  Why ?  When a file expand or contract…  Fragmentations occur

Internal representation of files

23

Sample - Fragmentation ….

File B

File A 50

40

…. 40

60

Free

File A 50

…….

File C 70

60

…….

File B

File C 70

85

 File B was expanded  Garbage collection – too high cost Internal representation of files

24

Structure of a Regular File – UNIX System V 13 entries in the inode table of contents  10 direct, 1 indirect, 1 double indirect, 1 triple indirect block

 Assume  a logical block = 1K bytes  a block number is addressable by a 32 bit (4 bytes) integer  a block can hold up to 256 block numbers

 Byte Capacity of a File

10 direct blocks with 1K bytes each= 10K bytes 1 indirect block with 256 direct blocks= 1K*256 = 256K bytes 1 double indirect block with 256 indirect blocks = 256K*256= 64M bytes 1 triple indirect block with 256 double indirect blocks=64M*256=16G bytes

Internal representation of files

25

Direct and Indirect Blocks in Inode Inode

Data Blocks

direct0

direct1 direct2 direct3 direct4

direct5 direct6 direct7 direct8 direct9 single indirect double indirect triple indirect Internal representation of files

26

Byte Offset and Block Number  Process access data in a file by byte offset.  The file starts at logical block 0 and continues to a logical block number corresponding to the file size

 Kernel accesses the inode and converts the logical file block into the appropriate disk block (bmap algorithm)

Internal representation of files

27

Conversion of Byte Offset to Block Number Algorithm bmap /* block map of logical file byte offset to file system block */ Input : inode, byte offset Output: (1) block number in file system, (2) byte offset into block, (3) bytes of I/O in block, (4) read ahead block number calculate logical block number in file from byte offset; calculate start byte in block for I/O; /* output 2 */ calculate number of bytes to copy to ; /* output 3 */ check if read-ahead applicable, mark inode; /* output 4*/ determine level of indirection; while(not at necessary level of indirection) calculate index into inode or indirect block from logical block number in file; get disk block number from inode or indirect block; release buffer from previous disk read, if any (algorithm brelse); if(no more levels of indirection) return (block number); read indirect disk block (algorithm bread); adjust logical block number in file according to level of indirection; Internal representation of files

28

Block Layout of a Sample File and Its inode 0

4096

228 45423 Byte 9000 in a file -> 8block 808th byte

0 0 11111

367 Data block

0 101 8

367

75 0

0

331

428 (10K+256K) 11

9156

9156 Double indirect

3333

331 Single indirect

816th byte 3333 Data block Byte 350,000 in a file

824 Internal representation of files

29

Unix i-nodes - Example  Byte number 9200 is in direct block 8

#1008th byte in block 367  Byte number 355,000 is calculated as follows: a. 1st byte of the double indirect block is 256k+10k = 272,384 b. byte number 355,000 is number 82,616 in the double indirect block c. every single indirect block has 256k bytes --> byte 355,000 is in the 0th single indirect block - 231 d. Every entry is 1k, so byte 82,616 is in the 80th block - 123 e. within block 123 it is byte #696

228 4542 3 0 1111 0 101 367 0

231

428

80

123

123

231

9156 824

Internal representation of files

367 data block

0

9156 30

Block Entry in the Inode is 0  Logical block entry contain no data.  Process never wrote data into the file at that byte offset

 No disk space is wasted  Cause by using the lseek and write system call

Internal representation of files

31

Two Extensions to the inode Structure  4.2 BSD file system  The more data the kernel can access on the disk in a

single operation, the faster file access becomes  But it increase block fragmentation  Solution : One disk block can contain fragments belonging to several files

 To store file data in the inode  By expanding the inode to occupy an entire disk block  The remainder can store the entire file

Internal representation of files

32

Table of Contents          

Introduction Inodes Structure of a Regular File Directories Conversion of a Path Name to an Inode Super Block Inode Assignment to a New File Allocation of Disk Blocks Other File Types Summary

Internal representation of files

33

Directories  A directory is a file

 Its data is a sequence of entries, each consisting

of an inode number and the name of a file contained in the directory  Path name is a null terminated character string divided by “/”  Each component except the last must be the name of a directory, last component may be a non-directory file

Internal representation of files

34

Directory Layout for /etc Byte Offset in Directory 0 16 32 48 ... 224 240 256

Inode Number (2 bytes) 83 2 1798 1276 ... 0 95 188

Internal representation of files

File Names . .. init fsck … crash mkfs inittab 35

Table of Contents  Introduction  Inodes  Structure of a Regular File  Directories  Conversion of a Path Name to an Inode  Super Block  Inode Assignment to a New File  Allocation of Disk Blocks  Other File Types  Summary Internal representation of files

36

conversion of path name to an inode if (path name starts with root) working inode= root inode

else working inode= current directory inode

while (there is more path name) read next component from input read directory content if (component matches an entry in directory) get inode number for matched component release working inode working inode=inode of matched component else return no inode

return (working inode) Internal representation of files

37

Table of Contents  Introduction  Inodes  Structure of a Regular File  Directories  Conversion of a Path Name to an Inode  Super Block  Inode Assignment to a New File  Allocation of Disk Blocks  Other File Types  Summary

Internal representation of files

38

Super block  File System boot block super block

inode list

data blocks

 Consists of          

the size of the file system the number of free blocks in the file system a list of free blocks available on the file system the index of the next free block in the free block list the size of the inode list the number of free inodes in the file system a list of free inodes in the file system the index of the next free inode in the free inode list lock fields for the free block and free inode lists a flag indicating that the super block has been modified

Internal representation of files

39

Table of Contents  Introduction  Inodes  Structure of a Regular File  Directories  Conversion of a Path Name to an Inode  Super Block  Inode Assignment to a New File  Allocation of Disk Blocks  Other File Types  Summary

Internal representation of files

40

Inode Assignment to a New File  File system contains a linear list of inodes  Inode is free : its type field is zero (0)  Super block contains an array to cache the

numbers of free inodes in the file system (to improve performance)

Internal representation of files

41

Algorithm for Asg New Inodes(1) Algorithm ialloc /* allocate inode */ Input : file system Output : locked inode { while(not done){ if(super block locked) { sleep(event super block becomes free); continue; } if(inode list in super block is empty){ lock super block; get ed inode for free inode search; search disk for free inodes until super block full, or no more free inodes (bread and brelese); unlock super block; wake up (event super block becomes free); if(no free inodes found on disk) return (no inode); set ed inode for next free inode search; }

Internal representation of files

42

Algorithm for Asg New Inodes(2) /* there are inodes in super block inode list */ get inode number from super block inode list; get inode (algorithm iget); if(inode not free after all) { write inode to disk; release inode (algorithm iput); continue; /* while loop */ } /* inode is free */ initialize inode; write inode to disk; decrement file system free inode count; return (inode); } // end of while }

Internal representation of files

43

Asg Free Inode from Middle of List Super Block Free Inode List free inodes 83 18

19

48

empty

20

array

index Super Block Free Inode List free inodes 83 18

empty

19

20

array

index

Internal representation of files

44

Asg Free Inode – Super Block List Empty Super Block Free Inode List 470 empty 0

index

array1 ed inode

Super Block Free Inode List 535 free inodes

0

array2 476 475 471

48

Internal representation of files

49

50

index

45

Algorithm for Freeing Inode Algorithm ifree /* inode free */ Input : file system inode number Output : none { increment file system free inode count; if(super block locked) return; if(inode list full){ if(inode number less than ed inode for search) set ed inode for search = input inode number; } else store inode number in inode list; return; } Internal representation of files

46

Placing Free Inode Numbers Into the Super Block 535 471

476

ed inode

475

free inodes index

Original Super Block List of Free Inodes 499 471

476 475

ed inode

free inodes index Free Inode 499

499 471

476 475

ed inode

free inodes Free Inode 601

Internal representation of files

index

47

Race Condition in Asg Inodes Process A

Process B

Process C

Assigns inode I from super block Sleeps while reading inode(a)

Tries to assign inode from super block Super block empty(b) Search for free inodes on disk, puts inode I in super block (c)

Inode I in core Does usual activity

Completes search, assigns another inode(d)

Assigns inode I from super block I is in use! Assign another inode(e)

Internal representation of files

48

Race Condition in Asg Inodes Time

(a)

(b)

(c)

(d)

(e)

I

empty

Free inodes

Free inodes

Free inodes

Internal representation of files

J

I K

J

I

L

49

Table of Contents  Inodes  Structure of a Regular File  Directories  Conversion of a Path Name to an Inode  Super Block  Inode Assignment to a New File  Allocation of Disk Blocks  Other File Types  Summary Internal representation of files

50

Linked List of Free Disk Block Numbers Super block list

109 106 103 100 ………………………….. 109 211 208 205 202 ……………………

112

211 310 307 304 301

214

……………………

310 409 406 403 400 ……………………

Internal representation of files

313

51

Algorithm for Allocating Disk Block  algorithm alloc - The kernel wants to allocate a block from a file system it allocates the next available block in the super block list - Once allocated , the block cannot be reallocated until it becomes free - If the allocated block is the last block , the kernel treats it as a pointer to a block that contains a list of free blocks • The kernel locks super block, reads block just taken from free list, copies block numbers in block into super block, releases block buffer,and unlocks super block - Otherwise, • The kernels gets buffer for block removed from super block list , zero buffer contents, decrements total count of free blocks, and marks super block modified

Internal representation of files

52

Requesting and Freeing Disk Blocks super block list 109 ………………………………………………………… 109 211 208 112

205 202

……………………………..

original configuration 109 949 ………………………………………………….. 109 211 208 205 202 ………………………………. 112 After freeing block number 949

Internal representation of files

53

Requesting and Freeing Disk Blocks 109 ……………………………………………………….. 109 211 208 112

205 202 ……………………………….

After asg block number(949) 211 208 205 202 ……………………………… 112 211 344 341 338 335 ………………………………. 243 After asg block number(109) replenish super block free list Internal representation of files

54

Table of Contents  Introduction  Inodes  Structure of a regular file  Directories  Conversion of a path name to an Inode  Super block  Inode assignment to a new file  Allocation of disk blocks  Other file types  Summary Internal representation of files

55

Other File Types  Pipe  fifo(first-in-first-out)  Its data is transient: once data is read from a pipe, it cannot be read again  Use only direct block (not the indirect block)  Special file  block device, character device  The inode contains the major and minor device number  Major number indicates a device type such as terminal or disk  Minor number indicates the unit number of the device

Internal representation of files

56

Table of Contents  Introduction  Inodes  Structure of a regular file  Directories  Conversion of a path name to an Inode  Super block  Inode assignment to a new file  Allocation of disk blocks  Other file types  Summary Internal representation of files

57

Summary  Inode is the data structure that describes the attributes of a

file, including the layout of its data on disk.  Two version of the inode  Disk copy : store the inode information when file is not in use  In-core copy : record the information about active files.

   

ialloc/ifree : assignment of a disk inode iget/iput : allocation of in-core inodes bmap : locate disk blocks of a file, according to byte offset Directories : files that correlate file name components to inode numbers  namei : convert file names to inodes  alloc/free : assignment of new disk blocks to a file Internal representation of files

58