Archive for October, 2014

VFS Data Structure关系(1)

October 20th, 2014

 VFS是管理具体文件系统的接口,Linux可支持数十种文件系统,不同的文件系统可以同时共存于一个系统之中。这些不同类型的文件系统并不是各自封闭的,会进行文件复制和移动等。

VFS是在各种具体的文件系统之上建立了一个抽象层,它屏蔽了不同文件系统间的差异。它之所以可以将各种文件系统纳入其中,是因为它提供了一个通用的文件系统模型。

VFS主要通过一组数据结构来描述文件对象。其中有四个基本的结构体:

超级块(struct super_block):它描述一个已安装了的文件系统。

索引结点(struct inode):它描述一个文件。

目录项(strcut dentry):它描述文件系统的层次结构。一个完整路径的每个组成部分都是一个目录项。比如打开/home/lzz/code/hello.c时,内核分别为/,home/,lzz/,code/,hello.c创建相应的目录项。

文件(struct file):它描述一个已被进程打开的文件。

位置:

block

VFS采用面向对象的思想,在上述每一个结构体中即包含描述每个文件对象属性的数据,又包含对这些数据进行操作的函数指针结构体。也就是说,上述四个基本的结构体中,每一个结构体中又嵌套了一个子结构体,这个子结构体包含了对父结构体进行各种操作的函数指针。

struct dentry (include/linux/dcache.h)

为了方便对目标文件的快速查找,VFS引入了目录项。目标文件路径中的每一项都代表一个目录项,比如/home/test.c中,/,home,test.c都分别是一个目录项。这些目录项都属于路径的一部分,并且每个目录项都与其对应的inode相联系。如果VFS得到了某个dentry,那么也就随之得到了这个目录项所对应文件的inode,这样就可以对这个inode所对应的文件进行相应操作。所以,依次沿着目标文件路径中各部分的目录项进行搜索,最终则可找到目标文件的inode。

与超级块和索引结点不同的是,目录项在磁盘上并没有对应的实体文件,它会在需要时候现场被创建。因此,在目录项结构体中并没有脏数据字段,因为目录项并不会涉及重写到磁盘。

d_inode:与该目录项相关联的索引结点;

struct super_block (include/linux/fs.h)

超级块结构代表一个已经安装了的文件系统,其存储该文件系统的有关信息。对于一个基于磁盘的文件系统来说,这类对象存放于磁盘的特定扇区中;对于非基于磁盘的文件系统,它会在该文件系统的使用现场创建超级块结构并存放在内存中。

s_inode 代表该文件系统中所有的索引结点形成一个双联表,该字段存放这个链表的头结点;

s_files:该文件系统中所有已被打开的文件形成一个双联表,该字段存放这个链表的头结点;

struct file(include/linux/fs.h)

每当一个进程打开一个文件时,内存中有会有相应的file结构体。因此,当一个文件被多个进程打开时,这个文件就会有多个对应的文件结构体。但是,这些文件结构体对应的索引结点和目录项却是唯一的

struct inode (include/linux/fs.h)

索引结点结构体用来描述存放在磁盘上的文件信息。每当内核对磁盘上的文件进行操作时,就会将该文件的信息填充到一个索引结点可以代表一个普通的文件,也可以代表管道或者设备文件等这样的特殊文件

i_sb_list:每个文件系统中的inode都会形成一个双联表,这个双链表的头结点存放在超级块的s_inodes中。而该字段中的prev和next指针分别指向在双链表中与其相邻的前后两个元素;

i_list:VFS中使用四个链表来管理不同状态的inode结点。inode_unused将当前未使用的inode链接起来,inode_in_use将当前正在被使用的inode链接起来,超级块中的s_dirty将所有脏inode链接起来,i_hash将所有hash值相同的inode链接起来。i_list中包含prev和next两个指针,分别指向与当前inode处于同一个状态链表的前后两个元素。

VFS

 

关于此图的说明:

1. 图中平行结构之间的箭头表示这两者之间仍有有若干个类似结点相连接;

PS:在linux 3.14.8 中,从task_struct到struct file有一个过程:

