* 在高并发编程中，多次使用IO复用select函数，本篇就来深入剖析一下其内核源码。。。→_→ *

了解poll机制底层原理请戳传送门——IO复用——poll机制内核源代码分析

了解select应用实例请戳传送门——IO复用——select函数应用实例

< – 2017-08-11 23:40 – >
还有一部分代码没贴。。。明天把select这个硬骨头啃下来。。。

< – 2017-08-16 13:32 – >
宿舍没网。。我的流量啊。。因为源代码大部分都在Select.c中。。。所以会有点多。。。看官请直接进sys_select。。。

//linux-2.4.0\fs\Select.c

//提供了6个宏函数，返回要求位图或结果位图中对应的下标元素的值
#define __IN(fds, n)		(fds->in + n)
#define __OUT(fds, n)		(fds->out + n)
#define __EX(fds, n)		(fds->ex + n)
#define __RES_IN(fds, n)	(fds->res_in + n)
#define __RES_OUT(fds, n)	(fds->res_out + n)
#define __RES_EX(fds, n)	(fds->res_ex + n)

//这个元素下标可以同时对应三种位图，所以在一个位图中监听存在就行
#define BITS(fds, n)		(*__IN(fds, n)|*__OUT(fds, n)|*__EX(fds, n))

static int max_select_fd(unsigned long n, fd_set_bits *fds)
{
	unsigned long *open_fds;
	unsigned long set;
	int max;

	/* handle last in-complete long-word first */
	set = ~(~0UL << (n & (__NFDBITS-1)));
	n /= __NFDBITS; //将所监听的文件描述符的个数转化为位图的元素下标
	open_fds = current->files->open_fds->fds_bits+n;
	max = 0; //记录最大的序号
	if (set) {
		set &= BITS(fds, n);
		if (set) {
			if (!(set & ~*open_fds))
				goto get_max;
			return -EBADF;
		}
	}
	while (n) {
		open_fds--;
		n--;
		set = BITS(fds, n); //判断在位图下标位n的元素中是否有要监听的文件描述符
		if (!set) //如果位图中下标为n的元素中没有要监听的文件描述符，就继续寻找
			continue;
		if (set & ~*open_fds)
			return -EBADF;
		if (max) //这里的最大序号可以理解为一个标志位
			continue;
get_max:
		do {
			max++;
			set >>= 1;
		} while (set);
		max += n * __NFDBITS; //再将位图中的元素序号转化为文件描述符对应的个数
	}

	return max;
}

#define BIT(i)		(1UL << ((i)&(__NFDBITS-1)))
#define MEM(i,m)	((m)+(unsigned)(i)/__NFDBITS)
#define ISSET(i,m)	(((i)&*(m)) != 0)
#define SET(i,m)	(*(m) |= (i))

#define POLLIN_SET (POLLRDNORM | POLLRDBAND | POLLIN | POLLHUP | POLLERR)
#define POLLOUT_SET (POLLWRBAND | POLLWRNORM | POLLOUT | POLLERR)
#define POLLEX_SET (POLLPRI)

