盛世嫡妃凤轻小说,盗墓笔记,君子以泽

epoll和poll的一個很大的區別在于，poll每次調用時都會存在一個將pollfd結構體數組中的每個結構體元素從用戶態向內核態中的一個鏈表節點拷貝的過程，而內核中的這個鏈表并不會一直保存，當poll運行一次就會重新執行一次上述的拷貝過程，這說明一個問題：poll并不會在內核中為要監聽的文件描述符長久的維護一個數據結構來存放他們，而epoll內核中維護了一個內核事件表，它是將所有的文件描述符全部都存放在內核中，系統去檢測有事件發生的時候觸發回調，當你要添加新的文件描述符的時候也是調用epoll_ctl函數使用EPOLL_CTL_ADD宏來插入，epoll_wait也不是每次調用時都會重新拷貝一遍所有的文件描述符到內核態。當我現在要在內核中長久的維護一個數據結構來存放文件描述符，并且時常會有插入，查找和刪除的操作發生，這對內核的效率會產生不小的影響，因此需要一種插入，查找和刪除效率都不錯的數據結構來存放這些文件描述符，那么紅黑樹當然是不二的人選。

接下來我們來看看epoll底層是如何使用紅黑樹的

我們知道epoll在添加一個文件描述符進行監聽或者刪除一個文件描述符時使用的是epoll_ctl函數，該函數底層調用的是sys_epoll_ctl函數，下面給出該函數的部分源碼

/*
 * The following function implements the controller interface for
 * the eventpoll file that enables the insertion/removal/change of
 * file descriptors inside the interest set.  It represents
 * the kernel part of the user space epoll_ctl(2).
 */
asmlinkage long
sys_epoll_ctl(int epfd, int op, int fd, struct epoll_event __user *event)
{
	int error;
	struct file *file, *tfile;
	struct eventpoll *ep;
	struct epitem *epi;
	struct epoll_event epds;

	DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p)n",
		     current, epfd, op, fd, event));

	error = -EFAULT;
	if (EP_OP_HASH_EVENT(op) &&
	    copy_from_user(&epds, event, sizeof(struct epoll_event)))
		goto eexit_1;

	/* Get the "struct file *" for the eventpoll file */
	error = -EBADF;
	file = fget(epfd);
	if (!file)
		goto eexit_1;

	/* Get the "struct file *" for the target file */
	tfile = fget(fd);
	if (!tfile)
		goto eexit_2;

	/* The target file descriptor must support poll */
	error = -EPERM;
	if (!tfile- >f_op || !tfile- >f_op- >poll)
		goto eexit_3;

	/*
	 * We have to check that the file structure underneath the file descriptor
	 * the user passed to us _is_ an eventpoll file. And also we do not permit
	 * adding an epoll file descriptor inside itself.
	 */
	error = -EINVAL;
	if (file == tfile || !IS_FILE_EPOLL(file))
		goto eexit_3;

	/*
	 * At this point it is safe to assume that the "private_data" contains
	 * our own data structure.
	 */
	ep = file- >private_data;

	down_write(&ep- >sem);

	/* Try to lookup the file inside our hash table */
	epi = ep_find(ep, tfile, fd);

在sys_epoll_ctl的參數中，op代表要進行的操作，fd表示要被操作的文件描述符。操作類型定義在下面著三個宏中

/* Valid opcodes to issue to sys_epoll_ctl() */
#define EPOLL_CTL_ADD 1
#define EPOLL_CTL_DEL 2
#define EPOLL_CTL_MOD 3

首先呢，會調用ep_find函數在內核事件表也就是紅黑樹中查找該fd是否已經存在，這里的結果會先保存在epi中，ep_find函數做了什么操作呢？這里就是我們第一個用到紅黑樹的地方：查找

先來看一下ep_find的實現：

/*
 * Search the file inside the eventpoll hash. It add usage count to
 * the returned item, so the caller must call ep_release_epitem()
 * after finished using the "struct epitem".
 */
static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
{
	int kcmp;
	unsigned long flags;
	struct rb_node *rbp;
	struct epitem *epi, *epir = NULL;
	struct epoll_filefd ffd;

	EP_SET_FFD(&ffd, file, fd);
	read_lock_irqsave(&ep- >lock, flags);
	for (rbp = ep- >rbr.rb_node; rbp; ) {
		epi = rb_entry(rbp, struct epitem, rbn);
		kcmp = EP_CMP_FFD(&ffd, &epi- >ffd);
		if (kcmp > 0)
			rbp = rbp- >rb_right;
		else if (kcmp < 0)
			rbp = rbp- >rb_left;
		else {
			ep_use_epitem(epi);
			epir = epi;
			break;
		}
	}
	read_unlock_irqrestore(&ep- >lock, flags);

	DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_find(%p) - > %pn",
		     current, file, epir));

	return epir;
}

這里的for循環就是一個紅黑樹的查找過程，我們可以看到這里查找的時候用到的一個變量是kcmp，這個kcmp的值就是我們的fd在紅黑樹中所用來排序的值。而且我們可以看到這個kcmp的值來源于宏函數EP_CMP_FFD我們來看一下這個宏函數的實現

/* Compare rb-tree keys */
#define EP_CMP_FFD(p1, p2) ((p1)- >file > (p2)- >file ? +1: 
			    ((p1)- >file < (p2)- >file ? -1: (p1)- >fd - (p2)- >fd))