task_struct -> struct files_struct -> struct file -> struct path -> struct dentry

2. 图中阴影部分所示的进程并不是以实际的关系来表示的;

3. 图中彩色线条示意的场景:三个进程分别打开同一个文件。进程1和进程2打开同一路径的文件,因此两者的打开文件对应同一个目录项;而进程3打开的是一个硬链接文件,因此对应的目录项与前两者不同;

4.索引结点中i_sb_list链表是链接一个文件系统中所有inode的链表,因此相邻的inode之间均会由此链表链接;而i_list链接的是处于同一个状态的所有inode。所以,相邻inode之间并不一定链接在一起。

 

具有健壮性的文件IO函数

October 13th, 2014

在理想环境下,我们使用linux下的read()write()函数可以依照我们想读的字节数读到buffer中。并没有考虑函数返回值的问题。

以read为例

static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
    int cnt;

    while (rp->rio_cnt <= 0) {  /* refill if buf is empty */
	rp->rio_cnt = read(rp->rio_fd, rp->rio_buf, 
			   sizeof(rp->rio_buf));
	if (rp->rio_cnt < 0) {
	    if (errno != EINTR) /* interrupted by sig handler return */
		return -1;
	}
	else if (rp->rio_cnt == 0)  /* EOF */
	    return 0;
	else 
	    rp->rio_bufptr = rp->rio_buf; /* reset buffer ptr */
    }

    /* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */
    cnt = n;          
    if (rp->rio_cnt < n)   
	cnt = rp->rio_cnt;
    memcpy(usrbuf, rp->rio_bufptr, cnt);
    rp->rio_bufptr += cnt;
    rp->rio_cnt -= cnt;
    return cnt;
}
ssize_t rio_readn(int fd, void *usrbuf, size_t n) 
{
 size_t nleft = n;
 ssize_t nread;
 char *bufp = usrbuf;

 while (nleft > 0) {
 if ((nread = read(fd, bufp, nleft)) < 0) {
 if (errno == EINTR) /* interrupted by sig handler return */
 nread = 0; /* and call read() again */
 else
 return -1; /* errno set by read() */ 
 } 
 else if (nread == 0)
 break; /* EOF */
 nleft -= nread;
 bufp += nread;
 }
 return (n - nleft); /* return >= 0 */
}

我们看到read返回值是有可能小于要求sizoof(buffer)的值,这种现象在kernel character device与network中非常普遍!

另外,read()应该也要处理用户发来的信号,如果遇到sigal信号,要使得返回值置0,并使得buffer指针的移动。

所以我们要注意,并进行比较。

比如在http://www.lizhaozhong.info/archives/1066中read也是实现了类似的思想。

维护一个len与count的关系,每次调用read函数都是确保len减去一个count大小的buffer,直到len<count,然后len赋值为count。

write函数也是类似,只不过len与count之间主要做加法。

 

具有阻塞操作的字符设备驱动

October 13th, 2014

http://www.lizhaozhong.info/archives/1062

在上面这篇文章里面,我们做的是一个简单的非阻塞操作的字符设备,也就是说对于这个设备的操作要么放弃,要么不停的轮询,直到操作可以进行下去。

而支持阻塞设备的字符操作,我们可以实现读操作或者写操作的睡眠。这就是我们要完成的操作。

关于程序的框架,与之前的其实是类似的,比如我们在全局设定一个等待队列头。

#define MYCDEV_SIZE 100
#define DEVICE_NAME "lzz_block_cdev"

static char globalmem[MYCDEV_SIZE];
static wait_queue_head_t rdwait;
static wait_queue_head_t wrwait;
static struct semaphore mutex;

static int len;
ssize_t myblock_read(struct file*,char*,size_t count,loff_t*);
ssize_t myblock_write(struct file*,char*,size_t count,loff_t*);
ssize_t mycdev_open(struct inode *inode, struct file *fp);
ssize_t mycdev_release(struct inode *inode, struct file *fp);

在模块初始化中,首先要初始化mutex,rdwait,wrwait。

