rawfs.c

rawfs.c

Skip to line: 8050 - 8100 - 8150 - 8200 - 8250 - 8300

If you have a comment for rawfs.c, please click here.

8000 /* rawfs.c - Raw Minix file system support. Author: Kees J. Bot

8001 * 23 Dec 1991

8002 * Based on readfs by Paul Polderman

8003 */


	Before going through this file, read sections 5.6.2, 5.6.3, and 5.6.4 in Operating Systems. These sections deal with file system fundamentals and describe super blocks, bit maps, zones, and inodes. You're not going to understand rawfs.c until you read these 3 sections (they're only a total of 8 pages anyway). I refer to specific pages from these 3 sections in my comments. The functionality of the boot monitor's file system is a subset of the functionality of the minix OS file system (i.e. the boot monitor's file system is a "raw" file system). For example, a user can't create a new file from the boot monitor. The functionality of the boot monitor's file system is limited to looking up information about files, directories, and the file system itself.

8004 #define nil 0


	`#define` is a preprocessor command. The preprocessor replaces all occurrences of the first string (in this case, "`nil`") with the second string (in this case, "`0`") before compilation. The string "`nil`" is used to increase readability.

8005 #define _POSIX_SOURCE 1

8006 #define _MINIX 1


	`_POSIX_SOURCE` and `_MINIX` are macros that are used by library routines. In fact, nearly all macros that begin with an underscore (`_`) are specific to library routines. The POSIX standard was created to improve portability between UNIX systems. The 12th paragraph of section 2.6.2, lines 01184-011200, and lines 01241-01245 in Operating Systems describe the `_POSIX_SOURCE` and `_MINIX` macros.

8007 #include <sys/types.h>


	A function must be either defined or declared in a file before it can be used. Header files (files ending in .h) make the task of declaring variables easier. Before compilation begins, the preprocessor replaces any `#include <filename.h>` statement with the contents of filename.h. If the filename is enclosed in < and >, the preprocessor searches for the file in a default directory (typically /usr/include) and other directories specified by the -I option of the compiler (see line 8016). If the filename is quoted (see line 8021), the preprocessor looks for the include file in the same directory that the source file is found. (In this case, rawfs.c is the source file and is found in the /usr/src/boot directory.) As an example, `strncpy()` (see line 8188) is declared in the file string.h (see line 8011). string.h is located in the directory /usr/include. Header files, in addition to containing function declarations, also frequently contain `#define`s. For example, `ROOT_INO` (see line 8273) is `#define`d in rawfs.h. Since rawfs.h is quoted (see line 8021), the preprocessor searches for rawfs.h in the same directory as rawfs.c and then the default directories. Indeed, both files are in the /usr/src/boot directory.

8008 #include <sys/stat.h>

8009 #include <stdlib.h>

8010 #include <limits.h>

8011 #include <string.h>

8012 #include <errno.h>

errno is declared in errno.h (see line 00230 in the book) as extern. Memory for a variable can be allocated in only one file (i.e. the variable is "defined") but the variable must be declared as extern in every other file that accesses it. However, memory is not allocated for errno in boothead.s, boot.c, bootimage.c, or rawfs.c. If you understand how memory is allocated for errno, please submit a comment to the site which will be displayed below.

Name: Christos Basil Karayiannis - Karditsa GR

Email: christos@kar.forthnet.gr

Date: Mar 18 2004 15:41:11 GMT

Subject: Where is errno declared?

Reponse: At line 8012 we include header file errno.h. By doing this, we use variables defined at errno.c (/minix/src/lib/other/errno.c). All this file does is declaring errno:

------------------
#include
/* errno.c - declare variable errno
Author: F. Meulenbroeks */

int errno = 0;
------------------


		Respond to Christos Basil Karayiannis - Karditsa GR's comment.

8013 #include <minix/config.h>
8014 #include <minix/const.h>
8015 #include <minix/type.h>

8016 #include <fs/const.h>


	If a filename is enclosed in < and >, the preprocessor searches for the file in the default directory (typically /usr/include) and other directories specified by the -I option of the compiler. In Makefile , the parent directory (..) is specified by the -I option. Makefile is found in /usr/src/boot; therefore, the parent directory is /usr/src. After the preprocessor unsuccessfully looks for const.h in the /usr/include/kernel directory, the preprocessor looks for (and finds) const.h in the /usr/src/fs directory. Note that the preprocessor can't find const.h in /usr/src/fs since this directory doesn't exist.

8017 #include <fs/type.h>

8018 #include <fs/buf.h>


	buf.h (see line 20113 in the book) `#include`s <sys/dir.h> (line 02400 in the book), which declares `struct direct` (see line 8162).

8019 #include <fs/super.h>
8020 #include <fs/inode.h>
8021 #include "rawfs.h"
8022

8023 void readblock(off_t blockno, char *buf);


	`readblock()` is defined in boot.c. Since this is the only function from boot.c that is called from rawfs.c and since `readblock()` isn't declared in boot.h (so we can't just `#include` boot.h), `readblock()` is declared here.

8024

8025 /* The following code handles two file system types: Version 1 with small

8026 * inodes and 16-bit disk addresses and Version 2 with big inodes and 32-bit

8027 * disk addresses.

8028 #ifdef FLEX

8029 * To make matters worse, Minix-vmd knows about the normal Unix Version 7

8030 * directories and directories with flexible entries.

8031 #endif

8032 */


	Read page 459 in Operating Systems to understand the differences between the V1 and V2 file systems. I do not cover sections of code specific to Unix Version 7 (`FLEX`).

8033

8034 /* File system parameters. */

8035 static unsigned nr_dzones; /* Fill these in after reading superblock. */

8036 static unsigned nr_indirects;

