套接字中select函数的理解

Dec 14, 2016

套接字中select函数的理解

问题

为什么select函数的时间复杂度是Ｏ(n)?
select函数如何判断文件描述符是ready状态?

select函数

select函数允许进程指示内核等待多个事件中的任何一个发生，并只在有一个或多个事件发生或经历一段指定的时间后才唤醒它。其定义如下：　　　

#include <sys/time.h> /* For portability */
#include <sys/select.h>

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

	Returns number of ready file descriptors, 0 on timeout, or –1 on error

nfds参数指定待测试的描述符个数，它的值是待测试的最大描述符加１，描述符0,1,2,…..一直到nfds-1均被测试。参数readfds、writefds和exceptfds
用于监控读、写和异常的文件描述符集合。最后的参数timeout用于超时时间。　　　

select函数的内核实现　　　

标准库中的select函数是由系统调用sys_select实现。其调用关系如下：

sys_select==>   
	core_sys_select==>   
		do_select

数据结构

#undef __NFDBITS
#define __NFDBITS   (8 * sizeof(unsigned long))

/* __FD_SETSIZE 代表select可以监控的fd最大数目。*/
#undef __FD_SETSIZE
#define __FD_SETSIZE    1024	

#undef __FDSET_LONGS
#define __FDSET_LONGS   (__FD_SETSIZE/__NFDBITS)

typedef struct {
    unsigned long fds_bits [__FDSET_LONGS];
} __kernel_fd_set;

typedef __kernel_fd_set     fd_set;

typedef struct {
    unsigned long *in, *out, *ex;
    unsigned long *res_in, *res_out, *res_ex;
} fd_set_bits;

/*
 * How many longwords for "nr" bits? nr需要的字节
 */
#define FDS_BITPERLONG  (8*sizeof(long))
#define FDS_LONGS(nr)   (((nr)+FDS_BITPERLONG-1)/FDS_BITPERLONG)
#define FDS_BYTES(nr)   (FDS_LONGS(nr)*sizeof(long))

主要代码流程　　　

在函数do_select中，将执行一个for循环。

    		for (j = 0; j < __NFDBITS; ++j, ++i, bit <<= 1) {
            	int fput_needed;
                if (i >= n)
                    break;
                if (!(bit & all_bits))
                    continue;
                /* TODO: 这个file 如何和tcp产生联想的？ */
                /*
                 struct socket_alloc {
                    struct socket socket;
                    struct inode vfs_inode;
                 };
            
                 TODO: file 的f_op 和 inode 的 i_fop 有什么关系。
                 */
                file = fget_light(i, &fput_needed);
                if (file) {
                    f_op = file->f_op;
                    mask = DEFAULT_POLLMASK;
                    /*  
                     这里应该是tcp_poll/udp_poll 
                     udp的接收应该会调用skb_recv_datagram 
                    */
                    if (f_op && f_op->poll)
                        mask = (*f_op->poll)(file, retval ? NULL : wait);
                    fput_light(file, fput_needed);
                    if ((mask & POLLIN_SET) && (in & bit)) {
                        res_in |= bit;
                        retval++;
                    }
                    if ((mask & POLLOUT_SET) && (out & bit)) {
                        res_out |= bit;
                        retval++;
                    }
                    if ((mask & POLLEX_SET) && (ex & bit)) {
                        res_ex |= bit;
                        retval++;
                    }
                }
                /* perform a process switch */
         		cond_resched();
            }
            if (res_in)
                *rinp = res_in;
            if (res_out)
                *routp = res_out;
            if (res_ex)
                *rexp = res_ex;
        }
        wait = NULL;
        /*
         signal_pending
         Returns the value 1 (true) if the process identified by the *p process descriptor has
         nonblocked pending signals, and returns the value 0 (false) if it doesn't. 
         */
        if (retval || !*timeout || signal_pending(current))
            break;