static int __init mycdev_init(void)
{
	int ret;

	printk("myblock module is working..\n");

	ret=register_chrdev(MYCDEV_MAJOR,DEVICE_NAME,&fops);
	if(ret<0)
	{
		printk("register failed..\n");
		return 0;
	}
	else
	{
		printk("register success..\n");
	}
	sema_init(&mutex,1);
	init_waitqueue_head(&rdwait);
	init_waitqueue_head(&wrwait);

	return 0;
}

先创建一个代表当前进程的等待队列结点wait,并把它加入到读等待队列当中。

当共享数据区的数据长度为0时,就阻塞该进程。因此,在循环中,首先将当前进程的状态设置TASK_INTERRUPTIBLE。

然后利用schedule函数进行重新调度,此时,读进程才会真正的睡眠,直至被写进程唤醒。在睡眠途中,如果用户给读进程发送了信号,那么也会唤醒睡眠的进程。

当共享数据区有数据时,会将count字节的数据拷贝到用户空间,并且唤醒正在睡眠的写进程。当上述工作完成后,会将当前进程从读等待队列中移除,并且将当前进程的状态设置为TASK_RUNNING。

关于从全局缓冲区移出已读数据,这里要特别说明一下。这里利用了memcpy函数将以(globalmem+count)开始的(len-count)字节的数据移动到缓冲区最开始的地方。

在调用schedule函数退出CPU后,下次唤醒后进入运行时将从schedule语句的下一条语句开始,即if (signal_pending(current)) 语句。

signal_pending(current)检查当前进程是否有信号处理,若要处理就返回非0!然后这个函数退出,插入到等待队列,等待下次重新开始执行!

ssize_t myblock_read(struct file*fp,char*buf,size_t count,loff_t*offp)
{
	int ret;
	DECLARE_WAITQUEUE(wait,current);

	down(&mutex);
	add_wait_queue(&rdwait,&wait);

	while(len==0)
	{
		__set_current_state(TASK_INTERRUPTIBLE);
		up(&mutex);
		schedule();
		if(signal_pending(current))
		{
			ret=-1;
			goto signal_out;
		}

		down(&mutex);
	}

	if(count>len)
	{
		count=len;
	}

	if(copy_to_user(buf,globalmem,count)==0)
	{
		memcpy(globalmem,globalmem+count,len-count);
		len-=count;
		printk("read %d bytes\n",count);
		wake_up_interruptible(&wrwait);
		ret=count;
	}
	else
	{
		ret=-1;
		goto copy_err_out;
	}

copy_err_out:up(&mutex);
signal_out:remove_wait_queue(&rdwait,&wait);

	set_current_state(TASK_RUNNING);
	return ret;
}

写函数的控制流程大致与读函数相同,只不过对应的等待队列是写等待队列。
唤醒后如何执行。无论因哪种方式而睡眠,当读进程被唤醒后,均顺序执行接下来的代码。

ssize_t myblock_write(struct file*fp,char*buf,size_t count,loff_t*offp)
{
	int ret;
	DECLARE_WAITQUEUE(wait,current);

	down(&mutex);
	add_wait_queue(&wrwait,&wait);

	while(len==MYCDEV_SIZE)
	{
		__set_current_state(TASK_INTERRUPTIBLE);
		up(&mutex);
		schedule();
		if(signal_pending(current))
		{
			ret=-1;
			goto signal_out;
		}

         	down(&mutex);
	}
	if(count>(MYCDEV_SIZE-len))
	{
		count=MYCDEV_SIZE-len;
	}

	if(copy_from_user(globalmem+len,buf,count)==0)
	{
		len=len+count;
		printk("written %d bytes\n",count);
		wake_up_interruptible(&rdwait);
		ret=count;
	}
	else
	{
		ret=-1;
		goto COPY_ERR_OUT;
	}

signal_out:up(&mutex);
COPY_ERR_OUT:remove_wait_queue(&wrwait,&wait);
	set_current_state(TASK_RUNNING);

	return ret;
}

读写函数down操作和add_wait_queue操作交换,可能会造成死锁。

up操作和remove_wait_queue操作交换。如果读进程从内核空间向用户空间拷贝数据失败时,就会从up往后执行。

