epoll底層如何使用紅黑樹

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

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

我們知道epoll在添加一個(gè)文件描述符進(jìn)行監(jiān)聽或者刪除一個(gè)文件描述符時(shí)使用的是epoll_ctl函數(shù)，該函數(shù)底層調(diào)用的是sys_epoll_ctl函數(shù)，下面給出該函數(shù)的部分源碼

/*
 * 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的參數(shù)中，op代表要進(jìn)行的操作，fd表示要被操作的文件描述符。操作類型定義在下面著三個(gè)宏中

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

首先呢，會調(diào)用ep_find函數(shù)在內(nèi)核事件表也就是紅黑樹中查找該fd是否已經(jīng)存在，這里的結(jié)果會先保存在epi中，ep_find函數(shù)做了什么操作呢？這里就是我們第一個(gè)用到紅黑樹的地方：查找

先來看一下ep_find的實(shí)現(xiàn)：

/*
 * 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循環(huán)就是一個(gè)紅黑樹的查找過程，我們可以看到這里查找的時(shí)候用到的一個(gè)變量是kcmp，這個(gè)kcmp的值就是我們的fd在紅黑樹中所用來排序的值。而且我們可以看到這個(gè)kcmp的值來源于宏函數(shù)EP_CMP_FFD我們來看一下這個(gè)宏函數(shù)的實(shí)現(xiàn)

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

根據(jù)該宏函數(shù)的實(shí)現(xiàn)我們看到在比較時(shí)其實(shí)使用的是一個(gè)epoll_filefd的結(jié)構(gòu)體中的file成員來比較的，那么我們再進(jìn)入epoll_filefd中查看一下

我們看到這里的file是一個(gè)struct file類型的指針，當(dāng)我們比較兩個(gè)file類型的指針時(shí)比較的是他們的指針的值，也就是file結(jié)構(gòu)體的地址。

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

查找完畢后，就要開始進(jìn)行具體的操作了，這里會根據(jù)宏的值判斷應(yīng)該進(jìn)行的操作是插入，刪除，還是修改。這里給出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;
}

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

epoll底層的紅黑樹插入是調(diào)用ep_insert插入的，而ep_insert函數(shù)里面調(diào)用了ep_rbtree_insert來進(jìn)行對紅黑樹中一個(gè)節(jié)點(diǎn)的插入。這兩個(gè)函數(shù)的聲明如下：

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函數(shù)其他的實(shí)現(xiàn)要點(diǎn)，直接查看它所調(diào)用的函數(shù)ep_retree_insert的實(shí)現(xiàn)

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);
}

可以看到這里在插入一個(gè)新節(jié)點(diǎn)時(shí)對于其在紅黑樹中的位置的選擇過程是用一個(gè)while循環(huán)來實(shí)現(xiàn)的，當(dāng)該while循環(huán)退出后，說明我們已經(jīng)找到了該節(jié)點(diǎn)應(yīng)在的位置，接下來調(diào)用rb_link_node函數(shù)將該節(jié)點(diǎn)插入到紅黑樹中，該函數(shù)的實(shí)現(xiàn)很簡單，就是往一顆二叉樹中插入一個(gè)新的節(jié)點(diǎn)，實(shí)現(xiàn)如下

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;
}

然后再調(diào)用rb_insert_color函數(shù)，這個(gè)函數(shù)實(shí)現(xiàn)的是對插入一個(gè)新節(jié)點(diǎn)之后的整個(gè)紅黑樹進(jìn)行調(diào)整的過程，這里牽扯到紅黑樹的旋轉(zhuǎn)，不是我們本文的重點(diǎn)，只把代碼貼上，有興趣的同學(xué)可以下去自習(xí)。

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;
}