2016年02月05日
情報科学類 オペレーティングシステム II
筑波大学 システム情報系
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2015/2016-02-05
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/
試験について
図? 割り込み処理の前半部分と後半部分
割り込みハンドラ(前半部)と後半部の役割分担の目安。
注意1: Tasklet は、task 構造体とはまったく関係ない。名前がよくない。
注意2: Softirq という用語を、割り込み処理の後半部という意味で使う人もい る。
注意3: 伝統的なUnixでは、top half は、システム・コールから派生する上位 層の処理、bottom half は、割り込みから派生する下位層の処理の意味で使わ れることがある。Linux では、top half, bottom half は、割り込み処理の前 半部分と後半部分の意味に使う。
Tasklet で1つの仕事は次のような、struct tasklet_struct で表現される。
linux-3.18.1/include/linux/interrupt.h
465: struct tasklet_struct
466: {
467: struct tasklet_struct *next;
468: unsigned long state;
469: atomic_t count;
470: void (*func)(unsigned long);
471: unsigned long data;
472: };
図? Taskletにおける仕事のキュー
DECLARE_TASKLET(name, func, data)
有効な(count==0) の struct tasklet_struct を宣言する
DECLARE_TASKLET_DISABLED(name, func, data)
無効な(count==1) の struct tasklet_struct を宣言する
void tasklet_init(struct tasklet_struct *t,
void (*func)(unsigned long), unsigned long data);
その他に、生成消滅有効無効に関して次のような操作がある。
void tasklet_handler(unsigned long data) {
...
}
void tasklet_schedule(struct tasklet_struct *t)
Tasklet t を通常の優先度でスケジュールする
void tasklet_hi_schedule(struct tasklet_struct *t)
Tasklet t を高優先度でスケジュールする
すると、それは「そのうちに」1度だけ実行される。
linux-4.3.3/drivers/net/wireless/ath/ath9k/ath9k.h
954: struct ath_softc {
...
961: struct tasklet_struct intr_tq;
962: struct tasklet_struct bcon_tasklet;
...
1042: };
linux-4.3.3/drivers/net/wireless/ath/ath9k/init.c
532: static int ath9k_init_softc(u16 devid, struct ath_softc *sc,
533: const struct ath_bus_ops *bus_ops)
534: {
...
619: tasklet_init(&sc->intr_tq, ath9k_tasklet, (unsigned long)sc);
620: tasklet_init(&sc->bcon_tasklet, ath9k_beacon_tasklet,
621: (unsigned long)sc);
...
682: }
linux-4.3.3/drivers/net/wireless/ath/ath9k/main.c
486: irqreturn_t ath_isr(int irq, void *dev)
487: {
...
504: struct ath_softc *sc = dev;
...
507: enum ath9k_int status;
...
509: bool sched = false;
...
529: ath9k_hw_getisr(ah, &status, &sync_cause); /* NB: clears ISR too */
...
546: if (status & SCHED_INTR)
547: sched = true;
...
560: if (status & ATH9K_INT_SWBA)
561: tasklet_schedule(&sc->bcon_tasklet);
...
588: if (sched) {
589: /* turn off every interrupt */
590: ath9k_hw_disable_interrupts(ah);
591: tasklet_schedule(&sc->intr_tq);
592: }
593:
594: return IRQ_HANDLED;
...
597: }
369: void ath9k_tasklet(unsigned long data)
370: {
...
484: }
linux-4.3.3/drivers/net/wireless/ath/ath9k/beacon.c
319: void ath9k_beacon_tasklet(unsigned long data)
320: {
...
439: }
図? Work Queueにおける仕事のキュー
キューにつながれる仕事は、Tasklet の仕事とほとんど同じで、関数へのポイ ンタ func と data からなる。処理の主体が、ワーカ・スレッドと呼ばれるカー ネル・レベルのスレッドである所が違う。
$ ps alx|egrep events
1 0 19 2 20 0 0 0 worker S ? 0:12 [events/0]
1 0 20 2 20 0 0 0 worker S ? 0:08 [events/1]
1 0 21 2 20 0 0 0 worker S ? 0:08 [events/2]
1 0 22 2 20 0 0 0 worker S ? 0:10 [events/3]
0 1013 3242 2450 20 0 105236 900 pipe_w S+ pts/3 0:00 egrep events
$
汎用の Work Queue のワーカ・スレッドの他に、専用のワーカ・スレッドを作
ることもできる。
linux-4.3.3/include/linux/workqueue.h
19: typedef void (*work_func_t)(struct work_struct *work);
100: struct work_struct {
101: atomic_long_t data;
102: struct list_head entry;
103: work_func_t func;
...
107: };
struct work_struct my_work; ... INIT_WORK(&my_work,my_work_handler);
void my_work_handler(struct work_struct *work)
{
...
}
schedule_work(&work);
この結果、INIT_WORK() で設定したハンドラがワーカ・スレッドにより「その
うち」に呼び出される。
schedule_work() では、即座に実行される可能性もある。少し後に実行したい (間を取りたい)時には、次の関数を呼ぶ。
schedule_delayed_work(&work,ticks);
ticks は、どのくらい間をとるか。単位は、
ticks (jiffiesの単位)。
多くのシステムで10ミリ秒-1ミリ秒で、設定によって異なる。
解決策:
図? 層構造を用いたファイル・システムの実装
解決策
$ ls -l /usr/bin/{perl,perl5.10.1}
-rwxr-xr-x. 2 root root 13304 Nov 12 18:11 /usr/bin/perl
-rwxr-xr-x. 2 root root 13304 Nov 12 18:11 /usr/bin/perl5.10.1
$ ls -li /usr/bin/{perl,perl5.10.1}
1837781 -rwxr-xr-x. 2 root root 13304 Nov 12 18:11 /usr/bin/perl
1837781 -rwxr-xr-x. 2 root root 13304 Nov 12 18:11 /usr/bin/perl5.10.1
$
$ grep -v '#' /etc/fstab
UUID=9cfbc67e-781c-48d1-8303-1dde8ce87ee9 / ext4 defaults 1 1
UUID=bab1faf1-5f5b-4a2a-b24f-e850a2b0b82d /boot ext4 defaults 1 2
UUID=a1f61ff2-2c99-4c54-8c3e-2178eed3ec10 swap swap defaults 0 0
tmpfs /dev/shm tmpfs defaults 0 0
devpts /dev/pts devpts gid=5,mode=620 0 0
sysfs /sys sysfs defaults 0 0
proc /proc proc defaults 0 0
pentas-fs:/vol0/home /home nfs rw,hard,bg,nfsvers=3,intr 0 0
pentas-fs:/vol0/web /var/www nfs rw,hard,bg,nfsvers=3,intr 0 0
pentas-fs:/vol0/local3 /
$ df /
Filesystem 1K-blocks Used Available Use% Mounted on
/dev/sda3 49071944 6721604 39857568 15% /
$ blkid /dev/sda3
/dev/sda3: UUID="9cfbc67e-781c-48d1-8303-1dde8ce87ee9" TYPE="ext4"
$ ls -l /dev/sda3
brw-rw----. 1 root disk 8, 3 Feb 2 10:50 /dev/sda3
$ lsblk
NAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINT
sda 8:0 0 50G 0 disk
|-sda1 8:1 0 512M 0 part /boot
|-sda2 8:2 0 2G 0 part [SWAP]
`-sda3 8:3 0 47.6G 0 part /
sr0 11:0 1 1024M 0 rom
$ ls -l /dev/sda
brw-rw----. 1 root disk 8, 0 Feb 2 10:50 /dev/sda
$
$ grep cd /etc/auto.misc
cd -fstype=iso9660,ro,nosuid,nodev :/dev/cdrom
$
STAT(2) Linux Programmer's Manual STAT(2)
...
int stat(const char *path, struct stat *buf);
...
struct stat {
dev_t st_dev; /* ID of device containing file */
ino_t st_ino; /* inode number */
mode_t st_mode; /* protection */
nlink_t st_nlink; /* number of hard links */
uid_t st_uid; /* user ID of owner */
gid_t st_gid; /* group ID of owner */
dev_t st_rdev; /* device ID (if special file) */
off_t st_size; /* total size, in bytes */
blksize_t st_blksize; /* blocksize for filesystem I/O */
blkcnt_t st_blocks; /* number of blocks allocated */
time_t st_atime; /* time of last access */
time_t st_mtime; /* time of last modification */
time_t st_ctime; /* time of last status change */
};
stat コマンドを使うと stat システム・コールで返される値に近いものが表示
される。
$ ls -l .bashrc
-rw-r--r--. 1 yas prof 241 Jun 19 2015 .bashrc
$ stat .bashrc
File: `.bashrc'
Size: 241 Blocks: 16 IO Block: 65536 regular file
Device: 13h/19d Inode: 29988667 Links: 1
Access: (0644/-rw-r--r--) Uid: ( 1013/ yas) Gid: ( 510/ prof)
Access: 2016-01-31 15:25:29.000000000 +0900
Modify: 2015-06-19 10:40:12.000860000 +0900
Change: 2016-01-30 16:39:59.001034000 +0900
$
図? スーパーブロック、inode、dentry、file
int fd1 = open("file1",O_RDONLY);
int fd2 = open("file1",O_RDONLY);
ファイル名 "file1" で表現されるファイルの inode 構造体は、1 個でも、
file 構造体は、2 個割り当てられる。
ディスク上には対応するデータ構造は存在しない。
linux-4.3.3/include/linux/fs.h
839: struct file {
...
844: struct path f_path;
845: struct inode *f_inode; /* cached value */
846: const struct file_operations *f_op;
...
853: atomic_long_t f_count;
...
855: fmode_t f_mode;
...
857: loff_t f_pos;
...
867: void *private_data;
...
874: struct address_space *f_mapping;
875: } __attribute__((aligned(4))); /* lest something weird decides that 2 is OK */