因为读进程是在获得信号量后才拷贝数据的,因此必须先释放信号量,再将读进程对应的等待队列项移出读等待队列。而当读进程因信号而被唤醒时,则直接跳转到remove_wait_queue操作,并往后执行(仅仅只是睡眠了,wake_up后继续向后执行)。

此时读进程并没有获得信号量,因此只需要移出队列操作即可。如果交换上述两个操作,读进程移出等待队列时还未释放互斥信号量,那么写进程就不能写。而当读进程因信号而唤醒时,读进程并没有获得信号量,却还要释放信号量。

设想一种情况:

while(len==0)
	{
		__set_current_state(TASK_INTERRUPTIBLE);
		up(&mutex);
		schedule();
		if(signal_pending(current))
		{
			ret=-1;
			goto signal_out;
		}

		down(&mutex);
	}

当schedule()重新调度该程序,从if()开始执行遭遇用户的Ctrl+C ,就会跳入signal_out。如果没有用户信号,因为在schedule()前已经up()了,所以接下来要拷贝数据,使用down()

对于goto操作:就是从Label以后,一直往后执行,并不是执行一条语句而已。

使用模块的方式,上篇博文说的很清楚。
使用的时候:

  • 终端输入:cat /dev/blockcdev&;即从字符设备文件中读数据,并让这个读进程在后台执行,可通过ps命令查看到这个进程;

  • 中断继续输入:echo ‘I like eating..’ > /dev/blockcdev;即向字符设备文件中写入数据;

 

实践字符设备驱动

October 7th, 2014

我们都知道在linux里面存在块设备与字符设备。我们这里是设计的字符驱动,在不久,我会加入支持阻塞的功能。

我们可以通过查看cat /proc/device查看已注册的设备

[lzz@localhost device_character]$ cat /proc/devices
Character devices:
  1 mem
  4 /dev/vc/0
  4 tty
  4 ttyS
  5 /dev/tty
  5 /dev/console
  5 /dev/ptmx
  7 vcs
 10 misc
 13 input
 14 sound
 21 sg
 29 fb
 99 ppdev
116 alsa
128 ptm
136 pts
162 raw
180 usb
188 ttyUSB
189 usb_device
202 cpu/msr
203 cpu/cpuid
226 drm
250 hidraw
251 usbmon
252 bsg
253 watchdog
254 rtc

Block devices:
259 blkext
  8 sd
  9 md
 11 sr
 65 sd
 66 sd
 67 sd
 68 sd
 69 sd
 70 sd
 71 sd
128 sd
129 sd
130 sd
131 sd
132 sd
133 sd
134 sd
135 sd
253 device-mapper
254 mdp

我们选取一个231作为我们字符设备号,别的不废话,上代码.

字符设备驱动程序:

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/fs.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/mm.h>
#include <linux/vmalloc.h>
#include <linux/slab.h>
#include <asm/io.h>
#include <linux/mman.h>
#include <linux/uaccess.h>

MODULE_AUTHOR("lzz");
MODULE_LICENSE("GPL");

#define MYCDEV_MAJOR 231 /*the predefined mycdev's major devno*/
#define MYCDEV_SIZE 100

static char kernel_buf[MYCDEV_SIZE];

static int mycdev_open(struct inode *inode, struct file *fp)
{
 return 0;
}

static int mycdev_release(struct inode *inode, struct file *fp)
{
 return 0;
}

static ssize_t mycdev_read(struct file *fp, char __user *buf, size_t size, loff_t *pos)
{

 unsigned long p = *pos;
 unsigned int count = size;
// int i;

 if(p >= MYCDEV_SIZE)
 return -1;
 if(count > MYCDEV_SIZE)
 count = MYCDEV_SIZE - p;

 if (copy_to_user(buf, kernel_buf, count) != 0) 
 {
 printk("read error!\n");
 return -1;
 }

 printk("lzz's reader: %d bytes was read...\n", count);
 return count;

}

