2 * fs/eventpoll.c ( Efficent event polling implementation )
3 * Copyright (C) 2001,...,2003 Davide Libenzi
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * Davide Libenzi <davidel@xmailserver.org>
14 #include <linux/module.h>
15 #include <linux/init.h>
16 #include <linux/kernel.h>
17 #include <linux/sched.h>
19 #include <linux/file.h>
20 #include <linux/signal.h>
21 #include <linux/errno.h>
23 #include <linux/slab.h>
24 #include <linux/poll.h>
25 #include <linux/smp_lock.h>
26 #include <linux/string.h>
27 #include <linux/list.h>
28 #include <linux/hash.h>
29 #include <linux/spinlock.h>
30 #include <linux/syscalls.h>
31 #include <linux/rwsem.h>
32 #include <linux/rbtree.h>
33 #include <linux/wait.h>
34 #include <linux/eventpoll.h>
35 #include <linux/mount.h>
36 #include <asm/bitops.h>
37 #include <asm/uaccess.h>
38 #include <asm/system.h>
41 #include <asm/atomic.h>
42 #include <asm/semaphore.h>
47 * There are three level of locking required by epoll :
49 * 1) epsem (semaphore)
50 * 2) ep->sem (rw_semaphore)
51 * 3) ep->lock (rw_lock)
53 * The acquire order is the one listed above, from 1 to 3.
54 * We need a spinlock (ep->lock) because we manipulate objects
55 * from inside the poll callback, that might be triggered from
56 * a wake_up() that in turn might be called from IRQ context.
57 * So we can't sleep inside the poll callback and hence we need
58 * a spinlock. During the event transfer loop (from kernel to
59 * user space) we could end up sleeping due a copy_to_user(), so
60 * we need a lock that will allow us to sleep. This lock is a
61 * read-write semaphore (ep->sem). It is acquired on read during
62 * the event transfer loop and in write during epoll_ctl(EPOLL_CTL_DEL)
63 * and during eventpoll_release_file(). Then we also need a global
64 * semaphore to serialize eventpoll_release_file() and ep_free().
65 * This semaphore is acquired by ep_free() during the epoll file
66 * cleanup path and it is also acquired by eventpoll_release_file()
67 * if a file has been pushed inside an epoll set and it is then
68 * close()d without a previous call toepoll_ctl(EPOLL_CTL_DEL).
69 * It is possible to drop the "ep->sem" and to use the global
70 * semaphore "epsem" (together with "ep->lock") to have it working,
71 * but having "ep->sem" will make the interface more scalable.
72 * Events that require holding "epsem" are very rare, while for
73 * normal operations the epoll private "ep->sem" will guarantee
74 * a greater scalability.
78 #define EVENTPOLLFS_MAGIC 0x03111965 /* My birthday should work for this :) */
83 #define DPRINTK(x) printk x
84 #define DNPRINTK(n, x) do { if ((n) <= DEBUG_EPOLL) printk x; } while (0)
85 #else /* #if DEBUG_EPOLL > 0 */
86 #define DPRINTK(x) (void) 0
87 #define DNPRINTK(n, x) (void) 0
88 #endif /* #if DEBUG_EPOLL > 0 */
93 #define EPI_SLAB_DEBUG (SLAB_DEBUG_FREE | SLAB_RED_ZONE /* | SLAB_POISON */)
94 #else /* #if DEBUG_EPI != 0 */
95 #define EPI_SLAB_DEBUG 0
96 #endif /* #if DEBUG_EPI != 0 */
98 /* Epoll private bits inside the event mask */
99 #define EP_PRIVATE_BITS (EPOLLONESHOT | EPOLLET)
101 /* Maximum number of poll wake up nests we are allowing */
102 #define EP_MAX_POLLWAKE_NESTS 4
104 /* Macro to allocate a "struct epitem" from the slab cache */
105 #define EPI_MEM_ALLOC() (struct epitem *) kmem_cache_alloc(epi_cache, SLAB_KERNEL)
107 /* Macro to free a "struct epitem" to the slab cache */
108 #define EPI_MEM_FREE(p) kmem_cache_free(epi_cache, p)
110 /* Macro to allocate a "struct eppoll_entry" from the slab cache */
111 #define PWQ_MEM_ALLOC() (struct eppoll_entry *) kmem_cache_alloc(pwq_cache, SLAB_KERNEL)
113 /* Macro to free a "struct eppoll_entry" to the slab cache */
114 #define PWQ_MEM_FREE(p) kmem_cache_free(pwq_cache, p)
116 /* Fast test to see if the file is an evenpoll file */
117 #define IS_FILE_EPOLL(f) ((f)->f_op == &eventpoll_fops)
119 /* Setup the structure that is used as key for the rb-tree */
120 #define EP_SET_FFD(p, f, d) do { (p)->file = (f); (p)->fd = (d); } while (0)
122 /* Compare rb-tree keys */
123 #define EP_CMP_FFD(p1, p2) ((p1)->file > (p2)->file ? +1: \
124 ((p1)->file < (p2)->file ? -1: (p1)->fd - (p2)->fd))
126 /* Special initialization for the rb-tree node to detect linkage */
127 #define EP_RB_INITNODE(n) (n)->rb_parent = (n)
129 /* Removes a node from the rb-tree and marks it for a fast is-linked check */
130 #define EP_RB_ERASE(n, r) do { rb_erase(n, r); (n)->rb_parent = (n); } while (0)
132 /* Fast check to verify that the item is linked to the main rb-tree */
133 #define EP_RB_LINKED(n) ((n)->rb_parent != (n))
136 * Remove the item from the list and perform its initialization.
137 * This is useful for us because we can test if the item is linked
138 * using "EP_IS_LINKED(p)".
140 #define EP_LIST_DEL(p) do { list_del(p); INIT_LIST_HEAD(p); } while (0)
142 /* Tells us if the item is currently linked */
143 #define EP_IS_LINKED(p) (!list_empty(p))
145 /* Get the "struct epitem" from a wait queue pointer */
146 #define EP_ITEM_FROM_WAIT(p) ((struct epitem *) container_of(p, struct eppoll_entry, wait)->base)
148 /* Get the "struct epitem" from an epoll queue wrapper */
149 #define EP_ITEM_FROM_EPQUEUE(p) (container_of(p, struct ep_pqueue, pt)->epi)
151 /* Tells if the epoll_ctl(2) operation needs an event copy from userspace */
152 #define EP_OP_HASH_EVENT(op) ((op) != EPOLL_CTL_DEL)
155 struct epoll_filefd
{
161 * Node that is linked into the "wake_task_list" member of the "struct poll_safewake".
162 * It is used to keep track on all tasks that are currently inside the wake_up() code
163 * to 1) short-circuit the one coming from the same task and same wait queue head
164 * ( loop ) 2) allow a maximum number of epoll descriptors inclusion nesting
165 * 3) let go the ones coming from other tasks.
167 struct wake_task_node
{
168 struct list_head llink
;
170 wait_queue_head_t
*wq
;
174 * This is used to implement the safe poll wake up avoiding to reenter
175 * the poll callback from inside wake_up().
177 struct poll_safewake
{
178 struct list_head wake_task_list
;
183 * This structure is stored inside the "private_data" member of the file
184 * structure and rapresent the main data sructure for the eventpoll
188 /* Protect the this structure access */
192 * This semaphore is used to ensure that files are not removed
193 * while epoll is using them. This is read-held during the event
194 * collection loop and it is write-held during the file cleanup
195 * path, the epoll file exit code and the ctl operations.
197 struct rw_semaphore sem
;
199 /* Wait queue used by sys_epoll_wait() */
200 wait_queue_head_t wq
;
202 /* Wait queue used by file->poll() */
203 wait_queue_head_t poll_wait
;
205 /* List of ready file descriptors */
206 struct list_head rdllist
;
208 /* RB-Tree root used to store monitored fd structs */
212 /* Wait structure used by the poll hooks */
213 struct eppoll_entry
{
214 /* List header used to link this structure to the "struct epitem" */
215 struct list_head llink
;
217 /* The "base" pointer is set to the container "struct epitem" */
221 * Wait queue item that will be linked to the target file wait
226 /* The wait queue head that linked the "wait" wait queue item */
227 wait_queue_head_t
*whead
;
231 * Each file descriptor added to the eventpoll interface will
232 * have an entry of this type linked to the hash.
235 /* RB-Tree node used to link this structure to the eventpoll rb-tree */
238 /* List header used to link this structure to the eventpoll ready list */
239 struct list_head rdllink
;
241 /* The file descriptor information this item refers to */
242 struct epoll_filefd ffd
;
244 /* Number of active wait queue attached to poll operations */
247 /* List containing poll wait queues */
248 struct list_head pwqlist
;
250 /* The "container" of this item */
251 struct eventpoll
*ep
;
253 /* The structure that describe the interested events and the source fd */
254 struct epoll_event event
;
257 * Used to keep track of the usage count of the structure. This avoids
258 * that the structure will desappear from underneath our processing.
262 /* List header used to link this item to the "struct file" items list */
263 struct list_head fllink
;
265 /* List header used to link the item to the transfer list */
266 struct list_head txlink
;
269 * This is used during the collection/transfer of events to userspace
270 * to pin items empty events set.
272 unsigned int revents
;
275 /* Wrapper struct used by poll queueing */
283 static void ep_poll_safewake_init(struct poll_safewake
*psw
);
284 static void ep_poll_safewake(struct poll_safewake
*psw
, wait_queue_head_t
*wq
);
285 static int ep_getfd(int *efd
, struct inode
**einode
, struct file
**efile
);
286 static int ep_file_init(struct file
*file
);
287 static void ep_free(struct eventpoll
*ep
);
288 static struct epitem
*ep_find(struct eventpoll
*ep
, struct file
*file
, int fd
);
289 static void ep_use_epitem(struct epitem
*epi
);
290 static void ep_release_epitem(struct epitem
*epi
);
291 static void ep_ptable_queue_proc(struct file
*file
, wait_queue_head_t
*whead
,
293 static void ep_rbtree_insert(struct eventpoll
*ep
, struct epitem
*epi
);
294 static int ep_insert(struct eventpoll
*ep
, struct epoll_event
*event
,
295 struct file
*tfile
, int fd
);
296 static int ep_modify(struct eventpoll
*ep
, struct epitem
*epi
,
297 struct epoll_event
*event
);
298 static void ep_unregister_pollwait(struct eventpoll
*ep
, struct epitem
*epi
);
299 static int ep_unlink(struct eventpoll
*ep
, struct epitem
*epi
);
300 static int ep_remove(struct eventpoll
*ep
, struct epitem
*epi
);
301 static int ep_poll_callback(wait_queue_t
*wait
, unsigned mode
, int sync
, void *key
);
302 static int ep_eventpoll_close(struct inode
*inode
, struct file
*file
);
303 static unsigned int ep_eventpoll_poll(struct file
*file
, poll_table
*wait
);
304 static int ep_collect_ready_items(struct eventpoll
*ep
,
305 struct list_head
*txlist
, int maxevents
);
306 static int ep_send_events(struct eventpoll
*ep
, struct list_head
*txlist
,
307 struct epoll_event __user
*events
);
308 static void ep_reinject_items(struct eventpoll
*ep
, struct list_head
*txlist
);
309 static int ep_events_transfer(struct eventpoll
*ep
,
310 struct epoll_event __user
*events
,
312 static int ep_poll(struct eventpoll
*ep
, struct epoll_event __user
*events
,
313 int maxevents
, long timeout
);
314 static int eventpollfs_delete_dentry(struct dentry
*dentry
);
315 static struct inode
*ep_eventpoll_inode(void);
316 static struct super_block
*eventpollfs_get_sb(struct file_system_type
*fs_type
,
317 int flags
, const char *dev_name
,
321 * This semaphore is used to serialize ep_free() and eventpoll_release_file().
323 struct semaphore epsem
;
325 /* Safe wake up implementation */
326 static struct poll_safewake psw
;
328 /* Slab cache used to allocate "struct epitem" */
329 static kmem_cache_t
*epi_cache
;
331 /* Slab cache used to allocate "struct eppoll_entry" */
332 static kmem_cache_t
*pwq_cache
;
334 /* Virtual fs used to allocate inodes for eventpoll files */
335 static struct vfsmount
*eventpoll_mnt
;
337 /* File callbacks that implement the eventpoll file behaviour */
338 static struct file_operations eventpoll_fops
= {
339 .release
= ep_eventpoll_close
,
340 .poll
= ep_eventpoll_poll
344 * This is used to register the virtual file system from where
345 * eventpoll inodes are allocated.
347 static struct file_system_type eventpoll_fs_type
= {
348 .name
= "eventpollfs",
349 .get_sb
= eventpollfs_get_sb
,
350 .kill_sb
= kill_anon_super
,
353 /* Very basic directory entry operations for the eventpoll virtual file system */
354 static struct dentry_operations eventpollfs_dentry_operations
= {
355 .d_delete
= eventpollfs_delete_dentry
,
360 /* Initialize the poll safe wake up structure */
361 static void ep_poll_safewake_init(struct poll_safewake
*psw
)
364 INIT_LIST_HEAD(&psw
->wake_task_list
);
365 spin_lock_init(&psw
->lock
);
370 * Perform a safe wake up of the poll wait list. The problem is that
371 * with the new callback'd wake up system, it is possible that the
372 * poll callback is reentered from inside the call to wake_up() done
373 * on the poll wait queue head. The rule is that we cannot reenter the
374 * wake up code from the same task more than EP_MAX_POLLWAKE_NESTS times,
375 * and we cannot reenter the same wait queue head at all. This will
376 * enable to have a hierarchy of epoll file descriptor of no more than
377 * EP_MAX_POLLWAKE_NESTS deep. We need the irq version of the spin lock
378 * because this one gets called by the poll callback, that in turn is called
379 * from inside a wake_up(), that might be called from irq context.
381 static void ep_poll_safewake(struct poll_safewake
*psw
, wait_queue_head_t
*wq
)
385 task_t
*this_task
= current
;
386 struct list_head
*lsthead
= &psw
->wake_task_list
, *lnk
;
387 struct wake_task_node
*tncur
;
388 struct wake_task_node tnode
;
390 spin_lock_irqsave(&psw
->lock
, flags
);
392 /* Try to see if the current task is already inside this wakeup call */
393 list_for_each(lnk
, lsthead
) {
394 tncur
= list_entry(lnk
, struct wake_task_node
, llink
);
396 if (tncur
->wq
== wq
||
397 (tncur
->task
== this_task
&& ++wake_nests
> EP_MAX_POLLWAKE_NESTS
)) {
399 * Ops ... loop detected or maximum nest level reached.
400 * We abort this wake by breaking the cycle itself.
402 spin_unlock_irqrestore(&psw
->lock
, flags
);
407 /* Add the current task to the list */
408 tnode
.task
= this_task
;
410 list_add(&tnode
.llink
, lsthead
);
412 spin_unlock_irqrestore(&psw
->lock
, flags
);
414 /* Do really wake up now */
417 /* Remove the current task from the list */
418 spin_lock_irqsave(&psw
->lock
, flags
);
419 list_del(&tnode
.llink
);
420 spin_unlock_irqrestore(&psw
->lock
, flags
);
424 /* Used to initialize the epoll bits inside the "struct file" */
425 void eventpoll_init_file(struct file
*file
)
428 INIT_LIST_HEAD(&file
->f_ep_links
);
429 spin_lock_init(&file
->f_ep_lock
);
434 * This is called from eventpoll_release() to unlink files from the eventpoll
435 * interface. We need to have this facility to cleanup correctly files that are
436 * closed without being removed from the eventpoll interface.
438 void eventpoll_release_file(struct file
*file
)
440 struct list_head
*lsthead
= &file
->f_ep_links
;
441 struct eventpoll
*ep
;
445 * We don't want to get "file->f_ep_lock" because it is not
446 * necessary. It is not necessary because we're in the "struct file"
447 * cleanup path, and this means that noone is using this file anymore.
448 * The only hit might come from ep_free() but by holding the semaphore
449 * will correctly serialize the operation. We do need to acquire
450 * "ep->sem" after "epsem" because ep_remove() requires it when called
451 * from anywhere but ep_free().
455 while (!list_empty(lsthead
)) {
456 epi
= list_entry(lsthead
->next
, struct epitem
, fllink
);
459 EP_LIST_DEL(&epi
->fllink
);
460 down_write(&ep
->sem
);
470 * It opens an eventpoll file descriptor by suggesting a storage of "size"
471 * file descriptors. The size parameter is just an hint about how to size
472 * data structures. It won't prevent the user to store more than "size"
473 * file descriptors inside the epoll interface. It is the kernel part of
474 * the userspace epoll_create(2).
476 asmlinkage
long sys_epoll_create(int size
)
482 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_create(%d)\n",
485 /* Sanity check on the size parameter */
491 * Creates all the items needed to setup an eventpoll file. That is,
492 * a file structure, and inode and a free file descriptor.
494 error
= ep_getfd(&fd
, &inode
, &file
);
498 /* Setup the file internal data structure ( "struct eventpoll" ) */
499 error
= ep_file_init(file
);
504 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_create(%d) = %d\n",
512 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_create(%d) = %d\n",
513 current
, size
, error
));
519 * The following function implements the controller interface for
520 * the eventpoll file that enables the insertion/removal/change of
521 * file descriptors inside the interest set. It represents
522 * the kernel part of the user space epoll_ctl(2).
525 sys_epoll_ctl(int epfd
, int op
, int fd
, struct epoll_event __user
*event
)
528 struct file
*file
, *tfile
;
529 struct eventpoll
*ep
;
531 struct epoll_event epds
;
533 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p)\n",
534 current
, epfd
, op
, fd
, event
));
537 if (EP_OP_HASH_EVENT(op
) &&
538 copy_from_user(&epds
, event
, sizeof(struct epoll_event
)))
541 /* Get the "struct file *" for the eventpoll file */
547 /* Get the "struct file *" for the target file */
552 /* The target file descriptor must support poll */
554 if (!tfile
->f_op
|| !tfile
->f_op
->poll
)
558 * We have to check that the file structure underneath the file descriptor
559 * the user passed to us _is_ an eventpoll file. And also we do not permit
560 * adding an epoll file descriptor inside itself.
563 if (file
== tfile
|| !IS_FILE_EPOLL(file
))
567 * At this point it is safe to assume that the "private_data" contains
568 * our own data structure.
570 ep
= file
->private_data
;
572 down_write(&ep
->sem
);
574 /* Try to lookup the file inside our hash table */
575 epi
= ep_find(ep
, tfile
, fd
);
581 epds
.events
|= POLLERR
| POLLHUP
;
583 error
= ep_insert(ep
, &epds
, tfile
, fd
);
589 error
= ep_remove(ep
, epi
);
595 epds
.events
|= POLLERR
| POLLHUP
;
596 error
= ep_modify(ep
, epi
, &epds
);
603 * The function ep_find() increments the usage count of the structure
604 * so, if this is not NULL, we need to release it.
607 ep_release_epitem(epi
);
616 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p) = %d\n",
617 current
, epfd
, op
, fd
, event
, error
));
624 * Implement the event wait interface for the eventpoll file. It is the kernel
625 * part of the user space epoll_wait(2).
627 asmlinkage
long sys_epoll_wait(int epfd
, struct epoll_event __user
*events
,
628 int maxevents
, int timeout
)
632 struct eventpoll
*ep
;
634 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d)\n",
635 current
, epfd
, events
, maxevents
, timeout
));
637 /* The maximum number of event must be greater than zero */
641 /* Verify that the area passed by the user is writeable */
642 if ((error
= verify_area(VERIFY_WRITE
, events
, maxevents
* sizeof(struct epoll_event
))))
645 /* Get the "struct file *" for the eventpoll file */
652 * We have to check that the file structure underneath the fd
653 * the user passed to us _is_ an eventpoll file.
656 if (!IS_FILE_EPOLL(file
))
660 * At this point it is safe to assume that the "private_data" contains
661 * our own data structure.
663 ep
= file
->private_data
;
665 /* Time to fish for events ... */
666 error
= ep_poll(ep
, events
, maxevents
, timeout
);
671 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d) = %d\n",
672 current
, epfd
, events
, maxevents
, timeout
, error
));
679 * Creates the file descriptor to be used by the epoll interface.
681 static int ep_getfd(int *efd
, struct inode
**einode
, struct file
**efile
)
685 struct dentry
*dentry
;
690 /* Get an ready to use file */
692 file
= get_empty_filp();
696 /* Allocates an inode from the eventpoll file system */
697 inode
= ep_eventpoll_inode();
698 error
= PTR_ERR(inode
);
702 /* Allocates a free descriptor to plug the file onto */
703 error
= get_unused_fd();
709 * Link the inode to a directory entry by creating a unique name
710 * using the inode number.
713 sprintf(name
, "[%lu]", inode
->i_ino
);
715 this.len
= strlen(name
);
716 this.hash
= inode
->i_ino
;
717 dentry
= d_alloc(eventpoll_mnt
->mnt_sb
->s_root
, &this);
720 dentry
->d_op
= &eventpollfs_dentry_operations
;
721 d_add(dentry
, inode
);
722 file
->f_vfsmnt
= mntget(eventpoll_mnt
);
723 file
->f_dentry
= dentry
;
724 file
->f_mapping
= inode
->i_mapping
;
727 file
->f_flags
= O_RDONLY
;
728 file
->f_op
= &eventpoll_fops
;
729 file
->f_mode
= FMODE_READ
;
731 file
->private_data
= NULL
;
733 /* Install the new setup file into the allocated fd. */
734 fd_install(fd
, file
);
752 static int ep_file_init(struct file
*file
)
754 struct eventpoll
*ep
;
756 if (!(ep
= kmalloc(sizeof(struct eventpoll
), GFP_KERNEL
)))
759 memset(ep
, 0, sizeof(*ep
));
760 rwlock_init(&ep
->lock
);
761 init_rwsem(&ep
->sem
);
762 init_waitqueue_head(&ep
->wq
);
763 init_waitqueue_head(&ep
->poll_wait
);
764 INIT_LIST_HEAD(&ep
->rdllist
);
767 file
->private_data
= ep
;
769 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: ep_file_init() ep=%p\n",
775 static void ep_free(struct eventpoll
*ep
)
780 /* We need to release all tasks waiting for these file */
781 if (waitqueue_active(&ep
->poll_wait
))
782 ep_poll_safewake(&psw
, &ep
->poll_wait
);
785 * We need to lock this because we could be hit by
786 * eventpoll_release_file() while we're freeing the "struct eventpoll".
787 * We do not need to hold "ep->sem" here because the epoll file
788 * is on the way to be removed and no one has references to it
789 * anymore. The only hit might come from eventpoll_release_file() but
790 * holding "epsem" is sufficent here.
795 * Walks through the whole tree by unregistering poll callbacks.
797 for (rbp
= rb_first(&ep
->rbr
); rbp
; rbp
= rb_next(rbp
)) {
798 epi
= rb_entry(rbp
, struct epitem
, rbn
);
800 ep_unregister_pollwait(ep
, epi
);
804 * Walks through the whole hash by freeing each "struct epitem". At this
805 * point we are sure no poll callbacks will be lingering around, and also by
806 * write-holding "sem" we can be sure that no file cleanup code will hit
807 * us during this operation. So we can avoid the lock on "ep->lock".
809 while ((rbp
= rb_first(&ep
->rbr
)) != 0) {
810 epi
= rb_entry(rbp
, struct epitem
, rbn
);
819 * Search the file inside the eventpoll hash. It add usage count to
820 * the returned item, so the caller must call ep_release_epitem()
821 * after finished using the "struct epitem".
823 static struct epitem
*ep_find(struct eventpoll
*ep
, struct file
*file
, int fd
)
828 struct epitem
*epi
, *epir
= NULL
;
829 struct epoll_filefd ffd
;
831 EP_SET_FFD(&ffd
, file
, fd
);
832 read_lock_irqsave(&ep
->lock
, flags
);
833 for (rbp
= ep
->rbr
.rb_node
; rbp
; ) {
834 epi
= rb_entry(rbp
, struct epitem
, rbn
);
835 kcmp
= EP_CMP_FFD(&ffd
, &epi
->ffd
);
846 read_unlock_irqrestore(&ep
->lock
, flags
);
848 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: ep_find(%p) -> %p\n",
849 current
, file
, epir
));
856 * Increment the usage count of the "struct epitem" making it sure
857 * that the user will have a valid pointer to reference.
859 static void ep_use_epitem(struct epitem
*epi
)
862 atomic_inc(&epi
->usecnt
);
867 * Decrement ( release ) the usage count by signaling that the user
868 * has finished using the structure. It might lead to freeing the
869 * structure itself if the count goes to zero.
871 static void ep_release_epitem(struct epitem
*epi
)
874 if (atomic_dec_and_test(&epi
->usecnt
))
880 * This is the callback that is used to add our wait queue to the
881 * target file wakeup lists.
883 static void ep_ptable_queue_proc(struct file
*file
, wait_queue_head_t
*whead
,
886 struct epitem
*epi
= EP_ITEM_FROM_EPQUEUE(pt
);
887 struct eppoll_entry
*pwq
;
889 if (epi
->nwait
>= 0 && (pwq
= PWQ_MEM_ALLOC())) {
890 init_waitqueue_func_entry(&pwq
->wait
, ep_poll_callback
);
893 add_wait_queue(whead
, &pwq
->wait
);
894 list_add_tail(&pwq
->llink
, &epi
->pwqlist
);
897 /* We have to signal that an error occurred */
903 static void ep_rbtree_insert(struct eventpoll
*ep
, struct epitem
*epi
)
906 struct rb_node
**p
= &ep
->rbr
.rb_node
, *parent
= NULL
;
911 epic
= rb_entry(parent
, struct epitem
, rbn
);
912 kcmp
= EP_CMP_FFD(&epi
->ffd
, &epic
->ffd
);
914 p
= &parent
->rb_right
;
916 p
= &parent
->rb_left
;
918 rb_link_node(&epi
->rbn
, parent
, p
);
919 rb_insert_color(&epi
->rbn
, &ep
->rbr
);
923 static int ep_insert(struct eventpoll
*ep
, struct epoll_event
*event
,
924 struct file
*tfile
, int fd
)
926 int error
, revents
, pwake
= 0;
929 struct ep_pqueue epq
;
932 if (!(epi
= EPI_MEM_ALLOC()))
935 /* Item initialization follow here ... */
936 EP_RB_INITNODE(&epi
->rbn
);
937 INIT_LIST_HEAD(&epi
->rdllink
);
938 INIT_LIST_HEAD(&epi
->fllink
);
939 INIT_LIST_HEAD(&epi
->txlink
);
940 INIT_LIST_HEAD(&epi
->pwqlist
);
942 EP_SET_FFD(&epi
->ffd
, tfile
, fd
);
944 atomic_set(&epi
->usecnt
, 1);
947 /* Initialize the poll table using the queue callback */
949 init_poll_funcptr(&epq
.pt
, ep_ptable_queue_proc
);
952 * Attach the item to the poll hooks and get current event bits.
953 * We can safely use the file* here because its usage count has
954 * been increased by the caller of this function.
956 revents
= tfile
->f_op
->poll(tfile
, &epq
.pt
);
959 * We have to check if something went wrong during the poll wait queue
960 * install process. Namely an allocation for a wait queue failed due
961 * high memory pressure.
966 /* Add the current item to the list of active epoll hook for this file */
967 spin_lock(&tfile
->f_ep_lock
);
968 list_add_tail(&epi
->fllink
, &tfile
->f_ep_links
);
969 spin_unlock(&tfile
->f_ep_lock
);
971 /* We have to drop the new item inside our item list to keep track of it */
972 write_lock_irqsave(&ep
->lock
, flags
);
974 /* Add the current item to the rb-tree */
975 ep_rbtree_insert(ep
, epi
);
977 /* If the file is already "ready" we drop it inside the ready list */
978 if ((revents
& event
->events
) && !EP_IS_LINKED(&epi
->rdllink
)) {
979 list_add_tail(&epi
->rdllink
, &ep
->rdllist
);
981 /* Notify waiting tasks that events are available */
982 if (waitqueue_active(&ep
->wq
))
984 if (waitqueue_active(&ep
->poll_wait
))
988 write_unlock_irqrestore(&ep
->lock
, flags
);
990 /* We have to call this outside the lock */
992 ep_poll_safewake(&psw
, &ep
->poll_wait
);
994 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: ep_insert(%p, %p, %d)\n",
995 current
, ep
, tfile
, fd
));
1000 ep_unregister_pollwait(ep
, epi
);
1003 * We need to do this because an event could have been arrived on some
1004 * allocated wait queue.
1006 write_lock_irqsave(&ep
->lock
, flags
);
1007 if (EP_IS_LINKED(&epi
->rdllink
))
1008 EP_LIST_DEL(&epi
->rdllink
);
1009 write_unlock_irqrestore(&ep
->lock
, flags
);
1018 * Modify the interest event mask by dropping an event if the new mask
1019 * has a match in the current file status.
1021 static int ep_modify(struct eventpoll
*ep
, struct epitem
*epi
, struct epoll_event
*event
)
1024 unsigned int revents
;
1025 unsigned long flags
;
1028 * Set the new event interest mask before calling f_op->poll(), otherwise
1029 * a potential race might occur. In fact if we do this operation inside
1030 * the lock, an event might happen between the f_op->poll() call and the
1031 * new event set registering.
1033 epi
->event
.events
= event
->events
;
1036 * Get current event bits. We can safely use the file* here because
1037 * its usage count has been increased by the caller of this function.
1039 revents
= epi
->ffd
.file
->f_op
->poll(epi
->ffd
.file
, NULL
);
1041 write_lock_irqsave(&ep
->lock
, flags
);
1043 /* Copy the data member from inside the lock */
1044 epi
->event
.data
= event
->data
;
1047 * If the item is not linked to the hash it means that it's on its
1048 * way toward the removal. Do nothing in this case.
1050 if (EP_RB_LINKED(&epi
->rbn
)) {
1052 * If the item is "hot" and it is not registered inside the ready
1053 * list, push it inside. If the item is not "hot" and it is currently
1054 * registered inside the ready list, unlink it.
1056 if (revents
& event
->events
) {
1057 if (!EP_IS_LINKED(&epi
->rdllink
)) {
1058 list_add_tail(&epi
->rdllink
, &ep
->rdllist
);
1060 /* Notify waiting tasks that events are available */
1061 if (waitqueue_active(&ep
->wq
))
1063 if (waitqueue_active(&ep
->poll_wait
))
1069 write_unlock_irqrestore(&ep
->lock
, flags
);
1071 /* We have to call this outside the lock */
1073 ep_poll_safewake(&psw
, &ep
->poll_wait
);
1080 * This function unregister poll callbacks from the associated file descriptor.
1081 * Since this must be called without holding "ep->lock" the atomic exchange trick
1082 * will protect us from multiple unregister.
1084 static void ep_unregister_pollwait(struct eventpoll
*ep
, struct epitem
*epi
)
1087 struct list_head
*lsthead
= &epi
->pwqlist
;
1088 struct eppoll_entry
*pwq
;
1090 /* This is called without locks, so we need the atomic exchange */
1091 nwait
= xchg(&epi
->nwait
, 0);
1094 while (!list_empty(lsthead
)) {
1095 pwq
= list_entry(lsthead
->next
, struct eppoll_entry
, llink
);
1097 EP_LIST_DEL(&pwq
->llink
);
1098 remove_wait_queue(pwq
->whead
, &pwq
->wait
);
1106 * Unlink the "struct epitem" from all places it might have been hooked up.
1107 * This function must be called with write IRQ lock on "ep->lock".
1109 static int ep_unlink(struct eventpoll
*ep
, struct epitem
*epi
)
1114 * It can happen that this one is called for an item already unlinked.
1115 * The check protect us from doing a double unlink ( crash ).
1118 if (!EP_RB_LINKED(&epi
->rbn
))
1122 * Clear the event mask for the unlinked item. This will avoid item
1123 * notifications to be sent after the unlink operation from inside
1124 * the kernel->userspace event transfer loop.
1126 epi
->event
.events
= 0;
1129 * At this point is safe to do the job, unlink the item from our rb-tree.
1130 * This operation togheter with the above check closes the door to
1133 EP_RB_ERASE(&epi
->rbn
, &ep
->rbr
);
1136 * If the item we are going to remove is inside the ready file descriptors
1137 * we want to remove it from this list to avoid stale events.
1139 if (EP_IS_LINKED(&epi
->rdllink
))
1140 EP_LIST_DEL(&epi
->rdllink
);
1145 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: ep_unlink(%p, %p) = %d\n",
1146 current
, ep
, epi
->file
, error
));
1153 * Removes a "struct epitem" from the eventpoll hash and deallocates
1154 * all the associated resources.
1156 static int ep_remove(struct eventpoll
*ep
, struct epitem
*epi
)
1159 unsigned long flags
;
1160 struct file
*file
= epi
->ffd
.file
;
1163 * Removes poll wait queue hooks. We _have_ to do this without holding
1164 * the "ep->lock" otherwise a deadlock might occur. This because of the
1165 * sequence of the lock acquisition. Here we do "ep->lock" then the wait
1166 * queue head lock when unregistering the wait queue. The wakeup callback
1167 * will run by holding the wait queue head lock and will call our callback
1168 * that will try to get "ep->lock".
1170 ep_unregister_pollwait(ep
, epi
);
1172 /* Remove the current item from the list of epoll hooks */
1173 spin_lock(&file
->f_ep_lock
);
1174 if (EP_IS_LINKED(&epi
->fllink
))
1175 EP_LIST_DEL(&epi
->fllink
);
1176 spin_unlock(&file
->f_ep_lock
);
1178 /* We need to acquire the write IRQ lock before calling ep_unlink() */
1179 write_lock_irqsave(&ep
->lock
, flags
);
1181 /* Really unlink the item from the hash */
1182 error
= ep_unlink(ep
, epi
);
1184 write_unlock_irqrestore(&ep
->lock
, flags
);
1189 /* At this point it is safe to free the eventpoll item */
1190 ep_release_epitem(epi
);
1194 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: ep_remove(%p, %p) = %d\n",
1195 current
, ep
, file
, error
));
1202 * This is the callback that is passed to the wait queue wakeup
1203 * machanism. It is called by the stored file descriptors when they
1204 * have events to report.
1206 static int ep_poll_callback(wait_queue_t
*wait
, unsigned mode
, int sync
, void *key
)
1209 unsigned long flags
;
1210 struct epitem
*epi
= EP_ITEM_FROM_WAIT(wait
);
1211 struct eventpoll
*ep
= epi
->ep
;
1213 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: poll_callback(%p) epi=%p ep=%p\n",
1214 current
, epi
->file
, epi
, ep
));
1216 write_lock_irqsave(&ep
->lock
, flags
);
1219 * If the event mask does not contain any poll(2) event, we consider the
1220 * descriptor to be disabled. This condition is likely the effect of the
1221 * EPOLLONESHOT bit that disables the descriptor when an event is received,
1222 * until the next EPOLL_CTL_MOD will be issued.
1224 if (!(epi
->event
.events
& ~EP_PRIVATE_BITS
))
1227 /* If this file is already in the ready list we exit soon */
1228 if (EP_IS_LINKED(&epi
->rdllink
))
1231 list_add_tail(&epi
->rdllink
, &ep
->rdllist
);
1235 * Wake up ( if active ) both the eventpoll wait list and the ->poll()
1238 if (waitqueue_active(&ep
->wq
))
1240 if (waitqueue_active(&ep
->poll_wait
))
1244 write_unlock_irqrestore(&ep
->lock
, flags
);
1246 /* We have to call this outside the lock */
1248 ep_poll_safewake(&psw
, &ep
->poll_wait
);
1254 static int ep_eventpoll_close(struct inode
*inode
, struct file
*file
)
1256 struct eventpoll
*ep
= file
->private_data
;
1263 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: close() ep=%p\n", current
, ep
));
1268 static unsigned int ep_eventpoll_poll(struct file
*file
, poll_table
*wait
)
1270 unsigned int pollflags
= 0;
1271 unsigned long flags
;
1272 struct eventpoll
*ep
= file
->private_data
;
1274 /* Insert inside our poll wait queue */
1275 poll_wait(file
, &ep
->poll_wait
, wait
);
1277 /* Check our condition */
1278 read_lock_irqsave(&ep
->lock
, flags
);
1279 if (!list_empty(&ep
->rdllist
))
1280 pollflags
= POLLIN
| POLLRDNORM
;
1281 read_unlock_irqrestore(&ep
->lock
, flags
);
1288 * Since we have to release the lock during the __copy_to_user() operation and
1289 * during the f_op->poll() call, we try to collect the maximum number of items
1290 * by reducing the irqlock/irqunlock switching rate.
1292 static int ep_collect_ready_items(struct eventpoll
*ep
, struct list_head
*txlist
, int maxevents
)
1295 unsigned long flags
;
1296 struct list_head
*lsthead
= &ep
->rdllist
, *lnk
;
1299 write_lock_irqsave(&ep
->lock
, flags
);
1301 for (nepi
= 0, lnk
= lsthead
->next
; lnk
!= lsthead
&& nepi
< maxevents
;) {
1302 epi
= list_entry(lnk
, struct epitem
, rdllink
);
1306 /* If this file is already in the ready list we exit soon */
1307 if (!EP_IS_LINKED(&epi
->txlink
)) {
1309 * This is initialized in this way so that the default
1310 * behaviour of the reinjecting code will be to push back
1311 * the item inside the ready list.
1313 epi
->revents
= epi
->event
.events
;
1315 /* Link the ready item into the transfer list */
1316 list_add(&epi
->txlink
, txlist
);
1320 * Unlink the item from the ready list.
1322 EP_LIST_DEL(&epi
->rdllink
);
1326 write_unlock_irqrestore(&ep
->lock
, flags
);
1333 * This function is called without holding the "ep->lock" since the call to
1334 * __copy_to_user() might sleep, and also f_op->poll() might reenable the IRQ
1335 * because of the way poll() is traditionally implemented in Linux.
1337 static int ep_send_events(struct eventpoll
*ep
, struct list_head
*txlist
,
1338 struct epoll_event __user
*events
)
1341 unsigned int revents
;
1342 struct list_head
*lnk
;
1346 * We can loop without lock because this is a task private list.
1347 * The test done during the collection loop will guarantee us that
1348 * another task will not try to collect this file. Also, items
1349 * cannot vanish during the loop because we are holding "sem".
1351 list_for_each(lnk
, txlist
) {
1352 epi
= list_entry(lnk
, struct epitem
, txlink
);
1355 * Get the ready file event set. We can safely use the file
1356 * because we are holding the "sem" in read and this will
1357 * guarantee that both the file and the item will not vanish.
1359 revents
= epi
->ffd
.file
->f_op
->poll(epi
->ffd
.file
, NULL
);
1362 * Set the return event set for the current file descriptor.
1363 * Note that only the task task was successfully able to link
1364 * the item to its "txlist" will write this field.
1366 epi
->revents
= revents
& epi
->event
.events
;
1369 if (__put_user(epi
->revents
,
1370 &events
[eventcnt
].events
) ||
1371 __put_user(epi
->event
.data
,
1372 &events
[eventcnt
].data
))
1374 if (epi
->event
.events
& EPOLLONESHOT
)
1375 epi
->event
.events
&= EP_PRIVATE_BITS
;
1384 * Walk through the transfer list we collected with ep_collect_ready_items()
1385 * and, if 1) the item is still "alive" 2) its event set is not empty 3) it's
1386 * not already linked, links it to the ready list. Same as above, we are holding
1387 * "sem" so items cannot vanish underneath our nose.
1389 static void ep_reinject_items(struct eventpoll
*ep
, struct list_head
*txlist
)
1391 int ricnt
= 0, pwake
= 0;
1392 unsigned long flags
;
1395 write_lock_irqsave(&ep
->lock
, flags
);
1397 while (!list_empty(txlist
)) {
1398 epi
= list_entry(txlist
->next
, struct epitem
, txlink
);
1400 /* Unlink the current item from the transfer list */
1401 EP_LIST_DEL(&epi
->txlink
);
1404 * If the item is no more linked to the interest set, we don't
1405 * have to push it inside the ready list because the following
1406 * ep_release_epitem() is going to drop it. Also, if the current
1407 * item is set to have an Edge Triggered behaviour, we don't have
1408 * to push it back either.
1410 if (EP_RB_LINKED(&epi
->rbn
) && !(epi
->event
.events
& EPOLLET
) &&
1411 (epi
->revents
& epi
->event
.events
) && !EP_IS_LINKED(&epi
->rdllink
)) {
1412 list_add_tail(&epi
->rdllink
, &ep
->rdllist
);
1419 * Wake up ( if active ) both the eventpoll wait list and the ->poll()
1422 if (waitqueue_active(&ep
->wq
))
1424 if (waitqueue_active(&ep
->poll_wait
))
1428 write_unlock_irqrestore(&ep
->lock
, flags
);
1430 /* We have to call this outside the lock */
1432 ep_poll_safewake(&psw
, &ep
->poll_wait
);
1437 * Perform the transfer of events to user space.
1439 static int ep_events_transfer(struct eventpoll
*ep
,
1440 struct epoll_event __user
*events
, int maxevents
)
1443 struct list_head txlist
;
1445 INIT_LIST_HEAD(&txlist
);
1448 * We need to lock this because we could be hit by
1449 * eventpoll_release_file() and epoll_ctl(EPOLL_CTL_DEL).
1451 down_read(&ep
->sem
);
1453 /* Collect/extract ready items */
1454 if (ep_collect_ready_items(ep
, &txlist
, maxevents
) > 0) {
1455 /* Build result set in userspace */
1456 eventcnt
= ep_send_events(ep
, &txlist
, events
);
1458 /* Reinject ready items into the ready list */
1459 ep_reinject_items(ep
, &txlist
);
1468 static int ep_poll(struct eventpoll
*ep
, struct epoll_event __user
*events
,
1469 int maxevents
, long timeout
)
1472 unsigned long flags
;
1477 * Calculate the timeout by checking for the "infinite" value ( -1 )
1478 * and the overflow condition. The passed timeout is in milliseconds,
1479 * that why (t * HZ) / 1000.
1481 jtimeout
= timeout
== -1 || timeout
> (MAX_SCHEDULE_TIMEOUT
- 1000) / HZ
?
1482 MAX_SCHEDULE_TIMEOUT
: (timeout
* HZ
+ 999) / 1000;
1485 write_lock_irqsave(&ep
->lock
, flags
);
1488 if (list_empty(&ep
->rdllist
)) {
1490 * We don't have any available event to return to the caller.
1491 * We need to sleep here, and we will be wake up by
1492 * ep_poll_callback() when events will become available.
1494 init_waitqueue_entry(&wait
, current
);
1495 add_wait_queue(&ep
->wq
, &wait
);
1499 * We don't want to sleep if the ep_poll_callback() sends us
1500 * a wakeup in between. That's why we set the task state
1501 * to TASK_INTERRUPTIBLE before doing the checks.
1503 set_current_state(TASK_INTERRUPTIBLE
);
1504 if (!list_empty(&ep
->rdllist
) || !jtimeout
)
1506 if (signal_pending(current
)) {
1511 write_unlock_irqrestore(&ep
->lock
, flags
);
1512 jtimeout
= schedule_timeout(jtimeout
);
1513 write_lock_irqsave(&ep
->lock
, flags
);
1515 remove_wait_queue(&ep
->wq
, &wait
);
1517 set_current_state(TASK_RUNNING
);
1520 /* Is it worth to try to dig for events ? */
1521 eavail
= !list_empty(&ep
->rdllist
);
1523 write_unlock_irqrestore(&ep
->lock
, flags
);
1526 * Try to transfer events to user space. In case we get 0 events and
1527 * there's still timeout left over, we go trying again in search of
1530 if (!res
&& eavail
&&
1531 !(res
= ep_events_transfer(ep
, events
, maxevents
)) && jtimeout
)
1538 static int eventpollfs_delete_dentry(struct dentry
*dentry
)
1545 static struct inode
*ep_eventpoll_inode(void)
1547 int error
= -ENOMEM
;
1548 struct inode
*inode
= new_inode(eventpoll_mnt
->mnt_sb
);
1553 inode
->i_fop
= &eventpoll_fops
;
1556 * Mark the inode dirty from the very beginning,
1557 * that way it will never be moved to the dirty
1558 * list because mark_inode_dirty() will think
1559 * that it already _is_ on the dirty list.
1561 inode
->i_state
= I_DIRTY
;
1562 inode
->i_mode
= S_IRUSR
| S_IWUSR
;
1563 inode
->i_uid
= current
->fsuid
;
1564 inode
->i_gid
= current
->fsgid
;
1565 inode
->i_atime
= inode
->i_mtime
= inode
->i_ctime
= CURRENT_TIME
;
1566 inode
->i_blksize
= PAGE_SIZE
;
1570 return ERR_PTR(error
);
1574 static struct super_block
*
1575 eventpollfs_get_sb(struct file_system_type
*fs_type
, int flags
,
1576 const char *dev_name
, void *data
)
1578 return get_sb_pseudo(fs_type
, "eventpoll:", NULL
, EVENTPOLLFS_MAGIC
);
1582 static int __init
eventpoll_init(void)
1588 /* Initialize the structure used to perform safe poll wait head wake ups */
1589 ep_poll_safewake_init(&psw
);
1591 /* Allocates slab cache used to allocate "struct epitem" items */
1592 epi_cache
= kmem_cache_create("eventpoll_epi", sizeof(struct epitem
),
1593 0, SLAB_HWCACHE_ALIGN
|EPI_SLAB_DEBUG
|SLAB_PANIC
,
1596 /* Allocates slab cache used to allocate "struct eppoll_entry" */
1597 pwq_cache
= kmem_cache_create("eventpoll_pwq",
1598 sizeof(struct eppoll_entry
), 0,
1599 EPI_SLAB_DEBUG
|SLAB_PANIC
, NULL
, NULL
);
1602 * Register the virtual file system that will be the source of inodes
1603 * for the eventpoll files
1605 error
= register_filesystem(&eventpoll_fs_type
);
1609 /* Mount the above commented virtual file system */
1610 eventpoll_mnt
= kern_mount(&eventpoll_fs_type
);
1611 error
= PTR_ERR(eventpoll_mnt
);
1612 if (IS_ERR(eventpoll_mnt
))
1615 DNPRINTK(3, (KERN_INFO
"[%p] eventpoll: successfully initialized.\n",
1620 panic("eventpoll_init() failed\n");
1624 static void __exit
eventpoll_exit(void)
1626 /* Undo all operations done inside eventpoll_init() */
1627 unregister_filesystem(&eventpoll_fs_type
);
1628 mntput(eventpoll_mnt
);
1629 kmem_cache_destroy(pwq_cache
);
1630 kmem_cache_destroy(epi_cache
);
1633 module_init(eventpoll_init
);
1634 module_exit(eventpoll_exit
);
1636 MODULE_LICENSE("GPL");