レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ 仮想ファイルシステムのデータ構造 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

今回はプロセスの仮想ファイルシステム(VFS)のデータ構造について見ていく。

VFSの役割

VFS(Virtual File System)はUNIXファイルシステムの全てのシステムコールを処理し、複数種類のファイルシステムへの共通インターフェースを提供する。

VFSが扱うファイルシステムは以下の3種類に大別される。

ディスクベースのファイルシステム

ローカルディスクやディスクをエミュレートするデバイスなど。

ネットワークファイルシステム

ネットワーク接続した他のホストの上に存在するファイルにアクセスするためのファイルシステム

特殊ファイルシステム

ローカルやネットワークどちらのディスク領域も管理しないファイルシステム(procfsなど)。

Unixディレクトリはルート(/)を起点とするツリー構造となっており、ルートディレクトリはルートファイルシステム(Ext2Ext3など)にマウントされ、他のファイルシステムはこのルートファイルシステムのサブディレクトリにマウントされる。

ディスクベースのファイルシステムは通常、ハードディスクやフロッピー、CD-ROMといった物理的なブロック型デバイスに保存されるが、LinuxではVFSの機能で仮想ブロック型デバイスとして扱うことも可能。

共通ファイルモデル

VFSを支える概念として共通ファイルモデルが存在する。この共通モデルではディレクトリはファイルや他のディレクトリの情報をもったファイルとして扱われる。

共通ファイルモデルは以下のようなオブジェクトから構成される。

スーパーブロック

マウントされたファイルシステムに関する情報を保存するオブジェクト。

iノードオブジェクト

個々のファイルの情報を持つオブジェクト。iノードにはiノード番号が振られファイルシステム内で一意にファイルを特定することができる。

ファイル

オープンされているファイルとプロセス間の処理に関する情報を保存するオブジェクト。プロセスがファルをオープンしている間のみカーネル内のメモリに存在する。

dエントリ

ディレクトリエントリ(ファイル名)と対応するファイルのリンク情報を保存するオブジェクト。ディスクベースのファイルシステムではファイルシステム独自の方法でディスクに保持される。

詳解Linuxカーネル

上記の図では3つのプロセスが同じファイルをオープンしており、そのうち2つが同じハードリンクを使用している。dエントリはハードリンクに対応しており、そのdエントリは同じiノードを参照している。

VFSは共通インターフェースを提供するだけでなく性能面にも貢献しており、dエントリオブジェクトをdエントリキャッシュと呼ばれるディスクキャッシュ内に配置し、ファイルパスを高速にiノードへ変換を高速化している。(ディスクキャッシュは一般的にディスクに保存されている情報をRAMに置くための仕組み)

VFSが扱うシステムコール

VFSが扱うシステムコールには主に以下のようなモノが存在する。

システムコール 説明
mount, umount, umount2 ファイルシステムのマウント・アンマウント
sysfs ファイルシステム情報の取得
stasfs, fstatfs, statfs64, fstatfs64, ustat ファイルシステムの統計情報の取得
chroot, pivot_root ルートディレクトリの変更
chdir, fchdir, getcwd カレントディレクトリの操作
mkdir, rmdir ディレクトリの作成・削除
getdents, getdents64, readdir, link, unlink, rename, lookup_dcookie ディレクトリエントリの操作
readlink, symlink シンボリックリンクの操作
chown, fchown, lchown, chown16, fchown16, lchown16 ファイル所有者の変更
chown, fchown, utime ファイル属性の変更
stat, fstat, lstat, access, oldstat, oldfstat, oldlstat, stat64, lstat64, fstat64 ファイル状態の読み取り
open, close, creat, umask ファイルのオープン・クローズ
dup, dup2, fcntl, fcnt64 ファイルディスクリプタの操作
select, poll ファイルディスクリプタの集合に対する事象
truncate, ftruncate, truncate64, ftruncate64 ファイル長の変更
lseek, llseek ファイルポインタの変更
read, write, readv, writev, sendfile, sendfile64, readahead ファイルのI/O操作
io_setup, io_submit, io_getevents, io_cancel, io_destroy 非同期I/O
pread64, pwrite64 ファイルポインタの変更とファイルアクセス
mmap, mmap2, munmap, madvise, mincore, remap_file_pages ファイルのメモリマッピング操作
fdatasync, fsync, sync, msync ファイルデータの同期
flock ファイルロックの操作
setxattr, lsetxattr, fsetattr, getxattr, lgetxattr, fgetattr, listxattr, listxattr, flistxattr, removexattr, lremovexattr, fremovexattr ファイルの拡張属性の操作

VFSデータ構造

スーパーブロックオブジェクト

スーパーブロックオブジェクトはsuper_block構造体から為る。