static ssize_t mycdev_write(struct file *fp, const char __user *buf, size_t size, loff_t *pos)
{
 unsigned long p = *pos;
 unsigned int count = size;
 int ret =0;

 if(copy_from_user(kernel_buf+p,buf,count))
 ret = -EFAULT;
 else
 {
 *pos+=count;
 ret = count;
 printk("lzz's write: %d bytes was wroten...\n", count);
 }
 return ret;
}

/*filling the mycdev's file operation interface in the struct file_operations*/
static const struct file_operations mycdev_fops =
{
 .owner = THIS_MODULE,
 .read = mycdev_read,
 .write = mycdev_write,
 .open = mycdev_open,
 .release = mycdev_release,
};

/*module loading function*/
static int __init mycdev_init(void)
{
 int ret;

 printk("mycdev module is staring..\n");

 ret=register_chrdev(MYCDEV_MAJOR,"lzz_cdev",&mycdev_fops);
 if(ret<0)
 {
 printk("register failed..\n");
 return 0;
 }
 else
 {
 printk("register success..\n");
 } 

 return 0;
}

/*module unloading function*/
static void __exit mycdev_exit(void)
{
 printk("mycdev module is leaving..\n");
 unregister_chrdev(MYCDEV_MAJOR,"lzz_cdev");
}

module_init(mycdev_init);
module_exit(mycdev_exit);

Makefile文件:

obj-m:= map_driver.o

CURRENT_PATH:=$(shell pwd)

LINUX_KERNEL:=$(shell uname -r)

LINUX_KERNEL_PATH:=/lib/modules/$(LINUX_KERNEL)/build

all:
 make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules

clean:
 make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean

用户态测试程序:

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>

int main()
{
 int testdev;
 int i, ret;
 char buf[100]="test lzz's cdev ok!";
 char buff[100];

 testdev = open("/dev/mycdev", O_RDWR);

 if (-1 == testdev) {
 printf("cannot open file.\n");
 exit(1);
 }

 write(testdev,buf,sizeof(buf)-1);

 if ((ret = read(testdev, buff, sizeof(buff)-1)) < 0) {
 printf("read error!\n");
 exit(1);
 }

 printf("%s\n", buff);

 close(testdev);

 return 0;
}

使用方法:
1.make编译map_driver.c文件,并插入到内核;
2.通过cat /proc/devices 查看系统中未使用的字符设备主设备号,比如当前231未使用;
3.创建设备文件结点:sudo mknod /dev/mycdev c 231 0;具体使用方法通过man mknod命令查看;
4.修改设备文件权限:sudo chmod 777 /dev/mycdev;(可选)
5.以上成功完成后,编译本用户态测试程序;运行该程序查看结果;
6.通过dmesg查看日志信息;

Screenshot from 2014-10-07 22:10:11

内核锁的使用

October 6th, 2014

内核锁有三种形态:

  • 原子操作
  • spinlock
  • semaphore

1.原子结构

typedef struct {
    int counter;
} atomic_t;

不能直接赋值,需要使用函数比如ATOMIC_INIT()等初始化等函数(arch/alpha/include/asm/atomic.h)
初始化宏的源码很明显的说明了如何初始化一个原子变量。我们在定义一个原子变量时可以这样的使用它:

atomic_t v=ATOMIC_INIT(0);

atomic_set函数可以原子的设置一个变量的值。

2.获取原子变量的值

23static inline int atomic_read(const atomic_t *v)
24{
25        return (*(volatile int *)&(v)->counter);
26}

返回原子型变量v中的counter值。关键字volatile保证&(v->counter)的值固定不变,以确保这个函数每次读入的都是原始地址中的值。

3.原子变量的加与减

47static inline void atomic_add(int i, atomic_t *v)
48{
49        asm volatile(LOCK_PREFIX "addl %1,%0"
50                     : "+m" (v->counter)
51                     : "ir" (i));
52}

61static inline void atomic_sub(int i, atomic_t *v)
62{
63        asm volatile(LOCK_PREFIX "subl %1,%0"
64                     : "+m" (v->counter)
65                     : "ir" (i));
66}

加减操作中使用了内联汇编语句。linux中的汇编语句都采用AT&T指令格式。

 