int do_select(int n, fd_set_bits *fds, long *timeout)
{
	//poll_table类型结构在下面有解释说明
	poll_table table, *wait;
	int retval, i, off;
	long __timeout = *timeout;

 	read_lock(&current->files->file_lock);
 	//计算所监听的文件描述符在位图中的最大的序号是多少，高于这个序号的文件描述符都与本次操作无关
 	//max_select_fd定义在上面
	retval = max_select_fd(n, fds);
	read_unlock(&current->files->file_lock);

	if (retval < 0)
		return retval;
	n = retval;
	
	//当一个进程要进入睡眠，而想要某个设备的驱动程序在设备的状态发生变化时将其唤醒，就要准备一个wait_queue_t数据结构，并将这个数据结构挂入目标设备的某个等待队列中。而wait_queue_t就封装在poll_table类型结构中
	//初始化poll_table类型结构变量，将table成员置为NULL，error成员置为0
	poll_initwait(&table);
	wait = &table;
	if (!__timeout)
		wait = NULL;
	retval = 0;
	//进入for循环，直到所监听的事件就绪，或指定的睡眠等待时间到期，或者当前进程收到了信号时才会结束
	for (;;) {
		set_current_state(TASK_INTERRUPTIBLE); //将当前进程的状态置为可中断阻塞，即当前进程将会进入浅睡眠状态
		//内层for循环中，对所要监视的文件描述符对应的位图进行一次扫描
		for (i = 0 ; i < n; i++) {
			unsigned long bit = BIT(i);
			unsigned long mask;
			struct file *file;

			off = i / __NFDBITS; //将文件描述符的个数i转化为位图中所对应的元素下标off
			if (!(bit & BITS(fds, off))) //如果三种位图的某一位为1，就对相应的文件描述符做一次询问
				continue;
			file = fget(i);
			mask = POLLNVAL;
			//文件的具体询问方式和其类型有关，即是通过file_operations数据结构中的函数指针poll进行的。关于poll操作将会在另一篇文章中总结。。
			if (file) {
				mask = DEFAULT_POLLMASK;
				if (file->f_op && file->f_op->poll)
					mask = file->f_op->poll(file, wait);
				fput(file);
			}
			//retval记录一共有几个事件就绪
			//将询问的输入结果汇集到fds所指的fd_set_bits变量中
			if ((mask & POLLIN_SET) && ISSET(bit, __IN(fds,off))) {
				SET(bit, __RES_IN(fds,off));
				retval++; //记录一共有多少个事件就绪
				wait = NULL;
			}
			//将询问的输出结果汇集到fds所指的fd_set_bits变量中
			if ((mask & POLLOUT_SET) && ISSET(bit, __OUT(fds,off))) {
				SET(bit, __RES_OUT(fds,off));
				retval++; //记录一共有多少个事件就绪
				wait = NULL;
			}
			//将询问的异常结果汇集到fds所指的fd_set_bits变量中
			if ((mask & POLLEX_SET) && ISSET(bit, __EX(fds,off))) {
				SET(bit, __RES_EX(fds,off));
				retval++; //记录一共有多少个事件就绪
				wait = NULL;
			}
		}
		wait = NULL;
		//对所有的文件描述符进行询问后，检查是否有事件就绪、睡眠等待时间超时、接收到了信号，如果有条件满足，就不会再进入睡眠状态，直接结束大循环
		//统计好就绪事件后，此时retval不为0，从break跳出，结束大循环
		if (retval || !__timeout || signal_pending(current))
			break;
		//检查是否出错，如果出错，也不会进入睡眠状态，直接结束大循环
		if(table.error) {
			retval = table.error;
			break;
		}
		//进入睡眠状态，被唤醒后再进行一次扫描询问
		//除第一次以外，以后都是在进程被唤醒时才执行一遍循环，从本质上讲是一种do-while循环
		__timeout = schedule_timeout(__timeout);
	}
	current->state = TASK_RUNNING; //设置当前进程的状态为运行态
	
	//将所有进程对应的wait_queue_t结构从各个等待队列中删除
	//poll_freewait定义在下面
	poll_freewait(&table);

	/*
	 * Up-to-date the caller timeout.
	 */
	*timeout = __timeout;
	return retval; //返回就绪事件的总数
}

static void *select_bits_alloc(int size)
{
	return kmalloc(6 * size, GFP_KERNEL); //通过kmalloc分配6个位图
}

static void select_bits_free(void *bits, int size)
{
	kfree(bits);
}

/*
 * We can actually return ERESTARTSYS instead of EINTR, but I'd
 * like to be certain this leads to no problems. So I return
 * EINTR just for safety.
 *
 * Update: ERESTARTSYS breaks at least the xview clock binary, so
 * I'm trying ERESTARTNOHAND which restart only when you want to.
 */
