2014年01月30日
情報科学類 オペレーティングシステム II
筑波大学 システム情報工学研究科
コンピュータサイエンス専攻, 電子・情報工学系
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2013/2014-01-30
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/
試験について
linux-3.12.6/kernel/sys.c
227: /*
228: * Ugh. To avoid negative return values, "getpriority()" will
229: * not return the normal nice-value, but a negated value that
230: * has been offset by 20 (ie it returns 40..1 instead of -20..19)
231: * to stay compatible.
232: */
233: SYSCALL_DEFINE2(getpriority, int, which, int, who)
234: {
235: struct task_struct *g, *p;
236: struct user_struct *user;
237: const struct cred *cred = current_cred();
238: long niceval, retval = -ESRCH;
239: struct pid *pgrp;
240: kuid_t uid;
241:
242: if (which > PRIO_USER || which < PRIO_PROCESS)
243: return -EINVAL;
...
247: switch (which) {
248: case PRIO_PROCESS:
249: if (who)
250: p = find_task_by_vpid(who);
251: else
252: p = current;
253: if (p) {
254: niceval = 20 - task_nice(p);
255: if (niceval > retval)
256: retval = niceval;
257: }
258: break;
259: case PRIO_PGRP:
...
259: case PRIO_PGRP:
...
270: case PRIO_USER:
...
289: }
...
294: return retval;
295: }
linux-3.12.6/include/linux/sched/rt.h
17: #define MAX_USER_RT_PRIO 100
18: #define MAX_RT_PRIO MAX_USER_RT_PRIO
19:
20: #define MAX_PRIO (MAX_RT_PRIO + 40)
21: #define DEFAULT_PRIO (MAX_RT_PRIO + 20)
linux-3.12.6/kernel/sched/sched.h
28: #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
29: #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
30: #define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
linux-3.12.6/kernel/sched/core.c
3200: int task_nice(const struct task_struct *p)
3201: {
3202: return TASK_NICE(p);
3203: }
解決策:
図? ファイル・システム実現に置ける層構造
ディスク・キャッシュの層もある。解決策
$ ls -l /bin/{gunzip,gzip,zcat} ![[←]](../icons/screen-return.gif)
-rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/gunzip
-rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/gzip
-rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/zcat
$ ls -li /bin/{gunzip,gzip,zcat}
5636134 -rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/gunzip
5636134 -rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/gzip
5636134 -rwxr-xr-x 3 root root 62872 Jan 21 2010 /bin/zcat
$ ![[]](../icons/screen-cursor.gif)
$ cat /etc/fstab
LABEL=/ / ext3 defaults 1 1
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
LABEL=SWAP-sda3 swap swap defaults 0 0
130.158.86.2:/vol/vol1/home /home nfs rw,hard,bg,nfsvers=3,intr 0 0
130.158.86.2:/vol/vol5/local3 /usr/local3 nfs rw,hard,bg,nfsvers=3,intr 0 0
$ df -h
Filesystem Size Used Avail Use% Mounted on
/dev/sda2 222G 13G 198G 6% /
tmpfs 2.0G 0 2.0G 0% /dev/shm
130.158.86.2:/vol/vol1/home
4.0T 1.5T 2.5T 38% /home
130.158.86.2:/vol/vol5/local3
80G 4.9G 76G 7% /usr/local3
$
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 199 Jun 16 2010 .bashrc
$ stat .bashrc
File: .bashrc
Size: 199 Blocks: 8 IO Block: 8192 regular file
Device: 18h/24d Inode: 29525858 Links: 1
Access: (0644/-rw-r--r--) Uid: ( 1013/ yas) Gid: ( 510/ prof)
Access: 2014-01-29 21:54:39.920338000 +0900
Modify: 2010-06-16 16:35:05.146214000 +0900
Change: 2010-06-16 16:35:05.146214000 +0900
$
図? スーパーブロック、inode、dentry、file
int fd1 = open("file1");
int fd2 = open("file1");
ファイル名 "file1" で表現されるファイルの inode 構造体は、1 個でも、
file 構造体は、2 個割り当てられる。
ディスク上には対応するデータ構造は存在しない。
linux-3.12.6/include/linux/fs.h
766: struct file {
...
776: struct path f_path;
777: #define f_dentry f_path.dentry
778: struct inode *f_inode; /* cached value */
779: const struct file_operations *f_op;
...
789: atomic_long_t f_count;
...
791: fmode_t f_mode;
792: loff_t f_pos;
...
802: void *private_data;
...
813: };
図? C言語によるオブジェクト指向の継承の実装方法。共通インスタンス変数・関数、固有インスタンス変数関数の置き方
struct fileの操作は、たとえば次のような形で行われる。 第1引数は、struct file *。
struct file *file;
file->f_op->read(file, buf, count, pos);
f_op には、次のような手続きがある。各ファイルシステム
(ext4,nfs,tmpfs,...) ごとに、手続きの実体は異なるが、インタフェースは同じ。
linux-3.12.6/include/linux/fs.h
1526: struct file_operations {
1527: struct module *owner;
1528: loff_t (*llseek) (struct file *, loff_t, int);
1529: ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
1530: ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
1531: ssize_t (*aio_read) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
1532: ssize_t (*aio_write) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
1533: int (*iterate) (struct file *, struct dir_context *);
1534: unsigned int (*poll) (struct file *, struct poll_table_struct *);
1535: long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
1536: long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
1537: int (*mmap) (struct file *, struct vm_area_struct *);
1538: int (*open) (struct inode *, struct file *);
1539: int (*flush) (struct file *, fl_owner_t id);
1540: int (*release) (struct inode *, struct file *);
1541: int (*fsync) (struct file *, loff_t, loff_t, int datasync);
1542: int (*aio_fsync) (struct kiocb *, int datasync);
1543: int (*fasync) (int, struct file *, int);
1544: int (*lock) (struct file *, int, struct file_lock *);
1545: ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
1546: unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
1547: int (*check_flags)(int);
1548: int (*flock) (struct file *, int, struct file_lock *);
1549: ssize_t (*splice_write)(struct pipe_inode_info *, struct file *, loff_t *, size_t, unsigned int);
1550: ssize_t (*splice_read)(struct file *, loff_t *, struct pipe_inode_info *, size_t, unsigned int);
1551: int (*setlease)(struct file *, long, struct file_lock **);
1552: long (*fallocate)(struct file *file, int mode, loff_t offset,
1553: loff_t len);
1554: int (*show_fdinfo)(struct seq_file *m, struct file *f);
1555: };
主な手続きの意味
linux-3.12.6/include/linux/dcache.h
106: struct dentry {
...
111: struct dentry *d_parent; /* parent directory */
112: struct qstr d_name;
113: struct inode *d_inode; /* Where the name belongs to - NULL is
114: * negative */
...
118: struct lockref d_lockref; /* per-dentry lock and refcount */
...
119: const struct dentry_operations *d_op;
120: struct super_block *d_sb; /* The root of the dentry tree */
...
122: void *d_fsdata; /* fs-specific data */
...
129: struct list_head d_child; /* child of parent list */
...
132: struct list_head d_subdirs; /* our children */
134: };
309: static inline unsigned d_count(const struct dentry *dentry)
310: {
311: return dentry->d_lockref.count;
312: }
31: #define HASH_LEN_DECLARE u32 hash; u32 len;
...
43: struct qstr {
...
46: HASH_LEN_DECLARE;
...
50: const unsigned char *name;
51: };
100: # define DNAME_INLINE_LEN 40 /* 128 bytes */
linux-3.6.8/include/linux/fs.h
782: struct inode {
783: umode_t i_mode;
784: unsigned short i_opflags;
785: kuid_t i_uid;
786: kgid_t i_gid;
...
794: const struct inode_operations *i_op;
795: struct super_block *i_sb;
...
803: unsigned long i_ino;
...
812: const unsigned int i_nlink;
...
815: dev_t i_rdev;
816: loff_t i_size;
817: struct timespec i_atime;
818: struct timespec i_mtime;
819: struct timespec i_ctime;
820: spinlock_t i_lock; /* i_blocks, i_bytes, maybe i_size */
821: unsigned short i_bytes;
822: unsigned int i_blkbits;
823: blkcnt_t i_blocks;
...
830: unsigned long i_state;
...
835: struct hlist_node i_hash;
...
840: struct hlist_head i_dentry;
...
844: atomic_t i_count;
...
870: void *i_private; /* fs or device private pointer */
871: };
struct inode *inode;
...
inode->i_op->create(inode, name, mode, true);
i_op には、次のような手続きがある。各ファイルシステム
(ext3,nfs,tmpfs,...) ごとに、手続きの実体は異なるが、インタフェースは同じ。
linux-3.12.6/include/linux/fs.h
1557: struct inode_operations {
1558: struct dentry * (*lookup) (struct inode *,struct dentry *, unsigned int);
1559: void * (*follow_link) (struct dentry *, struct nameidata *);
1560: int (*permission) (struct inode *, int);
1561: struct posix_acl * (*get_acl)(struct inode *, int);
1562:
1563: int (*readlink) (struct dentry *, char __user *,int);
1564: void (*put_link) (struct dentry *, struct nameidata *, void *);
1565:
1566: int (*create) (struct inode *,struct dentry *, umode_t, bool);
1567: int (*link) (struct dentry *,struct inode *,struct dentry *);
1568: int (*unlink) (struct inode *,struct dentry *);
1569: int (*symlink) (struct inode *,struct dentry *,const char *);
1570: int (*mkdir) (struct inode *,struct dentry *,umode_t);
1571: int (*rmdir) (struct inode *,struct dentry *);
1572: int (*mknod) (struct inode *,struct dentry *,umode_t,dev_t);
1573: int (*rename) (struct inode *, struct dentry *,
1574: struct inode *, struct dentry *);
1575: int (*setattr) (struct dentry *, struct iattr *);
1576: int (*getattr) (struct vfsmount *mnt, struct dentry *, struct kstat *);
1577: int (*setxattr) (struct dentry *, const char *,const void *,size_t,int);
1578: ssize_t (*getxattr) (struct dentry *, const char *, void *, size_t);
1579: ssize_t (*listxattr) (struct dentry *, char *, size_t);
1580: int (*removexattr) (struct dentry *, const char *);
1581: int (*fiemap)(struct inode *, struct fiemap_extent_info *, u64 start,
1582: u64 len);
1583: int (*update_time)(struct inode *, struct timespec *, int);
1584: int (*atomic_open)(struct inode *, struct dentry *,
1585: struct file *, unsigned open_flag,
1586: umode_t create_mode, int *opened);
1587: int (*tmpfile) (struct inode *, struct dentry *, umode_t);
1588: } ____cacheline_aligned;
linux-3.12.6/include/linux/fs.h
1243: struct super_block {
...
1248: loff_t s_maxbytes; /* Max file size */
1249: struct file_system_type *s_type;
1250: const struct super_operations *s_op;
...
1256: struct dentry *s_root;
...
1265: struct list_head s_inodes; /* all inodes */
...
1284: void *s_fs_info; /* Filesystem private info */
...
1331: struct list_lru s_dentry_lru ____cacheline_aligned_in_smp;
1332: struct list_lru s_inode_lru ____cacheline_aligned_in_smp;
1333: };
p->files->fd_array[fd] の struct file を表
す。
linux-3.12.6/include/linux/sched.h
1023: struct task_struct {
...
1203: struct files_struct *files;
...
1414: };
linux-3.12.6/include/linux/fdtable.h
45: struct files_struct {
...
59: struct file __rcu * fd_array[NR_OPEN_DEFAULT];
60: };
![図? p->files->fd_array[fd]](images/task-files-file-dentry-inode.png)
図? task_struct、ファイル記述子、file構造体、その他
linux-3.12.6/fs/read_write.c
499: SYSCALL_DEFINE3(read, unsigned int, fd, char __user *, buf, size_t, count)
500: {
501: struct fd f = fdget(fd);
502: ssize_t ret = -EBADF;
503:
504: if (f.file) {
505: loff_t pos = file_pos_read(f.file);
506: ret = vfs_read(f.file, buf, count, &pos);
507: if (ret >= 0)
508: file_pos_write(f.file, pos);
509: fdput(f);
510: }
511: return ret;
512: }
linux-3.12.6/include/linux/file.h
29: struct fd {
30: struct file *file;
31: int need_put;
32: };
linux-3.12.6/fs/read_write.c
381: ssize_t vfs_read(struct file *file, char __user *buf, size_t count, loff_t *pos)
382: {
383: ssize_t ret;
384:
385: if (!(file->f_mode & FMODE_READ))
386: return -EBADF;
387: if (!file->f_op || (!file->f_op->read && !file->f_op->aio_read))
388: return -EINVAL;
389: if (unlikely(!access_ok(VERIFY_WRITE, buf, count)))
390: return -EFAULT;
391:
392: ret = rw_verify_area(READ, file, pos, count);
393: if (ret >= 0) {
394: count = ret;
395: if (file->f_op->read)
396: ret = file->f_op->read(file, buf, count, pos);
397: else
398: ret = do_sync_read(file, buf, count, pos);
399: if (ret > 0) {
400: fsnotify_access(file);
401: add_rchar(current, ret);
402: }
403: inc_syscr(current);
404: }
405:
406: return ret;
407: }
linux-3.12.6/fs/ext4/file.c
593: const struct file_operations ext4_file_operations = {
594: .llseek = ext4_llseek,
595: .read = do_sync_read,
596: .write = do_sync_write,
597: .aio_read = generic_file_aio_read,
598: .aio_write = ext4_file_write,
599: .unlocked_ioctl = ext4_ioctl,
600: #ifdef CONFIG_COMPAT
601: .compat_ioctl = ext4_compat_ioctl,
602: #endif
603: .mmap = ext4_file_mmap,
604: .open = ext4_file_open,
605: .release = ext4_release_file,
606: .fsync = ext4_sync_file,
607: .splice_read = generic_file_splice_read,
608: .splice_write = generic_file_splice_write,
609: .fallocate = ext4_fallocate,
610: };
611:
612: const struct inode_operations ext4_file_inode_operations = {
...
621: };
622:
linux-3.12.6/fs/ext4/super.c
1081: static const struct super_operations ext4_sops = {
...
1100: };
linux-3.12.6/fs/ext4/ext4.h
802: struct ext4_inode_info {
...
860: struct inode vfs_inode;
...
929: };
...
1323: static inline struct ext4_inode_info *EXT4_I(struct inode *inode)
1324: {
1325: return container_of(inode, struct ext4_inode_info, vfs_inode);
1326: }
linux-3.12.6/include/linux/kernel.h
785: /**
786: * container_of - cast a member of a structure out to the containing structure
787: * @ptr: the pointer to the member.
788: * @type: the type of the container struct this is embedded in.
789: * @member: the name of the member within the struct.
790: *
791: */
792: #define container_of(ptr, type, member) ({ \
793: const typeof( ((type *)0)->member ) *__mptr = (ptr); \
794: (type *)( (char *)__mptr - offsetof(type,member) );}
795:
796: /* Trap pasters of __FUNCTION__ at compile-time */
)
図? Ext4 ファイルシステムで使う構造体 ext4_inode_info での struct inode の保持
図? 割り込み処理の前半部分と後半部分
割り込みハンドラ(前半部)と後半部の役割分担の目安。
注意1: Tasklet は、task 構造体とはまったく関係ない。名前がよくない。
注意2: Softirq という用語を、割り込み処理の後半部という意味で使う人もい る。
注意3: 伝統的なUnixでは、top half は、システム・コールから派生する上位 層の処理、bottom half は、割り込みから派生する下位層の処理の意味で使わ れることがある。Linux では、top half, bottom half は、割り込み処理の前 半部分と後半部分の意味に使う。
Tasklet で１つの仕事は次のような、struct tasklet_struct で表現される。
linux-3.12.6/include/linux/interrupt.h
431: struct tasklet_struct
432: {
433: struct tasklet_struct *next;
434: unsigned long state;
435: atomic_t count;
436: void (*func)(unsigned long);
437: unsigned long data;
438: };
図? 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-3.12.6/drivers/net/wireless/ath/ath9k/ath9k.h
697: struct ath_softc {
...
704: struct tasklet_struct intr_tq;
705: struct tasklet_struct bcon_tasklet;
...
777: };
linux-3.12.6/drivers/net/wireless/ath/ath9k/init.c
675: tasklet_init(&sc->intr_tq, ath9k_tasklet, (unsigned long)sc);
676: tasklet_init(&sc->bcon_tasklet, ath9k_beacon_tasklet,
677: (unsigned long)sc);
linux-3.12.6/drivers/net/wireless/ath/ath9k/main.c
421: irqreturn_t ath_isr(int irq, void *dev)
422: {
..
441: enum ath9k_int status;
...
468: ath9k_hw_getisr(ah, &status); /* NB: clears ISR too */
469: status &= ah->imask; /* discard unasked-for bits */
...
511: if (status & ATH9K_INT_SWBA)
512: tasklet_schedule(&sc->bcon_tasklet);
...
539: if (sched) {
540: /* turn off every interrupt */
541: ath9k_hw_disable_interrupts(ah);
542: tasklet_schedule(&sc->intr_tq);
543: }
544:
545: return IRQ_HANDLED;
...
548: }
353: void ath9k_tasklet(unsigned long data)
354: {
...
419: }
linux-3.12.6/drivers/net/wireless/ath/ath9k/beacon.c
311: void ath9k_beacon_tasklet(unsigned long data)
312: {
...
412: }
キューにつながれる仕事は、Tasklet の仕事とほとんど同じで、関数へのポイ ンタ func と data からなる。処理の主体が、ワーカ・スレッドと呼ばれるカー ネル・レベルのスレッドである所が違う。
$ ps alx
F UID PID PPID PRI NI VSZ RSS WCHAN STAT TTY TIME COMMAND
...
1 0 5 2 0 -20 0 0 worker S< ? 0:00 [kworker/0:0H]
1 0 6 2 20 0 0 0 worker S ? 0:00 [kworker/u:0]
1 0 7 2 0 -20 0 0 worker S< ? 0:00 [kworker/u:0H]
1 0 27 2 20 0 0 0 worker S ? 0:00 [kworker/u:1]
1 0 367 2 0 -20 0 0 worker S< ? 0:00 [kworker/0:1H]
1 0 650 2 0 -20 0 0 worker S< ? 0:00 [kworker/u:1H]
...
1 0 29461 2 20 0 0 0 worker S ? 0:00 [kworker/0:1]
1 0 29482 2 20 0 0 0 worker S ? 0:00 [kworker/0:2]
1 0 29503 2 20 0 0 0 worker S ? 0:00 [kworker/0:0]
1 0 29601 2 20 0 0 0 worker S ? 0:00 [kworker/0:3]
$
汎用の Work Queue のワーカ・スレッドの他に、専用のワーカ・スレッドを作
ることもできる。
linux-3.6.8/include/linux/workqueue.h
18: typedef void (*work_func_t)(struct work_struct *work);
79: struct work_struct {
80: atomic_long_t data;
81: struct list_head entry;
82: work_func_t func;
...
86: };
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ミリ秒で、設定によって異なる。
ssize_t vfs_write(struct file *file, const char __user *buf, size_t count, loff_t *pos)
{
ssize_t ret;
...
ret = rw_verify_area(WRITE, file, pos, count);
if (ret >= 0) {
count = ret;
file_start_write(file);
if (file->f_op->/*空欄(a)*/)
ret = file->f_op->/*空欄(b)*/(/*空欄(c)*/, buf, count, pos);
...
return ret;
}
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;
}