根據該宏函數的實現我們看到在比較時其實使用的是一個epoll_filefd的結構體中的file成員來比較的，那么我們再進入epoll_filefd中查看一下

我們看到這里的file是一個struct file類型的指針，當我們比較兩個file類型的指針時比較的是他們的指針的值，也就是file結構體的地址。

根據源碼判斷，在紅黑樹中排序的根據是file的地址大小。至于為什么，目前還并不是很清楚，也存在我理解錯誤的可能，這里不是很確定。

查找完畢后，就要開始進行具體的操作了，這里會根據宏的值判斷應該進行的操作是插入，刪除，還是修改。這里給出sys_epoll_ctl的剩余源碼（和文章開頭給出的前半部分剛好銜接）

error = -EINVAL;
	switch (op) {
	case EPOLL_CTL_ADD:
		if (!epi) {
			epds.events |= POLLERR | POLLHUP;

			error = ep_insert(ep, &epds, tfile, fd);
		} else
			error = -EEXIST;
		break;
	case EPOLL_CTL_DEL:
		if (epi)
			error = ep_remove(ep, epi);
		else
			error = -ENOENT;
		break;
	case EPOLL_CTL_MOD:
		if (epi) {
			epds.events |= POLLERR | POLLHUP;
			error = ep_modify(ep, epi, &epds);
		} else
			error = -ENOENT;
		break;
	}

	/*
	 * The function ep_find() increments the usage count of the structure
	 * so, if this is not NULL, we need to release it.
	 */
	if (epi)
		ep_release_epitem(epi);

	up_write(&ep- >sem);

eexit_3:
	fput(tfile);
eexit_2:
	fput(file);
eexit_1:
	DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p) = %dn",
		     current, epfd, op, fd, event, error));

	return error;
}

我們看到這部分代碼里最主要的工作就是進行這個switch，case語句所做的判斷工作了，這里sys_epoll_ctl函數根據參數op的不同而調用不同的函數進行處理，我們以EPOLL_CTL_ADD宏舉例，該宏要進行的操作是插入一個新的文件描述符。

epoll底層的紅黑樹插入是調用ep_insert插入的，而ep_insert函數里面調用了ep_rbtree_insert來進行對紅黑樹中一個節點的插入。這兩個函數的聲明如下：

static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi);
static int ep_insert(struct eventpoll *ep, struct epoll_event *event,
		     struct file *tfile, int fd);

我們忽略ep_insert函數其他的實現要點，直接查看它所調用的函數ep_retree_insert的實現

static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi)
{
	int kcmp;
	struct rb_node **p = &ep- >rbr.rb_node, *parent = NULL;
	struct epitem *epic;

	while (*p) {
		parent = *p;
		epic = rb_entry(parent, struct epitem, rbn);
		kcmp = EP_CMP_FFD(&epi- >ffd, &epic- >ffd);
		if (kcmp > 0)
			p = &parent- >rb_right;
		else
			p = &parent- >rb_left;
	}
	rb_link_node(&epi- >rbn, parent, p);
	rb_insert_color(&epi- >rbn, &ep- >rbr);
}

可以看到這里在插入一個新節點時對于其在紅黑樹中的位置的選擇過程是用一個while循環來實現的，當該while循環退出后，說明我們已經找到了該節點應在的位置，接下來調用rb_link_node函數將該節點插入到紅黑樹中，該函數的實現很簡單，就是往一顆二叉樹中插入一個新的節點，實現如下

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
				struct rb_node ** rb_link)
{
	node- >rb_parent = parent;
	node- >rb_color = RB_RED;
	node- >rb_left = node- >rb_right = NULL;

	*rb_link = node;
}

然后再調用rb_insert_color函數，這個函數實現的是對插入一個新節點之后的整個紅黑樹進行調整的過程，這里牽扯到紅黑樹的旋轉，不是我們本文的重點，只把代碼貼上，有興趣的同學可以下去自習。

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *parent, *gparent;

	while ((parent = node- >rb_parent) && parent- >rb_color == RB_RED)
	{
		gparent = parent- >rb_parent;

		if (parent == gparent- >rb_left)
		{
			{
				register struct rb_node *uncle = gparent- >rb_right;
				if (uncle && uncle- >rb_color == RB_RED)
				{
					uncle- >rb_color = RB_BLACK;
					parent- >rb_color = RB_BLACK;
					gparent- >rb_color = RB_RED;
					node = gparent;
					continue;
				}
			}

			if (parent- >rb_right == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_left(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			parent- >rb_color = RB_BLACK;
			gparent- >rb_color = RB_RED;
			__rb_rotate_right(gparent, root);
		} else {
			{
				register struct rb_node *uncle = gparent- >rb_left;
				if (uncle && uncle- >rb_color == RB_RED)
				{
					uncle- >rb_color = RB_BLACK;
					parent- >rb_color = RB_BLACK;
					gparent- >rb_color = RB_RED;
					node = gparent;
					continue;
				}
			}

			if (parent- >rb_left == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_right(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			parent- >rb_color = RB_BLACK;
			gparent- >rb_color = RB_RED;
			__rb_rotate_left(gparent, root);
		}
	}

	root- >rb_node- >rb_color = RB_BLACK;
}