// include/linux/fs.h
struct super_block {
    struct list_head   s_list;     /* スーパーブロックリストのポインタ */
    dev_t           s_dev;      /* デバイス番号 */
    unsigned long     s_blocksize; /* ブロック長(バイト単位) */
    unsigned long     s_old_blocksize; /* ブロック型デバイスドライバが通知したブロック長(バイト単位) */
    unsigned char     s_blocksize_bits; /* ブロック長(ビットの桁数) */
    unsigned char     s_dirt; /* 変更されたかどうかを示すフラグ */
    unsigned long long   s_maxbytes; /* ファイル長の最大値 */
    struct file_system_type    *s_type; /* ファイルシステム種別へのポインタ */
    struct super_operations    *s_op; /* スーパーブロックのメソッド */
    struct dquot_operations    *dq_op; /* ディスククォータの操作メソッド */
    struct quotactl_ops    *s_qcop; /* ディスククォータの管理メソッド */
    struct export_operations *s_export_op; /* ネットワークファイルシステムで使用するファイルシステム公開(export)処理 */
    unsigned long     s_flags; /* マウントフラグ */
    unsigned long     s_magic; /* マジックナンバー */
    struct dentry      *s_root; /* ファイルシステムのルートディレクトリ用のdエントリオブジェクト */
    struct rw_semaphore    s_umount; /* アンマウント用のセマフォ */
    struct semaphore   s_lock; /* スーパーブロックのセマフォ */
    int            s_count; /* 参照カウンタ */
    int            s_syncing; /* スーパーブロックのinode群が同期処理中であることを示すフラグ */
    int            s_need_sync_fs; /* マウント済みファイルシステムのスーパーブロックの同期処理時に使用するフラグ */
    atomic_t        s_active; /* 補助参照カウンタ */
    void                    *s_security; /* スーパーブロックのセキュリティ構造体へのポインタ */
    struct xattr_handler   **s_xattr; /* スーパーブロックの閣僚属性構造体へのポインタ */

    struct list_head   s_inodes;   /* 全iノードのリスト */
    struct list_head   s_dirty;    /* 変更されたiノードのリスト */
    struct list_head   s_io;       /* ディスクへの書き込み待ちiノードのリスト */
    struct hlist_head  s_anon;     /* ネットワークファイルシステム処理用の無名ディレクトリのリスト */
    struct list_head   s_files; /* ファイルオブジェクトのリスト */

    struct block_device    *s_bdev; /* ブロック型デバイスディスクリプタへのポインタ */
    struct list_head   s_instances; /* 同じファイルシステム種別のスーパーブロックオブジェクトのリスト用のポインタ */
    struct quota_info  s_dquot;    /* ディスククォータ用のディスクリプタ */

    int            s_frozen; /* ファイルシステムが凍結中であることを示すフラグ(強制同期のため) */
    wait_queue_head_t   s_wait_unfrozen; /* ファイルシステムの凍結が解除されるまでプロセスを休止させるためのキュー */
    /* ここでいう”凍結”は書き込みのできない状態にするということ */

    char s_id[32];                /* スーパーブロックを格納しているブロック型デバイス名 */

    void           *s_fs_info; /* ファイルシステム固有のスーパーブロック情報へのポインタ */
    /* s_fs_infoがiノードやブロックのビットマップなどを保持する */struct semaphore s_vfs_rename_sem; /* ディレクトリをまたいだファイル名変更時に使用するセマフォ */

    u32        s_time_gran /* タイムスタンプの粒度(ナノ秒単位) */;
};


/* システム上の全てのスーパーブロックオブジェクトの双方向リストの先頭 */
extern struct list_head super_blocks;
extern spinlock_t sb_lock; // 上記のリストのためのロック変数

s_fs_infoの参照先にあるデータはファイルシステム固有の情報であり、iノードやディスクブロックの使用未使用を表すビットマップなどを保持し、ディスクにアクセスすることなくメモリ上の情報を更新する。

一方で上記の方法だとメモリとディスクの情報に差異が生じるため、同期が取れていない状態を示すフラグとしてs_dirtyメンバが存在する。Linuxでは当該フラグを見て定期的にデータを動悸している。

スーパーブロックの操作用メソッドはs_opメンバ変数が管理しており、super_operations構造体として定義されている。

// include/linux/fs.h
struct super_operations {
    /* iノードオブジェクト領域を割り当てる(iノードにはファイルシステム固有のデータも含まれる)*/
    struct inode *(*alloc_inode)(struct super_block *sb);

    /* iノードオブジェクト領域の破棄する */
    void (*destroy_inode)(struct inode *); 

    /* iノードオブジェクトのアドレスを受け取り、ディスク上のデータを基にそのiノードオブジェクトを初期化する */
    void (*read_inode) (struct inode *);

    /* iノードがdirtyである時に呼び出される。ジャーナル機能のあるファイルシステムで使用される */
    void (*dirty_inode) (struct inode *);

    /* ファイルシステム上のiノードを引数のiノードオブジェクトで更新する */
    int (*write_inode) (struct inode *, int);

    /* iノードを開放する時に呼び出され、参照カウンタをデクリメントしファイルシステム固有の処理を行う */
    void (*put_inode) (struct inode *);

    /* iノードが破棄される時、参照カウンタが0になる時に呼び出され、ファイルシステムからそのiノードを開放する */
    void (*drop_inode) (struct inode *);