#define MAX_SELECT_SECONDS \
	((unsigned long) (MAX_SCHEDULE_TIMEOUT / HZ)-1)

//n表示调用时的参数表中一共有多少个位图，即需要监听的文件描述符最大值，一般为最大值加1
//fd_set类型结构在下面有解释说明
//fd_set表示已打开文件的位图，位图的每一位都代表着当前进程的一个已打开文件，根据其结构定义得知，select最多可以监听1024个文件描述符
//timeval类型结构在下面有解释说明
//tvp表示睡眠等待的最长时间，如果为0则表示立即返回，如果为NULL则表示阻塞等待，直到所监听的事件就绪
asmlinkage long
sys_select(int n, fd_set *inp, fd_set *outp, fd_set *exp, struct timeval *tvp)
{
	//fd_set_bits类型结构在下面有解释说明
	//其中分别保存了3种位图的要求和结果
	fd_set_bits fds;
	char *bits;
	long timeout;
	int ret, size;

	timeout = MAX_SCHEDULE_TIMEOUT;
	if (tvp) {
		time_t sec, usec;
		
		//将所需数据数据从用户空间拷贝到内核空间
		if ((ret = verify_area(VERIFY_READ, tvp, sizeof(*tvp)))
		    || (ret = __get_user(sec, &tvp->tv_sec))
		    || (ret = __get_user(usec, &tvp->tv_usec)))
			goto out_nofds;

		ret = -EINVAL;
		if (sec < 0 || usec < 0)
			goto out_nofds;

		if ((unsigned long) sec < MAX_SELECT_SECONDS) {
			timeout = ROUND_UP(usec, 1000000/HZ);
			timeout += sec * (unsigned long) HZ;
		}
	}

	ret = -EINVAL;
	if (n < 0)
		goto out_nofds;
	
	//判断文件描述符数量有没有超过最大值
	if (n > current->files->max_fdset)
		n = current->files->max_fdset;

	/*
	 * We need 6 bitmaps (in/out/ex for both incoming and outgoing),
	 * since we used fdset we need to allocate memory in units of
	 * long-words. 
	 */
	ret = -ENOMEM;
	size = FDS_BYTES(n);
	
	//select_bits_alloc定义在上面
	//一共分配6个位图
	bits = select_bits_alloc(size);
	//为要求和结果，一共6个位图初始化
	if (!bits)
		goto out_nofds;
	fds.in      = (unsigned long *)  bits;
	fds.out     = (unsigned long *) (bits +   size);
	fds.ex      = (unsigned long *) (bits + 2*size);
	fds.res_in  = (unsigned long *) (bits + 3*size);
	fds.res_out = (unsigned long *) (bits + 4*size);
	fds.res_ex  = (unsigned long *) (bits + 5*size);
	
	//将3个要求位图从用户空间复制到内核空间中的fds的要求位图
	if ((ret = get_fd_set(n, inp, fds.in)) ||
	    (ret = get_fd_set(n, outp, fds.out)) ||
	    (ret = get_fd_set(n, exp, fds.ex)))
		goto out;
	//将内核空间的fds的结果位图初始化为0
	zero_fd_set(n, fds.res_in);
	zero_fd_set(n, fds.res_out);
	zero_fd_set(n, fds.res_ex);
	
	//好戏开始。。。do_select定义在上面。。。→_→
	// ret记录就绪事件的总数
	ret = do_select(n, &fds, &timeout);

	if (tvp && !(current->personality & STICKY_TIMEOUTS)) {
		time_t sec = 0, usec = 0;
		if (timeout) {
			sec = timeout / HZ;
			usec = timeout % HZ;
			usec *= (1000000/HZ);
		}
		put_user(sec, &tvp->tv_sec);
		put_user(usec, &tvp->tv_usec);
	}

	if (ret < 0)
		goto out;
	if (!ret) {
		ret = -ERESTARTNOHAND;
		if (signal_pending(current))
			goto out;
		ret = 0;
	}

	//将3个结果位图的内容复制到用户空间中
	set_fd_set(n, inp, fds.res_in); 
	set_fd_set(n, outp, fds.res_out);
	set_fd_set(n, exp, fds.res_ex);

out:
	select_bits_free(bits, size); //释放要求和结果位图的6个位图的空间
out_nofds:
	return ret; //返回就绪事件的总数
}