図? C言語によるオブジェクト指向の継承の実装方法。共通インスタンス変数・関数、固有インスタンス変数関数の置き方
struct fileの操作は、たとえば次のような形で行われる。 第1引数は、struct file *。
struct file *file;
file->f_op->read(file, buf, count, pos);
f_op には、次のような手続きがある。各ファイルシステム
(ext4,nfs,tmpfs,...) ごとに、手続きの実体は異なるが、インタフェースは同じ。
linux-4.3.3/include/linux/fs.h
1613: struct file_operations {
1614: struct module *owner;
1615: loff_t (*llseek) (struct file *, loff_t, int);
1616: ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
1617: ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
1618: ssize_t (*read_iter) (struct kiocb *, struct iov_iter *);
1619: ssize_t (*write_iter) (struct kiocb *, struct iov_iter *);
1620: int (*iterate) (struct file *, struct dir_context *);
1621: unsigned int (*poll) (struct file *, struct poll_table_struct *);
1622: long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
1623: long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
1624: int (*mmap) (struct file *, struct vm_area_struct *);
1625: int (*open) (struct inode *, struct file *);
1626: int (*flush) (struct file *, fl_owner_t id);
1627: int (*release) (struct inode *, struct file *);
1628: int (*fsync) (struct file *, loff_t, loff_t, int datasync);
1629: int (*aio_fsync) (struct kiocb *, int datasync);
1630: int (*fasync) (int, struct file *, int);
1631: int (*lock) (struct file *, int, struct file_lock *);
1632: ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
1633: unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
1634: int (*check_flags)(int);
1635: int (*flock) (struct file *, int, struct file_lock *);
1636: ssize_t (*splice_write)(struct pipe_inode_info *, struct file *, loff_t *, size_t, unsigned int);
1637: ssize_t (*splice_read)(struct file *, loff_t *, struct pipe_inode_info *, size_t, unsigned int);
1638: int (*setlease)(struct file *, long, struct file_lock **, void **);
1639: long (*fallocate)(struct file *file, int mode, loff_t offset,
1640: loff_t len);
1641: void (*show_fdinfo)(struct seq_file *m, struct file *f);
1642: #ifndef CONFIG_MMU
1643: unsigned (*mmap_capabilities)(struct file *);
1644: #endif
1645: };
主な手続きの意味
linux-4.3.3/include/linux/dcache.h
108: struct dentry {
...
113: struct dentry *d_parent; /* parent directory */
114: struct qstr d_name;
115: struct inode *d_inode; /* Where the name belongs to - NULL is
116: * negative */
117: unsigned char d_iname[DNAME_INLINE_LEN]; /* small names */
...
120: struct lockref d_lockref; /* per-dentry lock and refcount */
121: const struct dentry_operations *d_op;
122: struct super_block *d_sb; /* The root of the dentry tree */
...
124: void *d_fsdata; /* fs-specific data */
...
127: struct list_head d_child; /* child of parent list */
128: struct list_head d_subdirs; /* our children */
...
136: };
322: static inline unsigned d_count(const struct dentry *dentry)
323: {
324: return dentry->d_lockref.count;
325: }
326:
30: #define HASH_LEN_DECLARE u32 hash; u32 len;
44: struct qstr {
...
47: HASH_LEN_DECLARE;
...
51: const unsigned char *name;
52: };
102: # define DNAME_INLINE_LEN 40 /* 128 bytes */
linux-4.3.3/include/linux/fs.h
584: struct inode {
585: umode_t i_mode;
586: unsigned short i_opflags;
587: kuid_t i_uid;
588: kgid_t i_gid;
...
596: const struct inode_operations *i_op;
597: struct super_block *i_sb;
...
605: unsigned long i_ino;
...
617: dev_t i_rdev;
618: loff_t i_size;
619: struct timespec i_atime;
620: struct timespec i_mtime;
621: struct timespec i_ctime;
622: spinlock_t i_lock; /* i_blocks, i_bytes, maybe i_size */
623: unsigned short i_bytes;
624: unsigned int i_blkbits;
625: blkcnt_t i_blocks;
...
632: unsigned long i_state;
...
638: struct hlist_node i_hash;
...
651: struct hlist_head i_dentry;
...
655: atomic_t i_count;
...
679: void *i_private; /* fs or device private pointer */
680: };
struct inode *inode;
...
inode->i_op->create(inode, name, mode, true);
i_op には、次のような手続きがある。各ファイルシステム
(ext4,nfs,tmpfs,...) ごとに、手続きの実体は異なるが、インタフェースは同じ。
linux-4.3.3/include/linux/fs.h
1647: struct inode_operations {
1648: struct dentry * (*lookup) (struct inode *,struct dentry *, unsigned int);
1649: const char * (*follow_link) (struct dentry *, void **);
1650: int (*permission) (struct inode *, int);
1651: struct posix_acl * (*get_acl)(struct inode *, int);
1652:
1653: int (*readlink) (struct dentry *, char __user *,int);
1654: void (*put_link) (struct inode *, void *);
1655:
1656: int (*create) (struct inode *,struct dentry *, umode_t, bool);
1657: int (*link) (struct dentry *,struct inode *,struct dentry *);
1658: int (*unlink) (struct inode *,struct dentry *);
1659: int (*symlink) (struct inode *,struct dentry *,const char *);
1660: int (*mkdir) (struct inode *,struct dentry *,umode_t);
1661: int (*rmdir) (struct inode *,struct dentry *);
1662: int (*mknod) (struct inode *,struct dentry *,umode_t,dev_t);
1663: int (*rename) (struct inode *, struct dentry *,
1664: struct inode *, struct dentry *);
1665: int (*rename2) (struct inode *, struct dentry *,
1666: struct inode *, struct dentry *, unsigned int);
1667: int (*setattr) (struct dentry *, struct iattr *);
1668: int (*getattr) (struct vfsmount *mnt, struct dentry *, struct kstat *);
1669: int (*setxattr) (struct dentry *, const char *,const void *,size_t,int);
1670: ssize_t (*getxattr) (struct dentry *, const char *, void *, size_t);
1671: ssize_t (*listxattr) (struct dentry *, char *, size_t);
1672: int (*removexattr) (struct dentry *, const char *);
1673: int (*fiemap)(struct inode *, struct fiemap_extent_info *, u64 start,
1674: u64 len);
1675: int (*update_time)(struct inode *, struct timespec *, int);
1676: int (*atomic_open)(struct inode *, struct dentry *,
1677: struct file *, unsigned open_flag,
1678: umode_t create_mode, int *opened);
1679: int (*tmpfile) (struct inode *, struct dentry *, umode_t);
1680: int (*set_acl)(struct inode *, struct posix_acl *, int);
1681:
1682: /* WARNING: probably going away soon, do not use! */
1683: } ____cacheline_aligned;
linux-4.3.3/include/linux/fs.h
1289: struct super_block {
...
1294: loff_t s_maxbytes; /* Max file size */
1295: struct file_system_type *s_type;
1296: const struct super_operations *s_op;
...
1303: struct dentry *s_root;
...
1326: void *s_fs_info; /* Filesystem private info */
...
1374: struct list_lru s_dentry_lru ____cacheline_aligned_in_smp;
1375: struct list_lru s_inode_lru ____cacheline_aligned_in_smp;
...
1388: struct list_head s_inodes; /* all inodes */
1389: };
p->files->fd_array[fd] の struct file を表
す。
linux-4.3.3/include/linux/sched.h
1378: struct task_struct {
...
1560: struct files_struct *files;
...
1823: };
linux-4.3.3/include/linux/fdtable.h
45: struct files_struct {
...
62: struct file __rcu * fd_array[NR_OPEN_DEFAULT];
63: };
22: #define NR_OPEN_DEFAULT BITS_PER_LONG
linux-4.3.3/include/asm-generic/bitsperlong.h
7: #ifdef CONFIG_64BIT
8: #define BITS_PER_LONG 64
9: #else
10: #define BITS_PER_LONG 32
11: #endif /* CONFIG_64BIT */
図? task_struct、ファイル記述子、file構造体、その他
linux-4.3.3/fs/read_write.c
562: SYSCALL_DEFINE3(read, unsigned int, fd, char __user *, buf, size_t, count)
563: {
564: struct fd f = fdget_pos(fd);
565: ssize_t ret = -EBADF;
566:
567: if (f.file) {
568: loff_t pos = file_pos_read(f.file);
569: ret = vfs_read(f.file, buf, count, &pos);
570: if (ret >= 0)
571: file_pos_write(f.file, pos);
572: fdput_pos(f);
573: }
574: return ret;
575: }
linux-4.3.3/include/linux/file.h
29: struct fd {
30: struct file *file;
31: unsigned int flags;
32: };
linux-4.3.3/fs/read_write.c
440: ssize_t vfs_read(struct file *file, char __user *buf, size_t count, loff_t *pos)
441: {
442: ssize_t ret;
443:
444: if (!(file->f_mode & FMODE_READ))
445: return -EBADF;
446: if (!(file->f_mode & FMODE_CAN_READ))
447: return -EINVAL;
448: if (unlikely(!access_ok(VERIFY_WRITE, buf, count)))
449: return -EFAULT;
450:
451: ret = rw_verify_area(READ, file, pos, count);
452: if (ret >= 0) {
453: count = ret;
454: ret = __vfs_read(file, buf, count, pos);
455: if (ret > 0) {
456: fsnotify_access(file);
457: add_rchar(current, ret);
458: }
459: inc_syscr(current);
460: }
461:
462: return ret;
463: }
linux-4.3.3/fs/ext4/file.c
696: const struct file_operations ext4_file_operations = {
697: .llseek = ext4_llseek,
698: .read_iter = generic_file_read_iter,
699: .write_iter = ext4_file_write_iter,
700: .unlocked_ioctl = ext4_ioctl,
701: #ifdef CONFIG_COMPAT
702: .compat_ioctl = ext4_compat_ioctl,
703: #endif
704: .mmap = ext4_file_mmap,
705: .open = ext4_file_open,
706: .release = ext4_release_file,
707: .fsync = ext4_sync_file,
708: .splice_read = generic_file_splice_read,
709: .splice_write = iter_file_splice_write,
710: .fallocate = ext4_fallocate,
711: };
713: const struct inode_operations ext4_file_inode_operations = {
...
723: };
linux-4.3.3/fs/ext4/super.c
1121: static const struct super_operations ext4_sops = {
...
1141: };
linux-4.3.3/fs/ext4/ext4.h
814: struct ext4_inode_info {
...
872: struct inode vfs_inode;
...
955: };
1378: static inline struct ext4_inode_info *EXT4_I(struct inode *inode)
1379: {
1380: return container_of(inode, struct ext4_inode_info, vfs_inode);
1381: }
linux-4.3.3/include/linux/kernel.h
803: /**
804: * container_of - cast a member of a structure out to the containing structure
805: * @ptr: the pointer to the member.
806: * @type: the type of the container struct this is embedded in.
807: * @member: the name of the member within the struct.
808: *
809: */
810: #define container_of(ptr, type, member) ({ \
811: const typeof( ((type *)0)->member ) *__mptr = (ptr); \
812: (type *)( (char *)__mptr - offsetof(type,member) );})
813:

図? Ext4 ファイルシステムで使う構造体 ext4_inode_info での struct inode の保持
linux-4.3.3/mm/filemap.c
1714: ssize_t
1715: generic_file_read_iter(struct kiocb *iocb, struct iov_iter *iter)
1716: {
1717: struct file *file = iocb->ki_filp;
1718: ssize_t retval = 0;
1719: loff_t *ppos = &iocb->ki_pos;
1720: loff_t pos = *ppos;
...
1758:
1759: retval = do_generic_file_read(file, ppos, iter, retval);
1760: out:
1761: return retval;
1762: }
linux-4.3.3/mm/filemap.c
1487: static ssize_t do_generic_file_read(struct file *filp, loff_t *ppos,
1488: struct iov_iter *iter, ssize_t written)
1489: {
1490: struct address_space *mapping = filp->f_mapping;
1491: struct inode *inode = mapping->host;
...
1493: pgoff_t index;
...
1496: unsigned long offset; /* offset into pagecache page */
...
1498: int error = 0;
...
1500: index = *ppos >> PAGE_CACHE_SHIFT;
...
1504: offset = *ppos & ~PAGE_CACHE_MASK;
...
1506: for (;;) {
1507: struct page *page;
...
1510: unsigned long nr, ret;
...
1514: page = find_get_page(mapping, index);
1515: if (!page) {
1516: page_cache_sync_readahead(mapping,
1517: ra, filp,
1518: index, last_index - index);
1519: page = find_get_page(mapping, index);
...
1522: }
...
1559: /* nr is the maximum number of bytes to copy from this page */
1560: nr = PAGE_CACHE_SIZE;
...
1568: nr = nr - offset;
...
1590: ret = copy_page_to_iter(page, offset, nr, iter);
1591: offset += ret;
1592: index += offset >> PAGE_CACHE_SHIFT;
1593: offset &= ~PAGE_CACHE_MASK;
...
1596: page_cache_release(page);
1597: written += ret;
1598: if (!iov_iter_count(iter))
1599: goto out;
...
1604: continue;
...
1694: }
1695:
1696: out:
1701: *ppos = ((loff_t)index << PAGE_CACHE_SHIFT) + offset;
1702: file_accessed(filp);
1703: return written ? written : error;
1704: }
void f(int arg1, int arg2) {
省略;
}
これを実現するために、どのような Tasklet のハンドラと初期化コードを書け
ばよいか。以下の空欄を埋めなさい。
void tasklet_handler(unsigned long data) { /* Tasklet ハンドラ */
int arg1, arg2;
arg1 = 省略;
arg2 = 省略;
/*空欄(a)*/
その他の仕事;
}
DECLARE_TASKLET(/*空欄(b)*/, /*空欄(c)*/, 0); /* 構造体の初期化 */
注意: 構造体の名前は、次の問題の解答で利用する。それらしいものを付けな
さい。
irqreturn_t irq_handler(int irq, void *dev) {
/*空欄(d)*/
return IRQ_HANDLED;
}
int vfs_fsync_range(struct file *file, loff_t start, loff_t end, int datasync)
{
struct inode *inode = file->f_mapping->host;
if (!file->f_op->/*空欄(e)*/)
return -EINVAL;
/*中略*/
return file->f_op->/*空欄(f)*/(/*空欄(g)*/, start, end, datasync);
}