    /* iノードを破棄する時に呼び出され、VFS及びディスク上両方のファイルデータ及びメタデータを削除する */
    void (*delete_inode) (struct inode *); 

    /* スーパーブロックオブジェクトのアドレスを受け取り、解放する(ファイルシステムがアンマウントされたため) */
    void (*put_super) (struct super_block *);

    /* 指定したスーパーブロックオブジェクトの内容でファイルシステムのスーパーブロックを更新する */
    void (*write_super) (struct super_block *);

    /* ファイルシステムのデータ構造をディスクに書き戻し更新する */
    int (*sync_fs)(struct super_block *sb, int wait);

    /* ファイルシステムの変更を禁止し、指定したスーパーブロックオブジェクトの内容でスーパーブロックを更新する(LVMが使用する) */
    void (*write_super_lockfs) (struct super_block *);

    /* ファイルシステムの変更禁止を解除する */
    void (*unlockfs) (struct super_block *);

    /* ファイルシステムの統計情報をバッファに入れて返す */
    int (*statfs) (struct super_block *, struct kstatfs *);

    /* 新しいオプションでファイルシステムを再マウントする(マウントオブション変更時など) */
    int (*remount_fs) (struct super_block *, int *, char *); 

    /* ディスクのiノードを破棄する場合に呼び出す */
    void (*clear_inode) (struct inode *);

    /* アンマウント操作が開始された(マウント操作の中断) */
    void (*umount_begin) (struct super_block *);

    /* ファイルシステム固有のオブションを表示する */
    int (*show_options)(struct seq_file *, struct vfsmount *);

    /* クォータシステムで使用されファイルシステムの制限値を管理するファイルからデータを読み出す */
    ssize_t (*quota_read)(struct super_block *, int, char *, size_t, loff_t);

    /* クォータシステムで使用されファイルシステムの制限値を管理するファイルにデータを書き込む */
    ssize_t (*quota_write)(struct super_block *, int, const char *, size_t, loff_t);
};

iノードオブジェクト

ファイルシステムが扱う各ファイルは全てiノードと呼ばれるデータ構造で管理される。ファイル名は変更可能だがiノードはファイルに対して一意に存在している。メモリ内のiノードオブジェクトはinode構造体から為る。

// include/linux/fs.h
struct inode {
    struct hlist_node  i_hash; /* ハッシュリスト用のポインタ */
    struct list_head   i_list; /* iノードの現在の状態を表すリスト用のポインタ */
    struct list_head   i_sb_list; /* スーパーブロックのiノードリスト用のポインタ */
    struct list_head   i_dentry; /* iノードの参照するdエントリオブジェクトリストの先頭 */
    unsigned long     i_ino; /* iノード番号 */
    atomic_t        i_count; /* 利用カウンタ */
    umode_t         i_mode; /* ファイル種別とアクセス権 */
    unsigned int      i_nlink; /* ハードリンク数 */
    uid_t           i_uid; /* ユーザID */
    gid_t           i_gid; /* グループID */
    dev_t           i_rdev; /* 実デバイス番号 */
    loff_t          i_size; /* ファイル長(単位: バイト) */
    struct timespec        i_atime; /* 最終アクセス時刻 */
    struct timespec        i_mtime; /* 最終書き込み時刻 */
    struct timespec        i_ctime; /* 最終更新時刻 */
    unsigned int      i_blkbits; /* ブロックサイズ(単位: ビット数) */
    unsigned long     i_blksize; /* ブロックサイズ(単位: バイト) */
    unsigned long     i_version; /* バージョン番号、inode使用時に自動的にインクリメントされる */
    unsigned long     i_blocks; /* ファイルのブロック数 */
    unsigned short          i_bytes; /* ファイルの最終ブロックのバイト数 */
    unsigned char     i_sock; /* このファイルがソケットであれば0以外の値を持つ */
    spinlock_t      i_lock; /* iノードのスピンロック */
    struct semaphore   i_sem; /* iノードアクセス用のセマフォ */
    struct rw_semaphore    i_alloc_sem; /* direct I/O用のセマフォ */
    struct inode_operations    *i_op; /* iノードの操作用のメソッド群 */
    struct file_operations *i_fop; /* 初期のファイル操作用のメソッド群 */
    struct super_block *i_sb; /* スーパーブロックオブジェクトへのポインタ */
    struct file_lock   *i_flock; /* ファイルロックリストへのポインタ */
    struct address_space   *i_mapping; /* アドレス空間オブジェクトへのポインタ */
    struct address_space   i_data; /* このファイルのアドレス空間オブジェクト */
#ifdef CONFIG_QUOTA
    struct dquot       *i_dquot[MAXQUOTAS]; /* ノードディスククォータ */
#endif
    /* These three should probably be a union */
    struct list_head   i_devices; /* キャラクタ型又はブロック型デバイスファイルに関連するiノードリストへのポインタ */
    struct pipe_inode_info *i_pipe; /* ファイルがパイプである場合に使用 */
    struct block_device    *i_bdev; /* ブロック型デバイスドライバへのポインタ */
    struct cdev        *i_cdev; /* キャラクタ型デバイスドライバへのポインタ */
    int            i_cindex; /* マイナー番号グループ内のデバイスファイルのインデックス */