// linux-2.4.0\include\linux\\Poll.h
//记录要求的3个位图和结果的3个位图
typedef struct {
	unsigned long *in, *out, *ex; //要求
	unsigned long *res_in, *res_out, *res_ex; //结果
} fd_set_bits;

//linux-2.4.0\include\linux\Time.h
struct timeval {
	time_t		tv_sec;		/* 秒数 seconds */
	suseconds_t	tv_usec;	/* 微秒数 microseconds */
};

//fd_set类型的定义
//linux-2.4.0\include\linux\Posix_types.h
#undef __NFDBITS
//__NFDBITS的值为32
#define __NFDBITS	(8 * sizeof(unsigned long))

#undef __FD_SETSIZE
#define __FD_SETSIZE	1024

#undef __FDSET_LONGS
//__FDSET_LONGS的值为32
#define __FDSET_LONGS	(__FD_SETSIZE/__NFDBITS)

#undef __FDELT
#define	__FDELT(d)	((d) / __NFDBITS)

#undef __FDMASK
#define	__FDMASK(d)	(1UL << ((d) % __NFDBITS))

//因此fd_set实际上是一个具有32个元素的unsigned long类型的数组
typedef struct {
	unsigned long fds_bits [__FDSET_LONGS];
} __kernel_fd_set;

typedef __kernel_fd_set		fd_set;

//linux-2.4.0\include\linux\Poll.h
//poll_table_page类型结构在下面有解释说明
typedef struct poll_table_struct {
	int error;
	struct poll_table_page * table;
} poll_table;

//linux-2.4.0\fs\Select.c
struct poll_table_entry {
	struct file * filp;
	wait_queue_t wait; //被封装的wait_queue_t
	wait_queue_head_t * wait_address; //等待队列的队头
};

struct poll_table_page {
	//一个页面用完了就再分配一个，通过next链成一条单链
	struct poll_table_page * next;
	//poll_table_entry类型结构上面有解释说明
	//entry总是指向entries中第一个空闲的poll_table_entry结构，根据需要动态的分配entries中的表项
	struct poll_table_entry * entry;
	//表示该数组可以动态地确定大小，实际使用中分配一个页面，页面中能容纳几个poll_table_entry，这个数组就有多大
	struct poll_table_entry entries[0]; 
};

//linux-2.4.0\fs\Select.c
void poll_freewait(poll_table* pt)
{
	struct poll_table_page * p = pt->table; //p指向第一个poll_table_page结构，poll_table_page结构由next成员链成单链
	//当p不为NULL时，继续循环
	while (p) {
		struct poll_table_entry * entry;
		struct poll_table_page *old;

		entry = p->entry; //entry指向entries中第一个空闲的poll_table_entry结构，entries是一个数组
		do {
			entry--; //entry前移
			remove_wait_queue(entry->wait_address,&entry->wait); //将entry表示的wait_queue_t结构从等待队列中删除
			fput(entry->filp);
		} while (entry > p->entries); //判断此entries数组中是否还有元素未删除
		old = p; //此时poll_table_page结构中的entries数组中已没有元素，此时old记录当前poll_table_page 结构
		p = p->next; //p指向下一个poll_table_page 结构
		free_page((unsigned long) old); //释放old所指向的poll_table_page结构页面
	}
}

* 哇。。。终于分析完了！！！一会儿直接上poll操作的源码分析和select的应用实例。。。→_→ *