2.自旋锁spinlock(include/linux/spinlock_types.h)

typedef struct spinlock {
    union {
        struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
        struct {
            u8 __padding[LOCK_PADSIZE];
            struct lockdep_map dep_map;
        };
#endif
    };
} spinlock_t;

自旋锁的使用:

1.定义初始化自旋锁

使用下面的语句就可以先定一个自旋锁变量,再对其进行初始化:

spinlock_t lock;
spin_lock_init(&lock);

2.获得自旋锁

void spin_lock(spinlock_t*);
int spin_trylock(spinlock_t*);

使用spin_lock(&lock)这样的语句来获得自旋锁。如果一个线程可以获得自旋锁,它将马上返回;否则,它将自旋至自旋锁的保持者释放锁。

另外可以使用spin_trylock(&lock)来试图获得自旋锁。如果一个线程可以立即获得自旋锁,则返回真;否则,返回假,此时它并不自旋。

3.释放自旋锁

void spin_unlock(spinlock_t*);

使用spin_unlock(&lock)来释放一个已持有的自旋锁。注意这个函数必须和spin_lock或spin_trylock函数配套使用。

3.信号量semaphore(include/linux/semaphore.h)

struct semaphore {
    raw_spinlock_t      lock;
    unsigned int        count;
    struct list_head    wait_list;
};

#define __SEMAPHORE_INITIALIZER(name, n)                \
{                                   \
    .lock       = __RAW_SPIN_LOCK_UNLOCKED((name).lock),    \
    .count      = n,                        \
    .wait_list  = LIST_HEAD_INIT((name).wait_list),     \
}

#define DEFINE_SEMAPHORE(name)  \
    struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1)

static inline void sema_init(struct semaphore *sem, int val)
{
    static struct lock_class_key __key;
    *sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val);
    lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0);
}

extern void down(struct semaphore *sem);
extern int __must_check down_interruptible(struct semaphore *sem);
extern int __must_check down_killable(struct semaphore *sem);
extern int __must_check down_trylock(struct semaphore *sem);
extern int __must_check down_timeout(struct semaphore *sem, long jiffies);
extern void up(struct semaphore *sem);

信号量(semaphore)是保护临界区的一种常用方法。它的功能与自旋锁相同,只能在得到信号量的进程才能执行临界区的代码。但是和自旋锁不同的是,一个进程不能获得信号量时,它会进入睡眠状态而不是自旋。

semaphore的使用

1.定义初始化信号量

使用下面的代码可以定义并初始化信号量sem:

struct semaphore sem;
sema_init(&sem,val);

其中val即为信号量的初始值。

除上面的方法,可以使用下面的两个宏定义并初始化信号量:

DECLARE_MUTEX(name);

DECLARE_MUTEX_LOCKED(name);

其中name为变量名。

2.获得信号量

down(&sem);

进程使用该函数时,如果信号量值此时为0,则该进车会进入睡眠状态,因此该函数不能用于中断上下文中。

down_interruptibale(&sem);

该函数与down函数功能类似,只不过使用down而睡眠的进程不能被信号所打断,而使用down_interruptibale的函数则可以被信号打断。

如果想要在中断上下文使用信号量,则可以使用下面的函数:

dwon_try(&sem);

使用该函数时,如果进程可以获得信号量,则返回0;否则返回非0值,不会导致睡眠。

3.释放信号量

up(&sem);

该函数会释放信号量,如果此时等待队列中有进程,则唤醒一个。

三种比较常用的互斥方式

需求 建议加锁的方法
低开销加锁 优先使用自旋锁
短期加锁 优先使用自旋锁
长期加锁 优先使用信号量
中断上下文加锁 使用自旋锁
持有锁时需要睡眠 使用信号量

自旋锁是忙等锁。当其他线程持有自旋锁时,如果另有线程想获得该锁,那么就只能循环的等待。这样忙的功能对CPU来说是极大的浪费。因此只有当由自旋锁保护的临界区执行时间很短时,使用自旋锁才比较合理。

spinlock.c
sharelist.c