    __u32           i_generation; /* iノードのバージョン番号 */

#ifdef CONFIG_DNOTIFY
    unsigned long     i_dnotify_mask; /* ディレクトリ通知イベント用のマスク */
    struct dnotify_struct  *i_dnotify; /* ディレクトリ通知に使用 */
#endif

    unsigned long     i_state; /* iノード状態のフラグ */
    unsigned long     dirtied_when;   /* ノードがdirtyになった時刻(単位: tick) */

    unsigned int      i_flags; /* ファイルシステムのマウントフラグ */

    atomic_t        i_writecount; /* 書き込みプロセス用の利用カウンタ */
    void           *i_security; /* iノードのセキュリティ構造体へのポインタ */
    union {
        void       *generic_ip; /* 固有データへのポインタ */
    } u;
#ifdef __NEED_I_SIZE_ORDERED
    seqcount_t      i_size_seqcount; /* SMPシステムでi_sizeの整合性を取るための順次カウンタ */
#endif
};

iノードオブジェクトのi_stateメンバはそのiノードの状態を表しており以下のような値がビットフラグとして設定される。

// include/linux/fs.h
/* iノードがdirtyな状態(ディスク上のデータと異なる状態) */
#define I_DIRTY_SYNC       1 /* Not dirty enough for O_DATASYNC */
#define I_DIRTY_DATASYNC   2 /* Data-related inode changes pending */
#define I_DIRTY_PAGES      4 /* Data-related inode changes pending */

#define __I_LOCK       3
#define I_LOCK         (1 << __I_LOCK) // I/O転送処理中
#define I_FREEING      16 // 解放処理中
#define I_CLEAR        32 // 無効
#define I_NEW          64 // 初期化前

各iノードは以下のいずれかの双方向リストに所属している。隣り合う要素同士は上記のi_listメンバで参照し合う。

  • 未使用のiノードオブジェクトのリスト。リスト上の要素はディスク上のiノードを正確に反映しておりプロセスからは利用されておらず、i_countメンバは0となっている。
extern struct list_head inode_unused;
  • 使用中のiノードオブジェクトのリスト。リスト上の要素はディスク上のiノードを正確に反映しており、プロセスが利用中のiノードオブジェクトが所属し、i_countメンバは0より大きい値が設定される。
extern struct list_head inode_in_use;
  • dirtyな状態のiノードオブジェクトのリスト。対応するスーパーブロックオブジェクトのs_dirtyメンバによあって参照できる。

上記のリストの他にもスーパーブロックオブジェクトのs_inodeメンバのリスト変数でも管理され、加えてinode_hashtableというハッシュテーブルでも管理されている。ハッシュテーブルの参照先は衝突を回避するためにinode構造体のi_hashメンバで双方向リストを為している。

iノードの操作にはinode構造体のi_opメンバが保持しているメソッドを使用する。i_opinode_operations構造体変数で以下のように定義されている。

struct inode_operations {
    /* ディレクトリ(dir)内のdエントリオブジェクト(dentry)に対応する通常ファイル用に新たなiノードを作成する */
    int (*create) (struct inode *,struct dentry *,int, struct nameidata *);

    /* ディレクトリ(dir)を検索し、dエントリオブジェクト(dentry)に含まれるファイル名に対応するiノードを見つける */
    struct dentry * (*lookup) (struct inode *,struct dentry *, struct nameidata *);

    /* ファイルを参照する新しいハードリンクをディレクトリ内に作成する。 */
    int (*link) (struct dentry *,struct inode *,struct dentry *);

    /* ディレクトリ内からハードリンクを削除する */
    int (*unlink) (struct inode *,struct dentry *);

    /* ディレクトリ内にハードリンクに対応するシンボリックリンクを作成する */
    int (*symlink) (struct inode *,struct dentry *,const char *);

    /* ディレクトリ内に指定されたディレクトリを作成する */
    int (*mkdir) (struct inode *,struct dentry *,int);

    /* サブディレクトリをディレクトリ内から削除する */
    int (*rmdir) (struct inode *,struct dentry *);

    /* ディレクトリ内に特殊ファイル用のiノードをディスク上に作成する */
    int (*mknod) (struct inode *,struct dentry *,int,dev_t);

    /* 指定のファイル情報を指定のdエントリに移す */
    int (*rename) (struct inode *, struct dentry *,
            struct inode *, struct dentry *);

    /* バッファに指定のシンボリックリンクのパスを書き込む */
    int (*readlink) (struct dentry *, char __user *,int);

    /* iノードオブジェクトで指定するシンボリックリンクを解釈する */
    int (*follow_link) (struct dentry *, struct nameidata *);

    /*  follow_linkによって確保されたデータ構造を開放する */
    void (*put_link) (struct dentry *, struct nameidata *);