8037 static unsigned inodes_per_block;


	The scope of an external `static` variable is only within the file in which the variable is defined. Note that "external" variables are variables that are declared outside of all functions. `nr_dzones`, `nr_indirects`, `inodes_per_block` are set on lines 8071-8073 for the V2 file system and 8077-8079 for the V1 file system. `nr_dzones` is the number of direct zones in an inode and is 7 for both the V1 and V2 file systems (section 5.6.4). `nr_indirects` is the number of zone addresses in an indirect block. A block is 1024 bytes for both the V1 and V2 file systems and zone addresses are 2 bytes for the V1 file system and 4 bytes for the V2 file system. Therefore `nr_indirects` is equal to 512 (1024/2) for the V1 file system and 256 (1024/4) for the V2 file system. A V1 inode is 32 bytes and a V2 inode is 64 bytes; therefore `inodes_per_block` is 32 (1024/32) for the V1 file system and 16 (1024/64) for the V2 file system.

8038 #ifdef FLEX


	I do not cover sections of code specific to Unix Version 7 (`FLEX`).

8039 #include <dirent.h>
8040 #define direct _v7_direct
8041 #else
8042 #include <sys/dir.h>
8043 #endif

8044

8045 static struct super_block super; /* Superblock of file system */ Super blocks are covered in section 5.6.2 and a diagram of the super block is shown in fig. 5-29. super is set on line 8067. struct super_block is declared in fs/super.h (see line 20721 in the book). 8046 static struct inode curfil; /* Inode of file under examination */ Inodes are covered in section 5.6.4 and a diagram of an inode is shown in fig. 5-30. curfil is set in r_stat() (see lines 8111-8120 and 8127-8136) and accessed in r_readdir() (see lines 8164 and 8166) and r_vir2abs() (line 8196). struct inode is declared in fs/inode.h (see line 20510 in the book). 8047 static char indir[BLOCK_SIZE]; /* Single indirect block. */ 8048 static char dindir[BLOCK_SIZE]; /* Double indirect block. */ Fig. 5-10 in section 5.3.1 describes single and double indirect blocks. Since a block is 1024 bytes (BLOCK_SIZE=1024) and each zone address is 2 bytes (V1 file system) or 4 bytes (V2 file system), indir[] and dindir[] hold 256 zone addresses (V1 file system) or 512 zone addresses (V2 file system). Both indir[] and dindir[] are set in r_vir2abs() (see lines 8251 and 8234) and are used in conjunction with a_indir and a_dindir (line 8052). 8049 static char dirbuf[BLOCK_SIZE]; /* Scratch/Directory block. */ 8050 #define scratch dirbuf dirbuf[] is used in several functions as a scratch buffer (see lines 8067 and 8103). 8051 8052 static block_t a_indir, a_dindir; /* Addresses of the indirects. */ a_indir is the block number of the block that was last read into indir[] (line 8047) and d_dindir is the block number of the block that was last read into dindir[] (line 8048). 8053 static off_t dirpos; /* Reading pos in a dir. */ Each call to r_readdir() reads a directory entry and advances to the next entry (see line 8191). dirpos keeps track of the current directory entry. 8054 8055 #define fsbuf(b) (* (struct buf *) (b)) The macro fsbuf() is used (and explained) in r_stat() (line 8087) and r_vir2abs() (line 8196) 8056 8057 #define zone_shift (super.s_log_zone_size) /* zone to block ratio */ The default for the minix file systems is 1 block per zone. Read section 5.6.3 for the motivation behind zones. 8058 8059 off_t r_super(void) 8060 /* Initialize variables, return size of file system in blocks, 8061 * (zero on error). 8062 */ r_super() fills in super (line 8045), sets the variables n_dzones, nr_indirects, and inodes_per_block, and returns the number of blocks in the file system. 8063 { 8064 /* Read superblock. */ 8065 readblock(SUPER_BLOCK, scratch); 8066 8067 memcpy(&super, scratch, sizeof(super)); BOOT_BLOCK (=0) and SUPER_BLOCK (=1) are #defined in <fs/const.h> (see lines 19560-19561 in the book). The boot block is the first block in a bootable partition or subpartition and the super block is the second block in a bootable partition or subpartition (see fig. 5-28 in the book). The super block is read into scratch (see lines 8049-8050) and then the first sizeof(super) bytes of the super block is copied to super (see line 8067). void *memcpy(void *s1, void *s2, size_t n) copies n characters from the address s2 to the address s1 and returns s1. 8068 8069 /* Is it really a MINIX file system ? */ nr_dzones (line 8035) is the number of direct zones in an inode and is 7 for both the V1 and V2 file systems (section 5.6.4). nr_indirects (line 8036) is the number of zone addresses in an indirect block. A block is 1024 bytes for both the V1 and V2 file systems and zone addresses are 2 bytes for the V1 file system and 4 bytes for the V2 file system. So nr_indirects is equal to 512 (1024/2) for the V1 file system and 256 (1024/4) for the V2 file system. A V1 inode is 32 bytes and a V2 inode is 64 bytes; therefore inodes_per_block (line 8037) is 32 (1024/32) for the V1 file system and 16 (1024/64) for the V2 file system. super.s_zones (for the V2 file system) and super.s_nzones (for the V1 file system) are the respective sizes (in zones) of V2 and V1 file systems. All the macros on lines 8070-8079 are #defined in <fs/const.h> (line 19500 in the book). 8070 if (super.s_magic == SUPER_V2) { 8071 nr_dzones= V2_NR_DZONES; 8072 nr_indirects= V2_INDIRECTS; 8073 inodes_per_block= V2_INODES_PER_BLOCK; 8074 return (off_t) super.s_zones << zone_shift; 8075 } else 8076 if (super.s_magic == SUPER_MAGIC) { 8077 nr_dzones= V1_NR_DZONES; 8078 nr_indirects= V1_INDIRECTS; 8079 inodes_per_block= V1_INODES_PER_BLOCK; 8080 return (off_t) super.s_nzones << zone_shift; 8081 } else { 8082 /* Filesystem not recognized as Minix. */ 8083 return 0; 8084 } 8085 } 8086 8087 void r_stat(Ino_t inum, struct stat *stp) 8088 /* Return information about a file like stat(2) and remember it. */ r_stat() returns information about the file or directory with inode number inum in *stp and "remembers" the information in inode curfil (line 8046). The strategy is typically to call r_stat() and then call either r_readdir() (line 8157) or r_vir2abs() (line 8196) to give additional information about curfil. 8089 { 8090 block_t block; 8091 block_t ino_block; 8092 ino_t ino_offset; 8093 8094 /* Calculate start of i-list */ 8095 block = SUPER_BLOCK + 1 + super.s_imap_blocks + super.s_zmap_blocks; Fig. 5-28 describes the disk layout; the order is: 1) the boot block 2) the super block 3) the inode bit maps (one or more blocks) 4) the zone bit maps (one or more blocks) 5) inodes 6) data As an example, suppose a V2 file system (inodes_per_block=16) has 4 blocks of inode bit maps (super.s_imap_blocks=4) and 5 blocks of zone bit maps (super.s_zmap_blocks=5) and inum is 54. block = SUPER_BLOCK + 1 + super.s_imap_blocks + super.s_zmap_blocks = 1 + 1 + 4 + 5 = 11 block is the block number (0-indexed) in the booted partition where the first block containing inodes can be found. 8096 8097 /* Calculate block with inode inum */ 8098 ino_block = ((inum - 1) / inodes_per_block); 8099 ino_offset = ((inum - 1) % inodes_per_block); 8100 block += ino_block; Continuing from lines 8094-8095 with our example: ino_block = ((54-1)/16)=(53/16)=3 (remember - it's integer math) ino_offset = ((54-1)%16)=(53%16)=5 block = block+ino_block=11+3 block is the block number (0-indexed) in the booted partition where the inode inum=54 can be found. 8101 8102 /* Fetch the block */ 8103 readblock(block,scratch); block is read into scratch (see lines 8049-8050). This block contains either 16 inodes (V2 file system) or 32 inodes (V1 file system). A pointer to the struct inode (see line 20510 in the book) corresponding to inum is found on lines 8109 (V2 file system) and 8125 (V1 file system). 8104 8105 if (super.s_magic == SUPER_V2) { 8106 d2_inode *dip; super must be set by r_super() (see line 8067) before r_stat() can be called. In memory, an inode from a V1 file system and an inode from a V2 file system are both stored in a struct inode (see line 20510 in the book). On disk, an inode from a V1 file system is stored in a struct d1_inode (see line 19600 in the book) and an inode from a V2 file system is stored in a struct d2_inode (see line 19611 in the book). Whether the inode corresponding to inum is from a V1 file system or a V2 file system, its inode information is copied to curfil. I do not understand why d2_inode is not preceded by the keyword struct. If you understand why this keyword can be omited, please submit a comment to the site which will be displayed below. Name: Christos Karayiannis Email: christos@nospamkar.forthnet.gr (remove "nospam") Date: Dec 01 2003 14:08:01 GMT Subject: Why d2_inode is not preceded by the keyword struct Reponse: When a struct is declared e.g. struct date{int month, day, year;} d; we define variable d of type struct date. One other option is to declare it as: typedef struct date{int month, day, year;} d; so that d, now a new variable type (and not a variable) is defined. Now we can use the new type (d) to declare other variables e.g. variable x as: d x; Respond to Christos Karayiannis's comment. Name: Brad Zhu Email: zlmblue@nospam163.net (remove "nospam") Date: Dec 08 2003 15:02:52 GMT Subject: no subject Reponse: struct d1_inode and d2_inode are declarated in : /* Declaration of the V1 inode as it is on the disk (not in core). */ typedef struct { /* V1.x disk inode */ mode_t d1_mode; /* file type, protection, etc. */ uid_t d1_uid; /* user id of the file's owner */ off_t d1_size; /* current file size in bytes */ time_t d1_mtime; /* when was file data last changed */ gid_t d1_gid; /* group number */ nlink_t d1_nlinks; /* how many links to this file */ u16_t d1_zone[V1_NR_TZONES]; /* block nums for direct, ind, and dbl ind */ } d1_inode; /* Declaration of the V2 inode as it is on the disk (not in core). */ typedef struct { /* V2.x disk inode */ mode_t d2_mode; /* file type, protection, etc. */ u16_t d2_nlinks; /* how many links to this file. HACK! */ uid_t d2_uid; /* user id of the file's owner. */ u16_t d2_gid; /* group number HACK! */ off_t d2_size; /* current file size in bytes */ time_t d2_atime; /* when was file data last accessed */ time_t d2_mtime; /* when was file data last changed */ time_t d2_ctime; /* when was inode data last changed */ zone_t d2_zone[V2_NR_TZONES]; /* block nums for direct, ind, and dbl ind */ } d2_inode; Respond to Brad Zhu's comment. 8107 int i; 8108 8109 dip= &fsbuf(scratch).b_v2_ino[ino_offset]; The pointer manipulations for the fsbuf() macro (line 8055) are difficult. fsbuf(scratch).b_v2_ino[ino_offset] is a struct d2_inode. &fsbuf(scratch).b_v2_ino[ino_offset] is the memory address of this struct d2_inode. dip= &fsbuf(scratch).b_v2_ino[ino_offset] dip= &(fsbuf(scratch).b_v2_ino[ino_offset]) ("." has higher precedence than "&") dip= &((* (struct buf *)(scratch)).b_v2_ino[ino_offset]) (expansion of fsbuf()) Let's replace this line of code: dip= &fsbuf(scratch).b_v2_ino[ino_offset] with several lines of code: struct buf *buf_ptr, buf1; d2_inode ino1; buf_ptr= (struct buf *)(scratch); buf1= *buf_ptr; ino1= buf1.b_v2_ino[ino_offset]; dip= &ino1; Note that this code is slow and wastes memory. In particular, the 2 lines buf_ptr= (struct buf *)(scratch); buf1= *buf_ptr; copy scratch (which has a size of 1024 bytes) to buf1; this copy was unnecessary in the original code. However, this new code accomplishes the same thing as the original code and since the code is broken down into several steps, it may help you to understand fsbuf(). struct buf (line 20115 in the book) contains a union. A union is a variable that can hold (at different times) objects of different types and sizes. A union is large enough to hold the largest type. For example, a long or a pointer (but only one at a time) can be stored in the following union: union { long long1; char *s1; } union1; and the members can be accessed in the following manner: union1.s1 = "hello"; union1.long1 = 50L; Note that after the second assignment (union1.long1 = 50L), union1 holds the long but no longer holds the pointer. 8110 8111 curfil.i_mode= dip->d2_mode; i_mode specifies the access rights (rwx bits) and the inode type (regular file, directory, special file, etc.). 8112 curfil.i_nlinks= dip->d2_nlinks; A (hard) link in minix (and Unix) is a file (or directory) that has a different name but refers to the same inode. When a file (or directory) is created, i_nlinks is equal to 1. Each additional link increments i_nlinks. Removing links or removing the original file or directory decrements i_nlinks. Only when i_nlinks equals 0 is the inode removed. 8113 curfil.i_uid= dip->d2_uid; 8118 curfil.i_gid= dip->d2_gid; i_uid and i_gid specify the user and group id of the inode owner. 8115 curfil.i_size= dip->d2_size; i_size is the size of the file or directory in bytes. 8116 curfil.i_atime= dip->d2_atime; 8117 curfil.i_mtime= dip->d2_mtime; 8117 curfil.i_ctime= dip->d2_ctime; i_atime is the time (in seconds since Jan. 1, 1970) of the last access of the file or directory. i_mtime is the time (in seconds since Jan. 1, 1970) of the last modification of the file or directory. i_ctime is the time (in seconds since Jan. 1, 1970) of the last change to the inode itself. 8119 for (i= 0; i < V2_NR_TZONES; i++) 8120 curfil.i_zone[i]= dip->d2_zone[i]; i_zone[] contains the 7 direct zones, the single indirect zone, and the double indirect zone (read section 5.6.4 in Operating Systems for details). 8121 } else { 8122 d1_inode *dip; 8123 int i; 8124 8125 dip= &fsbuf(scratch).b_v1_ino[ino_offset]; 8126 8127 curfil.i_mode= dip->d1_mode; 8128 curfil.i_nlinks= dip->d1_nlinks; 8129 curfil.i_uid= dip->d1_uid; 8130 curfil.i_gid= dip->d1_gid; 8131 curfil.i_size= dip->d1_size; 8132 curfil.i_atime= dip->d1_mtime; 8133 curfil.i_mtime= dip->d1_mtime; 8134 curfil.i_ctime= dip->d1_mtime; In memory, an inode from a V1 file system and an inode from a V2 file system are both stored in a struct inode (see line 20510 in the book). On disk, an inode from a V1 file system is stored in a struct d1_inode (see line 19600 in the book) and an inode from a V2 file system is stored in a struct d2_inode (see line 19611 in the book). Since the i_atime and i_ctime fields of struct inode don't have counterparts in struct d2_inode, the time of last modification (d1_mtime) is used for both. Obviously, this isn't ideal but it works well enough. 8135 for (i= 0; i < V1_NR_TZONES; i++) 8136 curfil.i_zone[i]= dip->d1_zone[i]; 8137 } 8138 curfil.i_dev= -1; /* Can't fill this in alas. */ I'm not sure why curfil.i_dev can't be set. If you understand, please send an e-mail to feedback@swartzbaugh.net. 8139 curfil.i_num= inum; 8140 8141 stp->st_dev= curfil.i_dev; r_stat() returns information about the file or directory with inode number inum in *stp. 8142 stp->st_ino= curfil.i_num; 8143 stp->st_mode= curfil.i_mode; 8144 stp->st_nlink= curfil.i_nlinks; 8145 stp->st_uid= curfil.i_uid; 8146 stp->st_gid= curfil.i_gid; 8147 stp->st_rdev= (dev_t) curfil.i_zone[0]; i_zone[0] typically holds the first zone that belongs to the inode. However, if the inode describes a special block or character file, i_zone[0] holds the (major, minor) numbers of the device. Read section 5.6.9 (beginning with the 4th paragraph) in Operating Systems. 8148 stp->st_size= curfil.i_size; 8149 stp->st_atime= curfil.i_atime; 8150 stp->st_mtime= curfil.i_mtime; 8151 stp->st_ctime= curfil.i_ctime; 8152 8153 a_indir= a_dindir= 0; 8154 dirpos= 0; a_indir and a_dindir are initialized in anticipation of the next call to vir2abs() (line 8196). dirpos is initialized in anticipation of the next call to r_readdir() (line 8157). 8155 } 8156 8157 ino_t r_readdir(char *name) 8158 /* Read next directory entry at "dirpos" from file "curfil". */ Before r_readdir() is called, r_stat() (line 8087) fills in curfil (line 8046) with information from a directory's inode and initializes dirpos to 0 (see line 8154). If curfil is not a directory, r_readdir() returns immediately (see line 8164). r_readdir() reads a directory entry and returns the entry's inode number and returns the name of the inode entry in *name. r_readdir() also updates dirpos (see line 8191) so that the next call to r_readdir() reads the next entry. r_readdir() returns 0 after it has read all the directory entries. Directories are explained in sections 5.3.2 ("Directories in UNIX") and 5.6.6 in Operating Systems. 8159 { 8160 ino_t inum= 0; 8161 int blkpos; 8162 struct direct *dp; struct direct is declared in <sys/dir.h> (see line 02411 in the book). 2 bytes are reserved for the inode number and 14 bytes are reserved for the name (minix file and directory names can be 14 characters long). 8163 8164 if (!S_ISDIR(curfil.i_mode)) { errno= ENOTDIR; return -1; } S_ISDIR() returns TRUE if curfil is a directory. S_ISDIR() is #defined in stat.h (see line 02355 in the book). 8165 8166 while (inum == 0 && dirpos < curfil.i_size) { This while loop reads in a new block (if necessary) of directory entries and extracts the name and inode number of the entry corresponding to dirpos. The name of the entry is copied to name (see lines 8188-8189) and inum is set to the inode number (see line 8186). If the directory entry corresponding to dirpos is empty, r_readdir() returns 0. 8167 if ((blkpos= (int) (dirpos % BLOCK_SIZE)) == 0) { dirpos is the offset from the beginning of the first directory block; blkpos is the offset from the beginning of the current directory block. 8168 /* Need to fetch a new directory block. */ 8169 8170 readblock(r_vir2abs(dirpos / BLOCK_SIZE), dirbuf); void readblock(off_t blk, char *buf) reads blk into the buffer buf. Note that blk is not an absolute block on the hard drive; blk is the offset (in blocks) from the beginning of the partition. off_t r_vir2abs(off_t virblk) translates virblk, a block number within curfil, to a block number within the partition. 8171 } 8172 #ifdef FLEX I do not cover sections of code specific to Unix Version 7 (FLEX). 8173 if (super.s_flags & S_FLEX) { 8174 struct _fl_direct *dp; 8175 8176 dp= (struct _fl_direct *) (dirbuf + blkpos); 8177 if ((inum= dp->d_ino) != 0) strcpy(name, dp->d_name); 8178 8179 dirpos+= (1 + dp->d_extent) * FL_DIR_ENTRY_SIZE; 8180 continue; 8181 } 8182 #endif 8183 /* Let dp point to the next entry. */ 8184 dp= (struct direct *) (dirbuf + blkpos); dp points to the current directory entry. blkpos was set on line 8167. 8185 8186 if ((inum= dp->d_ino) != 0) { 8187 /* This entry is occupied, return name. */ 8188 strncpy(name, dp->d_name, sizeof(dp->d_name)); char *strncpy(char *s1,char *s2, size_t n) copies the first n characters of string s2 to string s1. 8189 name[sizeof(dp->d_name)]= 0; Don't forget the terminating 0. 8190 } 8191 dirpos+= DIR_ENTRY_SIZE; DIR_ENTRY_SIZE is #defined in <fs/const.h> as usizeof(struct direct) (see line 19563). struct direct is 16 bytes - 2 bytes for the inode number and 14 bytes for the name of the directory entry. 8192 } 8193 return inum; 8194 } 8195 8196 off_t r_vir2abs(off_t virblk) 8197 /* Translate a block number in a file to an absolute disk block number. 8198 * Returns 0 for a hole and -1 if block is past end of file. 8199 */ off_t r_vir2abs(off_t virblk) translates virblk, a block number within curfil (line 8046), to a block number offset within the partition. curfil is previously set by r_stat() (line 8087). Note that the returned value for r_vir2abs() is not an "absolute disk block number" but rather a block number offset within a partition. For example, if the first block of the partition is 550, then a return value of 100 corresponds to an absolute disk block number of 650. In order to understand r_vir2abs(), you must first read sections 5.6.3 and 5.6.4 in Operating Systems. The best way to explain r_vir2abs() is with an example. Assume curfil is a large file and that we wish to translate block number 3111 within curfil (virblk=3111) to a block number offset within the partition. Also assume that this is a V2 file system and that there are 4 blocks per zone (zone_shift=2 - see line 8057). (This is not the default; the default for minix is 1 block per zone.) Please understand that r_vir2abs() is a difficult function; trying to understand this function will likely give you a headache. 8200 { 8201 block_t b= virblk; It's unclear why another variable is introduced, since virblk could be used instead of b. 8202 zone_t zone, ind_zone; 8203 block_t z, zone_index; 8204 int i; 8205 8206 /* Check if virblk within file. */ 8207 if (virblk * BLOCK_SIZE >= curfil.i_size) return -1; i_size is the size (in bytes) of the file. BLOCK_SIZE (=1024) is #defined in <minix/const.h> (see line 02915 in the book). 8208 8209 /* Calculate zone in which the datablock number is contained */ 8210 zone = (zone_t) (b >> zone_shift); zone = 3111 >> 2 = 110000100111 >> 2 = 1100001001 = 777 8211 8212 /* Calculate index of the block number in the zone */ 8213 zone_index = b - ((block_t) zone << zone_shift); zone_index = 3111 - (777 << 2) = 3111 - 3108 = 3 8214 8215 /* Go get the zone */ 8216 if (zone < (zone_t) nr_dzones) { /* direct block */ nr_dzones = 7 (see line 8071) Since 777 is not less than 7, the if block is not executed. 8217 zone = curfil.i_zone[(int) zone]; 8218 z = ((block_t) zone << zone_shift) + zone_index; 8219 return z; 8220 } 8221 8222 /* The zone is not a direct one */ 8223 zone -= (zone_t) nr_dzones; zone = zone - nr_dzones = 777 - 7 = 770 8224 8225 /* Is it single indirect ? */ 8226 if (zone < (zone_t) nr_indirects) { /* single indirect block */ nr_indirects = 256 (for the V2 file system - see line 8072) Since 770 is not less than 256, the else block is executed. 8227 ind_zone = curfil.i_zone[nr_dzones]; 8228 } else { /* double indirect block */ 8229 /* Fetch the double indirect block */ 8230 if ((ind_zone = curfil.i_zone[nr_dzones + 1]) == 0) return 0; ind_zone = curfil.i_zone[nr_dzones + 1] = curfil.i_zone[7 + 1] = curfil.i_zone[8] In figure 5-30 in the book, i_zone[8] corresponds to the field "Double indirect zone". Obviously, if there is a block 3111 in curfil, this field should not be equal to 0. According to the figure, ind_zone = 68. The first block of this zone contains a double indirect block - we need to read this block into dindir[] (see line 8234). 8231 8232 z = (block_t) ind_zone << zone_shift; z = 68 << 2 = 272 Note that z is a block number, not a zone number. The name z is unfortunate. 8233 if (a_dindir != z) { a_dindir (line 8052) is the block number of the block that was previously read into dindir[] (see line 8235). (In other words, a_dindir and dindir[] together are a cache.) If a_dindir equals z, dindir[] already contains block z so there's no need to read the block again. When r_vir2abs() is called for the first time, dindir[] is empty and a_dindir equals 0. 8234 readblock(z, dindir); void readblock(off_t blk, char *buf) reads blk into the buffer buf. Note that blk is not an absolute block on the hard drive; blk is the offset (in blocks) from the beginning of the partition. 8235 a_dindir= z; 8236 } 8237 /* Extract the indirect zone number from it */ 8238 zone -= (zone_t) nr_indirects; Block 3111 is in a zone that is found in the double indirect block. On line 8223 we subtracted the number of direct zones in the inode and here we subtract the number of zones in the single indirect block. (Remember, the 8th zone in a file is the first zone in the single indirect block and the (8+256=) 264th zone is the first zone covered by the double indirect block.) zone = zone - nr_indirects = 770 - 256 = 514 8239 8240 i = zone / (zone_t) nr_indirects; i = 514 / 256 = 2 (remember, it's integer math) 8241 ind_zone = super.s_magic == SUPER_V2 8242 ? fsbuf(dindir).b_v2_ind[i] 8243 : fsbuf(dindir).b_v1_ind[i]; For a full explanation of the fsbuf() macro, see the comments for line 8109. I use the same approach to explaining fsbuf()as on line 8109. Since our example is for the V2 file system: ind_zone = fsbuf(dindir).b_v2_ind[i]; ind_zone = (* (struct buf *))(dindir).b_v2_ind[i]; Again, this alternative code is inefficient and shouldn't normally be used, but this code might help you to understand the complicated pointer assignment of the original code. struct buf buf1, *buf_ptr; buf_ptr= (struct buf *)(dindir); buf1= *buf_ptr; ind_zone= buf1.b_v2_ind[i]; For our example (i=2), ind_zone= (* (struct buf *))(dindir).b_v2_ind[2] ind_zone= 504 8244 zone %= (zone_t) nr_indirects; Block 3111 is found in the 3rd single indirect block covered by the double indirect block. On line 8223 we subtracted the number of direct zones in the inode and we subtract on line 8238 the number of zones in the single indirect block. Here we must subtract the 2 previous single indirect blocks covered by the double indirect block. zone = zone % nr_indirects = 514 % 256 = 2 (Remember 11 % 3 = 2; % is the modulus operator.) 8245 } 8246 if (ind_zone == 0) return 0; If ind_zone equals 0, there is a hole in the file. 8247 8248 /* Extract the datablock number from the indirect zone */ 8249 z = (block_t) ind_zone << zone_shift; z = 504 << 2 = 2016 8250 if (a_indir != z) { a_indir (line 8052) is the block number of the block that was previously read into indir[] (see line 8252). (In other words, a_indir and indir[] together are a cache.) If a_indir equals z, indir[] already contains block z so there's no need to read the block again. When r_vir2abs() is called for the first time, indir[] is empty and a_indir equals 0. 8251 readblock(z, indir); void readblock(off_t blk, char *buf) reads blk into the buffer buf. Note that blk is not an absolute block on the hard drive; blk is the offset (in blocks) from the beginning of the partition. 8252 a_indir= z; 8253 } 8254 zone = super.s_magic == SUPER_V2 For a full explanation of the fsbuf() macro, see the comments for line 8109. Here I use the same approach to explaining fsbuf() as on line 8109. Since our example is for the V2 file system: zone = fsbuf(indir).b_v2_ind[zone]; zone = (* (struct buf *))(indir).b_v2_ind[zone]; Again, this alternative code is inefficient and shouldn't normally be used, but this code might help you to understand the complicated pointer assignment of the original code. struct buf buf1, *buf_ptr; buf_ptr= (struct buf *)(indir); buf1= *buf_ptr; zone= buf1.b_v2_ind[zone]; For our example (zone=2), zone= (* (struct buf *))(indir).b_v2_ind[2] zone= 2519 8255 ? fsbuf(indir).b_v2_ind[(int) zone] 8256 : fsbuf(indir).b_v1_ind[(int) zone]; 8257 8258 /* Calculate absolute datablock number */ 8259 z = ((block_t) zone << zone_shift) + zone_index; 8260 return z; z = (2519 << 2) + 3 = 10076 + 3 = 10079 Block number 3111 in curfil corresponds to block number 10079 in the partition. zone_index = 3 (see line 8213) 8261 } 8262 8263 ino_t r_lookup(Ino_t cwd, char *path) 8264 /* Translates a pathname to an inode number. This is just a nice utility 8265 * function, it only needs r_stat and r_readdir. 8266 */ r_lookup() translates either an absolute path (for example, "/dir1/dir2/file1") or a relative path (for example, "dir2/file1") to an inode number. cwd, the inode number for the current working directory (cwd), must be given for relative paths. If file1 refers to the same file in the previous two examples, cwd must be the inode number for dir1. If path is an absolute path, cwd is not used. r_lookup() works its way through the path. For example, if path is "/dir1/dir2/file1", r_lookup() first looks for the entry "dir1" in the root directory, "/". If r_lookup() finds "dir1", it next looks for the entry "dir2" in directory "dir1". If it finds "dir2", it next looks for the entry "file1" in the directory "dir2". If it finds "file1" and determines that "file1" is at the end of path, it returns the inode number for "file1". Note that r_lookup() can also look up directories. For example, if path is "/dir1/dir2/", r_lookup() will return the inode number for dir2. 8267 { 8268 char name[NAME_MAX+1], r_name[NAME_MAX+1]; name[] (see line 8294) holds a single directory name or file name of path. For example, if path is "/dir1/dir2/file1", name[] first holds "dir1", then "dir2", and finally "file1". r_readdir() (see line 8297) returns the names of directory entries, one at a time, in r_name[]. The "+1" is for the terminating 0. 8269 char *n; 8270 struct stat st; struct stat is a subset of struct inode (see line 20510 in the book) and therefore describes a file or directory. struct stat is declared in stat.h (see line 02300 in the book). 8271 ino_t ino; 8272 8273 ino= path[0] == '/' ? ROOT_INO : cwd; If the first character of path is a '/', path is an absolute path and r_lookup() begins by searching the root directory. If the first character of path is not a '/', path is a relative path and r_lookup() begins by searching the current working directory (cwd). ROOT_INO (=1) is the inode of the root directory, '/' and is #defined in rawfs.h. 8274 8275 for (;;) { 8276 if (ino == 0) { An inode number of 0 indicates an error - in this case, that a directory (or the file) in path does not exist. 8277 errno= ENOENT; ENOENT is reported by unix_err() . 8278 return 0; 8279 } 8280 8281 while (*path == '/') path++; The path "/dir1/dir2/file1" is functionally the same as the path "///dir1///////dir2//file1". 8282 8283 if (*path == 0) return ino; r_lookup() returns here if the lookup was successful. 8284 8285 r_stat(ino, &st); r_stat() (line 8087) returns information about the file or directory with inode number ino in st and "remembers" the information in inode curfil (line 8046). readdir() (see line 8297) is then repeatedly called to go through the directory entries of curfil. Note that curfil is a directory unless something is wrong. 8286 8287 if (!S_ISDIR(st.st_mode)) { If file1 is a file, the path "/dir1/file1/dir2/file2" is illegal. This if statement catches this error. S_ISDIR() returns TRUE if st is a directory. S_ISDIR() is #defined in stat.h (see line 02355 in the book). 8288 errno= ENOTDIR; ENOTDIR is reported by unix_err(). 8289 return 0; 8290 } 8291 8292 n= name; 8293 while (*path != 0 && *path != '/') 8294 if (n < name + NAME_MAX) *n++ = *path++; name[] is set to the current node in path. For example, if path is "/dir1/dir2/file1", name[] is initially "dir1", then "dir2", and then "file1". 8295 *n= 0; Don't forget the terminating 0. 8296 8297 while ((ino= r_readdir(r_name)) != 0 8298 && strcmp(name, r_name) != 0) {} Before r_readdir() (line 8157) is called, r_stat() (see line 8285) fills in curfil (line 8046) with information from a directory's inode and initializes dirpos to 0 (see line 8154). r_readdir() reads a directory entry and returns the entry's inode number in ino and returns the name of the inode entry in r_name[]. r_readdir() also updates dirpos (see line 8191) so that the next call to r_readdir() reads the next entry. r_readdir() returns 0 after it has read all the directory entries. Directories are explained in sections 5.3.2 ("Directories in UNIX") and 5.6.6 in Operating Systems. The current node is in name[] (see lines 8292-8294). r_readdir() reads directory entries into r_name[] until a match with name[] occurs or until it has read all the directory entries. 8299 } 8300 } end of fileback up


	Super blocks are covered in section 5.6.2 and a diagram of the super block is shown in fig. 5-29. `super` is set on line 8067. `struct super_block` is declared in fs/super.h (see line 20721 in the book).


	Inodes are covered in section 5.6.4 and a diagram of an inode is shown in fig. 5-30. `curfil` is set in `r_stat()` (see lines 8111-8120 and 8127-8136) and accessed in `r_readdir()` (see lines 8164 and 8166) and `r_vir2abs()` (line 8196). `struct inode` is declared in fs/inode.h (see line 20510 in the book).


	Fig. 5-10 in section 5.3.1 describes single and double indirect blocks. Since a block is 1024 bytes (`BLOCK_SIZE`=1024) and each zone address is 2 bytes (V1 file system) or 4 bytes (V2 file system), `indir[]` and `dindir[]` hold 256 zone addresses (V1 file system) or 512 zone addresses (V2 file system). Both `indir[]` and `dindir[]` are set in `r_vir2abs()` (see lines 8251 and 8234) and are used in conjunction with `a_indir` and `a_dindir` (line 8052).


	`dirbuf[]` is used in several functions as a scratch buffer (see lines 8067 and 8103).


	`a_indir` is the block number of the block that was last read into `indir[]` (line 8047) and `d_dindir` is the block number of the block that was last read into `dindir[]` (line 8048).


	Each call to `r_readdir()` reads a directory entry and advances to the next entry (see line 8191). `dirpos` keeps track of the current directory entry.


	The macro `fsbuf()` is used (and explained) in `r_stat()` (line 8087) and `r_vir2abs()` (line 8196)


	The default for the minix file systems is 1 block per zone. Read section 5.6.3 for the motivation behind zones.


	`r_super()` fills in `super` (line 8045), sets the variables `n_dzones`, `nr_indirects`, and `inodes_per_block`, and returns the number of blocks in the file system.


	`BOOT_BLOCK` (=0) and `SUPER_BLOCK` (=1) are `#define`d in <fs/const.h> (see lines 19560-19561 in the book). The boot block is the first block in a bootable partition or subpartition and the super block is the second block in a bootable partition or subpartition (see fig. 5-28 in the book). The super block is read into `scratch` (see lines 8049-8050) and then the first `sizeof(super)` bytes of the super block is copied to `super` (see line 8067). `void memcpy(void s1, void *s2, size_t n)` copies `n` characters from the address `s2` to the address `s1` and returns `s1`.


	`nr_dzones` (line 8035) is the number of direct zones in an inode and is 7 for both the V1 and V2 file systems (section 5.6.4). `nr_indirects` (line 8036) is the number of zone addresses in an indirect block. A block is 1024 bytes for both the V1 and V2 file systems and zone addresses are 2 bytes for the V1 file system and 4 bytes for the V2 file system. So `nr_indirects` is equal to 512 (1024/2) for the V1 file system and 256 (1024/4) for the V2 file system. A V1 inode is 32 bytes and a V2 inode is 64 bytes; therefore `inodes_per_block` (line 8037) is 32 (1024/32) for the V1 file system and 16 (1024/64) for the V2 file system. `super.s_zones` (for the V2 file system) and `super.s_nzones` (for the V1 file system) are the respective sizes (in zones) of V2 and V1 file systems. All the macros on lines 8070-8079 are `#define`d in <fs/const.h> (line 19500 in the book).


	`r_stat()` returns information about the file or directory with inode number `inum` in `*stp` and "remembers" the information in `inode curfil` (line 8046). The strategy is typically to call `r_stat()` and then call either `r_readdir()` (line 8157) or `r_vir2abs()` (line 8196) to give additional information about `curfil`.


	Fig. 5-28 describes the disk layout; the order is: 1) the boot block 2) the super block 3) the inode bit maps (one or more blocks) 4) the zone bit maps (one or more blocks) 5) inodes 6) data As an example, suppose a V2 file system (`inodes_per_block`=16) has 4 blocks of inode bit maps (`super.s_imap_blocks`=4) and 5 blocks of zone bit maps (`super.s_zmap_blocks`=5) and `inum` is 54. `block = SUPER_BLOCK + 1 + super.s_imap_blocks + super.s_zmap_blocks = 1 + 1 + 4 + 5 = 11` `block` is the block number (0-indexed) in the booted partition where the first block containing inodes can be found.


	Continuing from lines 8094-8095 with our example: `ino_block = ((54-1)/16)=(53/16)=3` (remember - it's integer math) `ino_offset = ((54-1)%16)=(53%16)=5` `block = block+ino_block=11+3` `block` is the block number (0-indexed) in the booted partition where the inode `inum`=54 can be found.


	`block` is read into `scratch` (see lines 8049-8050). This block contains either 16 inodes (V2 file system) or 32 inodes (V1 file system). A pointer to the `struct inode` (see line 20510 in the book) corresponding to `inum` is found on lines 8109 (V2 file system) and 8125 (V1 file system).


	The pointer manipulations for the `fsbuf()` macro (line 8055) are difficult. `fsbuf(scratch).b_v2_ino[ino_offset]` is a `struct d2_inode`. `&fsbuf(scratch).b_v2_ino[ino_offset]` is the memory address of this `struct d2_inode`. `dip= &fsbuf(scratch).b_v2_ino[ino_offset]` `dip= &(fsbuf(scratch).b_v2_ino[ino_offset])` ("`.`" has higher precedence than "`&`") `dip= &((* (struct buf )(scratch)).b_v2_ino[ino_offset])` (expansion of `fsbuf()`) Let's replace this line of code: `dip= &fsbuf(scratch).b_v2_ino[ino_offset]` with several lines of code: `struct buf buf_ptr, buf1;` `d2_inode ino1;` `buf_ptr= (struct buf )(scratch);` `buf1= buf_ptr;` `ino1= buf1.b_v2_ino[ino_offset];` `dip= &ino1;` Note that this code is slow and wastes memory. In particular, the 2 lines `buf_ptr= (struct buf )(scratch);` `buf1= buf_ptr;` copy `scratch` (which has a size of 1024 bytes) to `buf1`; this copy was unnecessary in the original code. However, this new code accomplishes the same thing as the original code and since the code is broken down into several steps, it may help you to understand `fsbuf()`. `struct buf` (line 20115 in the book) contains a `union`. A `union` is a variable that can hold (at different times) objects of different types and sizes. A `union` is large enough to hold the largest type. For example, a `long` or a pointer (but only one at a time) can be stored in the following `union`: `union {` `long long1;` `char *s1;` `} union1;` and the members can be accessed in the following manner: `union1.s1 = "hello";` `union1.long1 = 50L;` Note that after the second assignment (`union1.long1 = 50L`), `union1` holds the `long` but no longer holds the pointer.


	`i_mode` specifies the access rights (rwx bits) and the inode type (regular file, directory, special file, etc.).


	A (hard) link in minix (and Unix) is a file (or directory) that has a different name but refers to the same inode. When a file (or directory) is created, `i_nlinks` is equal to 1. Each additional link increments `i_nlinks`. Removing links or removing the original file or directory decrements `i_nlinks`. Only when `i_nlinks` equals 0 is the inode removed.


	`i_uid` and `i_gid` specify the user and group id of the inode owner.


	`i_atime` is the time (in seconds since Jan. 1, 1970) of the last access of the file or directory. `i_mtime` is the time (in seconds since Jan. 1, 1970) of the last modification of the file or directory. `i_ctime` is the time (in seconds since Jan. 1, 1970) of the last change to the inode itself.


	`i_zone[]` contains the 7 direct zones, the single indirect zone, and the double indirect zone (read section 5.6.4 in Operating Systems for details).


	In memory, an inode from a V1 file system and an inode from a V2 file system are both stored in a `struct inode` (see line 20510 in the book). On disk, an inode from a V1 file system is stored in a `struct d1_inode` (see line 19600 in the book) and an inode from a V2 file system is stored in a `struct d2_inode` (see line 19611 in the book). Since the `i_atime` and `i_ctime` fields of `struct inode` don't have counterparts in `struct d2_inode`, the time of last modification (`d1_mtime`) is used for both. Obviously, this isn't ideal but it works well enough.


	I'm not sure why `curfil.i_dev` can't be set. If you understand, please send an e-mail to feedback@swartzbaugh.net.


	`i_zone[0]` typically holds the first zone that belongs to the inode. However, if the inode describes a special block or character file, `i_zone[0]` holds the (major, minor) numbers of the device. Read section 5.6.9 (beginning with the 4th paragraph) in Operating Systems.


	`a_indir` and `a_dindir` are initialized in anticipation of the next call to `vir2abs()` (line 8196). `dirpos` is initialized in anticipation of the next call to `r_readdir()` (line 8157).


	Before `r_readdir()` is called, `r_stat()` (line 8087) fills in `curfil` (line 8046) with information from a directory's inode and initializes `dirpos` to 0 (see line 8154). If `curfil` is not a directory, `r_readdir()` returns immediately (see line 8164). `r_readdir()` reads a directory entry and returns the entry's inode number and returns the name of the inode entry in `*name`. `r_readdir()` also updates `dirpos` (see line 8191) so that the next call to `r_readdir()` reads the next entry. `r_readdir()` returns 0 after it has read all the directory entries. Directories are explained in sections 5.3.2 ("Directories in UNIX") and 5.6.6 in Operating Systems.


	`struct direct` is declared in <sys/dir.h> (see line 02411 in the book). 2 bytes are reserved for the inode number and 14 bytes are reserved for the name (minix file and directory names can be 14 characters long).


	`S_ISDIR()` returns TRUE if `curfil` is a directory. `S_ISDIR()` is `#define`d in stat.h (see line 02355 in the book).


	This `while` loop reads in a new block (if necessary) of directory entries and extracts the name and inode number of the entry corresponding to `dirpos`. The name of the entry is copied to `name` (see lines 8188-8189) and `inum` is set to the inode number (see line 8186). If the directory entry corresponding to `dirpos` is empty, `r_readdir()` returns 0.


	`dirpos` is the offset from the beginning of the first directory block; `blkpos` is the offset from the beginning of the current directory block.