    /* inodeに対応するファイルサイズを変更する */
    void (*truncate) (struct inode *);

    /* 指定の権限がinodeで許可されているかを調べる */
    int (*permission) (struct inode *, int, struct nameidata *);

    /* iノード促成の変更があったことを通知 */
    int (*setattr) (struct dentry *, struct iattr *);

    /* iノード属性を読み込む */
    int (*getattr) (struct vfsmount *mnt, struct dentry *, struct kstat *);

    /* iノードの拡張属性を設定する */
    int (*setxattr) (struct dentry *, const char *,const void *,size_t,int);

    /* iノードの拡張属性を取得する */
    ssize_t (*getxattr) (struct dentry *, const char *, void *, size_t);

    /* 拡張属性を表す名前リストを取得 */
    ssize_t (*listxattr) (struct dentry *, char *, size_t);

    /* iノードの拡張属性を削除する */
    int (*removexattr) (struct dentry *, const char *);
};

上記のうちiノードとファイルシステムに利用して意味があるのは一部のみで、ファイルシステムで実装されていないメソッドにはNULLが設定される。

ファイルオブジェクト

プロセスとそのプロセスによってオープンされたファイルの情報を保持するもので、ディスク上には存在しない。当該オブジェクトはfile構造体として定義されている。

// include/linux/fs.h
struct file {
    struct list_head   f_list; // ファイルオブジェクトの汎用的なリスト用のポインタ
    struct dentry      *f_dentry; // オープン時に利用したファイル名を保持するdエントリ
    struct vfsmount         *f_vfsmnt; // そのファイルを扱うファイルシステムへのポインタ
    struct file_operations *f_op; // ファイル操作用のメソッドを保持する構造体へのポインタ
    atomic_t        f_count; // ファイルオブジェクトへの参照ポインタ
    unsigned int      f_flags; // ファイルのオープン時に指定されたフラグ
    mode_t          f_mode; // プロセスのアクセスモード
    int            f_error; // ネットワーク経由の書き込み時に発生したエラー番号
    loff_t          f_pos; // 現在のファイルオフセット
    struct fown_struct f_owner; // シグナル経由のI/Oイベント通知用データ
    unsigned int      f_uid, f_gid; // ユーザID、グループID
    struct file_ra_state   f_ra; // ファイルの先読み状態

    size_t         f_maxcount; // 一度の処理で書き込み可能な最大バイト数
    unsigned long     f_version; // バージョン番号(アクセス時に自動インクリメント)
    void           *f_security; // ファイルオブジェクトのセキュリティ構造体へのポインタ

    /* needed for tty driver, and maybe others */
    void           *private_data; // ファイルシステムやデバイスドライバの固有データへのポインタ

#ifdef CONFIG_EPOLL
    /* Used by fs/eventpoll.c to link all the hooks to this file */
    struct list_head   f_ep_links; // このファイル用のイベントポール待ちリストの先頭
    spinlock_t      f_ep_lock; // f_ep_linksのためのスピンロック
#endif /* #ifdef CONFIG_EPOLL */
    struct address_space   *f_mapping; // ファイルのアドレス空間オブジェクトへのポインタ
};

ファイルオブジェクトの中で重要なのはファイルポインタ(オフセット)で、現在利用中のファイルのどの位置を読んでいるのかを表すデータである。これはプロレス毎に独立した値として管理する必要があるため、iノードではなくファイルオブジェクトとして管理する。

ファイルオブジェクトはファイルキャッシュから割り当てられる。

// fs/dcache.c
kmem_cache_t *filp_cachep;

システム上で作成できるファイルオブジェクト数はfile_statで管理される。

// fs/file_table.c
/* sysctl tunables... */
struct files_stat_struct files_stat = {
    .max_files = NR_FILE
};

使用中のファイルオブジェクトはそのファイルを管理するファイルシステムのiノードを基点としたリストに繋がれ、前後の要素はファイルオブジェクトのf_listメンバで接続される。

ファイルオブジェクトのf_countメンバはファイルオブジェクトの参照カウンタで、そのファイルオブジェクトを参照しているプロセスを表す(cloneシステムコールCLONE_FILESフラグを指定されたプロセスは親とファイルオブジェクトを共有する)。この参照数はカーネルがオブジェクトを参照する際にも同様にインクリメントされる。

ファイル操作用の関数はファイルオブジェクトのf_opメンバが保持しており、プロセスがファイルをオープンする際にiノードオフジェクトが保持している操作メソッドのアドレス群で初期化する。

// include/linux/fs.h
struct file_operations {
    struct module *owner;

    /* ファイルポインタ(オフセット)の更新 */
    loff_t (*llseek) (struct file *, loff_t, int);

    /* ファイルポインタを基点に指定オフセットから指定サイズ分のデータを読み込み、ユーザ空間のバッファに格納し、読み込んだサイズ分オフセットを更新する */
    ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);

    /* 非同期に読み込みを行う */
    ssize_t (*aio_read) (struct kiocb *, char __user *, size_t, loff_t);

    /* ファイルポインタを基点に指定オフセットから指定サイズ分のデータを書き込み、ユーザ空間のバッファに格納し、書き込んだサイズ分オフセットを更新する */
    ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);

    /* 非同期に書き込みを行う */
    ssize_t (*aio_write) (struct kiocb *, const char __user *, size_t, loff_t);

    /* ディレクトリの次のエントリを返す */
    int (*readdir) (struct file *, void *, filldir_t);

    /* ファイルの変更が行われるまで待機する */
    unsigned int (*poll) (struct file *, struct poll_table_struct *);

    /*  特殊な処理を行うための関数(主にデバイス周りで使用される) */
    int (*ioctl) (struct inode *, struct file *, unsigned int, unsigned long);

    /* グローバルカーネルロックを使用しない"ioctl" */
    long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);

    /* 64bitの環境で32bitのioctlを使用するためのもの */
    long (*compat_ioctl) (struct file *, unsigned int, unsigned long);

    /* プロセスのアドレス空間にメモリマッピングを行う */
    int (*mmap) (struct file *, struct vm_area_struct *);

    /* ファイルオブジェクトを生成し対応するiノードオブジェクトとリンクする */
    int (*open) (struct inode *, struct file *);

    /* オープン中のファイルがクローズされた時に呼び出される(処理の詳細はファイルシステムに依存する) */
    int (*flush) (struct file *);

    /* ファイルオブジェクトを開放する(f_countメンバが0になった時) */
    int (*release) (struct inode *, struct file *);

    /* メモリにキャッシュされているデータをディスクに書き戻す */
    int (*fsync) (struct file *, struct dentry *, int datasync);

    /* 非同期でキャッシュされているメモリのデータをディスクに書き戻す */
    int (*aio_fsync) (struct kiocb *, int datasync);

    /* シグナルで受け取るI/Oイベントの通知を許可または禁止する */
    int (*fasync) (int, struct file *, int);

    /* ファイルをロックする */
    int (*lock) (struct file *, int, struct file_lock *);

    /*  ファイルからデータを読み込みバッファに格納する */
    ssize_t (*readv) (struct file *, const struct iovec *, unsigned long, loff_t *);

    /* バッファからデータをファイルに書き込む */
    ssize_t (*writev) (struct file *, const struct iovec *, unsigned long, loff_t *);

    /* データを転送する */
    ssize_t (*sendfile) (struct file *, loff_t *, size_t, read_actor_t, void *);
    
    /* ページキャッシュにあるファイルデータを転送する(ネットワークで使用される) */
    ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);

    /* ファイルにマッピングするための未使用アドレス範囲を取得する */
    unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
    
    /* fcntlシステムコールが呼び出す、NFSが使用 */
    int (*check_flags)(int);
    
    /* fcntlシステムコールが呼び出す(ディレクトリの変更通知を設定する)、CIFSが使用 */
    int (*dir_notify)(struct file *filp, unsigned long arg);

    /* flockシステムコールの振る舞いを変更する */
    int (*flock) (struct file *, int, struct file_lock *);
};

実装されていないメソッドにはNULLが設定される。

dエントリオブジェクト

ディスク上でディレクトリはファイルとサブディレクトリの一覧が入った通常のファイルとみなされており、そのディレクトリ内のエントリがメモリに読み込まれる際にdエントリとして扱われる。

dエントリはプロセスが参照するパス名の要素1つ1つに対となるよう作成され/tmp/testであれば、/tmptestの3つに対して作成される。

dエントリオブジェクトはディスク上に対応するデータは無く、スラブアロケータキャッシュに保存される。

// fs/dcache.c
static kmem_cache_t *dentry_cache;

dエントリの構造体であるdentryは以下のように定義されている。

// include/linux/dcache.h
struct dentry {
    atomic_t d_count; /* dエントリの参照カウンタ */
    unsigned int d_flags;     /* フラグ */
    spinlock_t d_lock;      /* エントリ用のスピンロック */
    struct inode *d_inode;     /* dエントリに対応するiノード */
    /*
    * The next three fields are touched by __d_lookup.  Place them here
    * so they all fit in a 16-byte range, with 16-byte alignment.
    */
    struct dentry *d_parent;   /* 親ディレクトリのdエントリ */
    struct qstr d_name; /* ファイル名 */

    struct list_head d_lru;        /* 未使用ディレクトリリスト(LRU) */
    struct list_head d_child;  /* 同一のdエントリを親として持つ子のリスト */
    struct list_head d_subdirs;    /* このdエントリに対応するディレクトリ内にあるdエントリ */
    struct list_head d_alias;  /* 同じiノードを共有するeエントリのリスト */
    unsigned long d_time;     /* d_revalidate関数によって使用される */
    struct dentry_operations *d_op; /* dエントリのメソッド群 */
    struct super_block *d_sb;  /* ファイルのスーパーオブジェクト */
    void *d_fsdata;            /* ファイルシステム固有のデータ */
    struct rcu_head d_rcu; /* rエントリオブジェクトの回収時に使用するRCUディスクリプタ */
    struct dcookie_struct *d_cookie; /* プロファイラが使用するデータ構造へのポインタ */
    struct hlist_node d_hash;  /* ハッシュテーブルエントリ中のリストへのポインタ */ 
    int d_mounted; /* dエントリにマウントしたファイルシステム数のカウンタ */
    unsigned char d_iname[DNAME_INLINE_LEN_MIN];  /* 短いファイル名を格納する領域 */
};

dエントリオブジェクトは以下のいずれかの状態になる。

  • 空き

dエントリは有効な情報を保持しておらず、VFSによって使用されていない状態。メモリ領域はスラブアロケータによって管理される。

  • 未使用

dエントリはカーネルよって使用されておらずd_countメンバは0だが、d_inodeメンバは対応するiノードを指している状態。dエントリは有効な情報を保持しているが再利用の対象と為る。

  • 使用中

dエントリがカーネルによって使用されている。d_countは1以上の値が入っており、d_inodeは対応するiノードオブジェクトを指す。オブジェクトには有効な情報が格納されており破棄されない。

dエントリに対応するiノードが存在せず、ディスク上のiノードも削除された状態。d_inodeにはNULLが設定されている。

dエントリオブジェクトの操作メソッドはd_opメンバが保持しており、当該メンバはdentry_operations構造体として定義されている。

// include/linux/dcache.h
struct dentry_operations {
    /* ファイルのパス名変換時にdエントリが有効化どうかを確認する(デフォルトはNULLでネットワークファイルシステムでは特定の処理が設定されていることがある) */
    int (*d_revalidate)(struct dentry *, struct nameidata *);

    /* dエントリハッシュテーブルで使用されるファイルシステム独自のハッシュ関数。 */
    int (*d_hash) (struct dentry *, struct qstr *);

    /* 2つのファイル名を比較する(デフォルトでは文字列比較) */
    int (*d_compare) (struct dentry *, struct qstr *, struct qstr *);

    /* dエントリオブジェクトの参照数が0になった際に呼び出される(デフォルトでは何もしない) */
    int (*d_delete)(struct dentry *);

    /* dエントリオブジェクトが開放される時に呼び出される(デフォルトでは何もしない) */
    void (*d_release)(struct dentry *);

    /* dエントリオブジェクトが”負”の状態になった時に呼び出される(デフォルトではiノードオブジェクトを開放する"iput()"が呼び出される) */
    void (*d_iput)(struct dentry *, struct inode *);
};

dエントリキャッシュ

ディレクトリエントリをディスクから読み込みdエントリオブジェクトを構築するのはコストがかかるため、dエントリキャッシュを使用する。

当該キャッシュは2つのデータ構造から為る。

  • 「使用中」「未使用」「負」の状態のいずれかにあるdエントリキャッシュの集合
  • ファイル名とディレクトリが与えられた際に対応するdエントリオブジェクトを高速に取得するためハッシュテーブル。

未使用のdエントリに対応するiノードオブジェクトは、dエントリキャッシュに参照されているため破棄されない、よってそのiノードオブジェクトはRAMに置かれたままとなり、対応するdエントリによって高速に参照が可能となる。

未使用のdエントリはLRU(Least Recently Used)リストで管理されている。

// fs/dcache.c
static LIST_HEAD(dentry_unused);

dentry_unused変数のnextprevメンバがリストの先頭と末尾を、dエントリオブジェクトのd_lruメンバがその前後の要素を参照している。

使用中のdエントリオブジェクトは対応するiノードオブジェクトのi_dentryメンバが参照している双方向リストで管理される(iノードは複数のハードリンクから参照される可能性があるため)。dエントリオブジェクトのd_aliasメンバにはリストの隣接する要素のアドレスが保存される。

ハッシュテーブルはdentry_hashtable配列によって実装されている。各要素は同じハッシュを持つdエントリリストへのポインタで配列のサイズはシステムが搭載しているRAMサイズに比例する。dエントリオブジェクトのd_hashメンバは同一ハッシュ値を持つリストの隣接する要素を参照する。

プロセスとファイル

プロセスにはワーキングディレクトリとルートディレクトリが存在し、その情報はプロセスディスクリプタ(tasK_struct)のfsメンバ(fs_struct)が保持している。

// include/linux/fs_struct.h
struct fs_struct {
    atomic_t count; // 共有するプロセス数
    rwlock_t lock; // 読み書きスピンロック
    int umask; // ファイル権限のためのビットマスク

    // ルートディレクトリ、ワーキングディレクトリのdエントリ
    struct dentry * root, * pwd, * altroot;
    // ルートディレクトリ、ワーキングディレクトリのファイルシステムオブジェクト
    struct vfsmount * rootmnt, * pwdmnt, * altrootmnt;
};

プロセスには上記の他に現在オープンしているファイル情報も保持する必要があり、その情報はプロセスディスクリプタfilesメンバであるfiles_struct構造体で管理されている。

// include/linux/file.h
struct files_struct {
        atomic_t count; /* この構造体を共有するプロセス数*/
        spinlock_t file_lock; /* この構造体用のスピンロック */
        int max_fds; /* ファイルオブジェクトの最大数 */
        int max_fdset; /* ファイルディスクリプタの現在の最大数 */
        int next_fd; /* 次に割り当てるのディスクリプタ番号 */
        struct file ** fd; /* ファイルオブジェクトポインタ配列へのポインタ */
        fd_set *close_on_exec; /* exec()時にクローズする必要のあるファイルディスクリプタ */
        fd_set *open_fds; /* オープン中のファイルディスクリプタへのポインタ */
        fd_set close_on_exec_init; /* exec()の際にクローズすべきファイルディスクリプタ集合の初期値 */
        fd_set open_fds_init; /* ファイルディスクリプタ集合の初期値 */
        struct file * fd_array[NR_OPEN_DEFAULT]; /* ファイルオブジェクトへのポインタを格納する初期配列 */
};

fdはファイルオブジェクト配列へのポインタで、通常はfd_array配列を参照する。1番目の要素は標準入力、2番目は標準出力、3番目は標準エラー出力となる。dupfcntlシステムコールで複数のファイルディスクリプタが同じオープン状態のファイルを参照可能なのは、複数の配列要素が同じファイルオブジェクトを参照することができるからである。

プロセスはNR_OPENの値よりも多くファイルディスクリプタを使用することができない。上限の初期値は1024に設定されておりルート権限を保持している場合のみ上限を変更することが可能。

// include/linux/fs.h
#define NR_OPEN (1024*1024)  /* Absolute upper limit on fd num */
#define INR_OPEN 1024     /* Initial setting for nfile rlimits */

ファイルディスクリプタ番号をfdが保持している場合、カレントプロセスからファイルオブジェクトを取得する際には以下のようなコードになる。

current->files->fd[fd];

ファイルシステムの種別

特殊ファイルシステム

ネットワークやディスクベースのファイルシステム以外に特殊な用途で用いられるファイルシステムがいくつか存在する。代表的なものに以下のようなものが挙げられる。

名前 マウントポイント 説明
bdev ブロック型デバイス
devpts /dev/pts 疑似端末の提供
eventpollfs 効率の良いイベントポーリング機構が利用
futexfs futex(ユーザ空間のロック機構)が使用
pipefs パイプをFIFOとして扱う
proc カーネルデータ構造へのアクセスポイント
rootfs ブートストラップフェーズ用の空ルートディレクトリを提供
shm IPC共有メモリリージョン
mqueue POSIXメッセージキューの実装で使用
sockfs ソケット
sysfs システムデータへのアクセスポイント
tmpfs 一時ファイル
usbfs USBデバイス

特殊ファイルシステムには対応するブロックデバイスが存在せず、マウント時に擬似デバイスを割り当てる。疑似デバイスのメジャー番号は0でマイナー番号は任意の値となる。

ファイルシステム種別の登録

ファイルシステムの登録にはカーネルコンパイル時に静的に組み込む方法とモジュールとして動的に組み込む方法がある。登録したファイルシステムfile_system_type構造体のオブジェクトとして管理される。

// include/linux/fs.h
struct file_system_type {
    const char *name; /* ファイルシステム名 */
    int fs_flags; /* ファイルシステム種別のフラグ */
    struct super_block *(*get_sb) (struct file_system_type *, int,
                       const char *, void *); /* スーパーブロック読み取り用メソッド */
    void (*kill_sb) (struct super_block *); /* スーパーブロック削除メソッド */
    struct module *owner; /* ファイルシステムを実装するモジュールへのポインタ */
    struct file_system_type * next; /* ファイルシステム種別リストの次要素へのポインタ */
    struct list_head fs_supers; /* 同じファイルシステム種別のスーパーブロックオブジェクトリストの先頭 */
};

全てのファイルシステム種別オブジェクトは単方向リストのfile_systems変数で管理され、file_system_lock変数がスピンロック用の変数、これら2つの変数は以下のように定義されている。

// include/linux/fs.h
static struct file_system_type *file_systems;
static DEFINE_RWLOCK(file_systems_lock);

get_sbは新しいスーパーブロックの割り当てと初期化、kill_sbはスーパーブロックを破棄するために使用される。

fs_flagsメンバには以下のような値が設定される。

// include/linux/fs.h
#define FS_REQUIRES_DEV 1 /* 物理ディスクデバイス上に存在する */
#define FS_BINARY_MOUNTDATA 2 /* ファイルシステムがバイナリのマウントデータを使用する */
#define FS_REVAL_DOT   16384  /* dエントリキャッシュの"."、".."について有効性の確認を行う(ネットワークファイルシステム用) */ /* Check the paths ".", ".." for staleness */
#define FS_ODD_RENAME  32768  /* renameをmove操作に変更する */

実際のファイルシステムの登録処理はカーネルコンパイル時に指定されたファイルシステムを、システムの初期化時にregister_filesystem関数を呼び出し適切なfile_system_typeオブジェクトをファイルシステム種別リストに挿入することで行われる。register_filesystem関数はモジュールを組み込む際にも呼び出される。

参考