1 /* 2 * fs/eventpoll.c (Efficent event polling implementation) 3 * Copyright (C) 2001,...,2007 Davide Libenzi 4 * 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. 9 * 10 * Davide Libenzi <davidel@xmailserver.org> 11 * 12 */ 13 14 #include <linux/init.h> 15 #include <linux/kernel.h> 16 #include <linux/sched.h> 17 #include <linux/fs.h> 18 #include <linux/file.h> 19 #include <linux/signal.h> 20 #include <linux/errno.h> 21 #include <linux/mm.h> 22 #include <linux/slab.h> 23 #include <linux/poll.h> 24 #include <linux/string.h> 25 #include <linux/list.h> 26 #include <linux/hash.h> 27 #include <linux/spinlock.h> 28 #include <linux/syscalls.h> 29 #include <linux/rbtree.h> 30 #include <linux/wait.h> 31 #include <linux/eventpoll.h> 32 #include <linux/mount.h> 33 #include <linux/bitops.h> 34 #include <linux/mutex.h> 35 #include <linux/anon_inodes.h> 36 #include <asm/uaccess.h> 37 #include <asm/system.h> 38 #include <asm/io.h> 39 #include <asm/mman.h> 40 #include <asm/atomic.h> 41 42 /* 43 * LOCKING: 44 * There are three level of locking required by epoll : 45 * 46 * 1) epmutex (mutex) 47 * 2) ep->mtx (mutex) 48 * 3) ep->lock (spinlock) 49 * 50 * The acquire order is the one listed above, from 1 to 3. 51 * We need a spinlock (ep->lock) because we manipulate objects 52 * from inside the poll callback, that might be triggered from 53 * a wake_up() that in turn might be called from IRQ context. 54 * So we can't sleep inside the poll callback and hence we need 55 * a spinlock. During the event transfer loop (from kernel to 56 * user space) we could end up sleeping due a copy_to_user(), so 57 * we need a lock that will allow us to sleep. This lock is a 58 * mutex (ep->mtx). It is acquired during the event transfer loop, 59 * during epoll_ctl(EPOLL_CTL_DEL) and during eventpoll_release_file(). 60 * Then we also need a global mutex to serialize eventpoll_release_file() 61 * and ep_free(). 62 * This mutex is acquired by ep_free() during the epoll file 63 * cleanup path and it is also acquired by eventpoll_release_file() 64 * if a file has been pushed inside an epoll set and it is then 65 * close()d without a previous call toepoll_ctl(EPOLL_CTL_DEL). 66 * It is possible to drop the "ep->mtx" and to use the global 67 * mutex "epmutex" (together with "ep->lock") to have it working, 68 * but having "ep->mtx" will make the interface more scalable. 69 * Events that require holding "epmutex" are very rare, while for 70 * normal operations the epoll private "ep->mtx" will guarantee 71 * a better scalability. 72 */ 73 74 #define DEBUG_EPOLL 0 75 76 #if DEBUG_EPOLL > 0 77 #define DPRINTK(x) printk x 78 #define DNPRINTK(n, x) do { if ((n) <= DEBUG_EPOLL) printk x; } while (0) 79 #else /* #if DEBUG_EPOLL > 0 */ 80 #define DPRINTK(x) (void) 0 81 #define DNPRINTK(n, x) (void) 0 82 #endif /* #if DEBUG_EPOLL > 0 */ 83 84 #define DEBUG_EPI 0 85 86 #if DEBUG_EPI != 0 87 #define EPI_SLAB_DEBUG (SLAB_DEBUG_FREE | SLAB_RED_ZONE /* | SLAB_POISON */) 88 #else /* #if DEBUG_EPI != 0 */ 89 #define EPI_SLAB_DEBUG 0 90 #endif /* #if DEBUG_EPI != 0 */ 91 92 /* Epoll private bits inside the event mask */ 93 #define EP_PRIVATE_BITS (EPOLLONESHOT | EPOLLET) 94 95 /* Maximum number of poll wake up nests we are allowing */ 96 #define EP_MAX_POLLWAKE_NESTS 4 97 98 /* Maximum msec timeout value storeable in a long int */ 99 #define EP_MAX_MSTIMEO min(1000ULL * MAX_SCHEDULE_TIMEOUT / HZ, (LONG_MAX - 999ULL) / HZ) 100 101 #define EP_MAX_EVENTS (INT_MAX / sizeof(struct epoll_event)) 102 103 #define EP_UNACTIVE_PTR ((void *) -1L) 104 105 struct epoll_filefd { 106 struct file *file; 107 int fd; 108 }; 109 110 /* 111 * Node that is linked into the "wake_task_list" member of the "struct poll_safewake". 112 * It is used to keep track on all tasks that are currently inside the wake_up() code 113 * to 1) short-circuit the one coming from the same task and same wait queue head 114 * (loop) 2) allow a maximum number of epoll descriptors inclusion nesting 115 * 3) let go the ones coming from other tasks. 116 */ 117 struct wake_task_node { 118 struct list_head llink; 119 struct task_struct *task; 120 wait_queue_head_t *wq; 121 }; 122 123 /* 124 * This is used to implement the safe poll wake up avoiding to reenter 125 * the poll callback from inside wake_up(). 126 */ 127 struct poll_safewake { 128 struct list_head wake_task_list; 129 spinlock_t lock; 130 }; 131 132 /* 133 * Each file descriptor added to the eventpoll interface will 134 * have an entry of this type linked to the "rbr" RB tree. 135 */ 136 struct epitem { 137 /* RB tree node used to link this structure to the eventpoll RB tree */ 138 struct rb_node rbn; 139 140 /* List header used to link this structure to the eventpoll ready list */ 141 struct list_head rdllink; 142 143 /* 144 * Works together "struct eventpoll"->ovflist in keeping the 145 * single linked chain of items. 146 */ 147 struct epitem *next; 148 149 /* The file descriptor information this item refers to */ 150 struct epoll_filefd ffd; 151 152 /* Number of active wait queue attached to poll operations */ 153 int nwait; 154 155 /* List containing poll wait queues */ 156 struct list_head pwqlist; 157 158 /* The "container" of this item */ 159 struct eventpoll *ep; 160 161 /* List header used to link this item to the "struct file" items list */ 162 struct list_head fllink; 163 164 /* The structure that describe the interested events and the source fd */ 165 struct epoll_event event; 166 }; 167 168 /* 169 * This structure is stored inside the "private_data" member of the file 170 * structure and rapresent the main data sructure for the eventpoll 171 * interface. 172 */ 173 struct eventpoll { 174 /* Protect the this structure access */ 175 spinlock_t lock; 176 177 /* 178 * This mutex is used to ensure that files are not removed 179 * while epoll is using them. This is held during the event 180 * collection loop, the file cleanup path, the epoll file exit 181 * code and the ctl operations. 182 */ 183 struct mutex mtx; 184 185 /* Wait queue used by sys_epoll_wait() */ 186 wait_queue_head_t wq; 187 188 /* Wait queue used by file->poll() */ 189 wait_queue_head_t poll_wait; 190 191 /* List of ready file descriptors */ 192 struct list_head rdllist; 193 194 /* RB tree root used to store monitored fd structs */ 195 struct rb_root rbr; 196 197 /* 198 * This is a single linked list that chains all the "struct epitem" that 199 * happened while transfering ready events to userspace w/out 200 * holding ->lock. 201 */ 202 struct epitem *ovflist; 203 }; 204 205 /* Wait structure used by the poll hooks */ 206 struct eppoll_entry { 207 /* List header used to link this structure to the "struct epitem" */ 208 struct list_head llink; 209 210 /* The "base" pointer is set to the container "struct epitem" */ 211 void *base; 212 213 /* 214 * Wait queue item that will be linked to the target file wait 215 * queue head. 216 */ 217 wait_queue_t wait; 218 219 /* The wait queue head that linked the "wait" wait queue item */ 220 wait_queue_head_t *whead; 221 }; 222 223 /* Wrapper struct used by poll queueing */ 224 struct ep_pqueue { 225 poll_table pt; 226 struct epitem *epi; 227 }; 228 229 /* 230 * This mutex is used to serialize ep_free() and eventpoll_release_file(). 231 */ 232 static struct mutex epmutex; 233 234 /* Safe wake up implementation */ 235 static struct poll_safewake psw; 236 237 /* Slab cache used to allocate "struct epitem" */ 238 static struct kmem_cache *epi_cache __read_mostly; 239 240 /* Slab cache used to allocate "struct eppoll_entry" */ 241 static struct kmem_cache *pwq_cache __read_mostly; 242 243 244 /* Setup the structure that is used as key for the RB tree */ 245 static inline void ep_set_ffd(struct epoll_filefd *ffd, 246 struct file *file, int fd) 247 { 248 ffd->file = file; 249 ffd->fd = fd; 250 } 251 252 /* Compare RB tree keys */ 253 static inline int ep_cmp_ffd(struct epoll_filefd *p1, 254 struct epoll_filefd *p2) 255 { 256 return (p1->file > p2->file ? +1: 257 (p1->file < p2->file ? -1 : p1->fd - p2->fd)); 258 } 259 260 /* Special initialization for the RB tree node to detect linkage */ 261 static inline void ep_rb_initnode(struct rb_node *n) 262 { 263 rb_set_parent(n, n); 264 } 265 266 /* Removes a node from the RB tree and marks it for a fast is-linked check */ 267 static inline void ep_rb_erase(struct rb_node *n, struct rb_root *r) 268 { 269 rb_erase(n, r); 270 rb_set_parent(n, n); 271 } 272 273 /* Fast check to verify that the item is linked to the main RB tree */ 274 static inline int ep_rb_linked(struct rb_node *n) 275 { 276 return rb_parent(n) != n; 277 } 278 279 /* Tells us if the item is currently linked */ 280 static inline int ep_is_linked(struct list_head *p) 281 { 282 return !list_empty(p); 283 } 284 285 /* Get the "struct epitem" from a wait queue pointer */ 286 static inline struct epitem * ep_item_from_wait(wait_queue_t *p) 287 { 288 return container_of(p, struct eppoll_entry, wait)->base; 289 } 290 291 /* Get the "struct epitem" from an epoll queue wrapper */ 292 static inline struct epitem * ep_item_from_epqueue(poll_table *p) 293 { 294 return container_of(p, struct ep_pqueue, pt)->epi; 295 } 296 297 /* Tells if the epoll_ctl(2) operation needs an event copy from userspace */ 298 static inline int ep_op_has_event(int op) 299 { 300 return op != EPOLL_CTL_DEL; 301 } 302 303 /* Initialize the poll safe wake up structure */ 304 static void ep_poll_safewake_init(struct poll_safewake *psw) 305 { 306 307 INIT_LIST_HEAD(&psw->wake_task_list); 308 spin_lock_init(&psw->lock); 309 } 310 311 /* 312 * Perform a safe wake up of the poll wait list. The problem is that 313 * with the new callback'd wake up system, it is possible that the 314 * poll callback is reentered from inside the call to wake_up() done 315 * on the poll wait queue head. The rule is that we cannot reenter the 316 * wake up code from the same task more than EP_MAX_POLLWAKE_NESTS times, 317 * and we cannot reenter the same wait queue head at all. This will 318 * enable to have a hierarchy of epoll file descriptor of no more than 319 * EP_MAX_POLLWAKE_NESTS deep. We need the irq version of the spin lock 320 * because this one gets called by the poll callback, that in turn is called 321 * from inside a wake_up(), that might be called from irq context. 322 */ 323 static void ep_poll_safewake(struct poll_safewake *psw, wait_queue_head_t *wq) 324 { 325 int wake_nests = 0; 326 unsigned long flags; 327 struct task_struct *this_task = current; 328 struct list_head *lsthead = &psw->wake_task_list; 329 struct wake_task_node *tncur; 330 struct wake_task_node tnode; 331 332 spin_lock_irqsave(&psw->lock, flags); 333 334 /* Try to see if the current task is already inside this wakeup call */ 335 list_for_each_entry(tncur, lsthead, llink) { 336 337 if (tncur->wq == wq || 338 (tncur->task == this_task && ++wake_nests > EP_MAX_POLLWAKE_NESTS)) { 339 /* 340 * Ops ... loop detected or maximum nest level reached. 341 * We abort this wake by breaking the cycle itself. 342 */ 343 spin_unlock_irqrestore(&psw->lock, flags); 344 return; 345 } 346 } 347 348 /* Add the current task to the list */ 349 tnode.task = this_task; 350 tnode.wq = wq; 351 list_add(&tnode.llink, lsthead); 352 353 spin_unlock_irqrestore(&psw->lock, flags); 354 355 /* Do really wake up now */ 356 wake_up(wq); 357 358 /* Remove the current task from the list */ 359 spin_lock_irqsave(&psw->lock, flags); 360 list_del(&tnode.llink); 361 spin_unlock_irqrestore(&psw->lock, flags); 362 } 363 364 /* 365 * This function unregister poll callbacks from the associated file descriptor. 366 * Since this must be called without holding "ep->lock" the atomic exchange trick 367 * will protect us from multiple unregister. 368 */ 369 static void ep_unregister_pollwait(struct eventpoll *ep, struct epitem *epi) 370 { 371 int nwait; 372 struct list_head *lsthead = &epi->pwqlist; 373 struct eppoll_entry *pwq; 374 375 /* This is called without locks, so we need the atomic exchange */ 376 nwait = xchg(&epi->nwait, 0); 377 378 if (nwait) { 379 while (!list_empty(lsthead)) { 380 pwq = list_first_entry(lsthead, struct eppoll_entry, llink); 381 382 list_del_init(&pwq->llink); 383 remove_wait_queue(pwq->whead, &pwq->wait); 384 kmem_cache_free(pwq_cache, pwq); 385 } 386 } 387 } 388 389 /* 390 * Removes a "struct epitem" from the eventpoll RB tree and deallocates 391 * all the associated resources. Must be called with "mtx" held. 392 */ 393 static int ep_remove(struct eventpoll *ep, struct epitem *epi) 394 { 395 unsigned long flags; 396 struct file *file = epi->ffd.file; 397 398 /* 399 * Removes poll wait queue hooks. We _have_ to do this without holding 400 * the "ep->lock" otherwise a deadlock might occur. This because of the 401 * sequence of the lock acquisition. Here we do "ep->lock" then the wait 402 * queue head lock when unregistering the wait queue. The wakeup callback 403 * will run by holding the wait queue head lock and will call our callback 404 * that will try to get "ep->lock". 405 */ 406 ep_unregister_pollwait(ep, epi); 407 408 /* Remove the current item from the list of epoll hooks */ 409 spin_lock(&file->f_ep_lock); 410 if (ep_is_linked(&epi->fllink)) 411 list_del_init(&epi->fllink); 412 spin_unlock(&file->f_ep_lock); 413 414 if (ep_rb_linked(&epi->rbn)) 415 ep_rb_erase(&epi->rbn, &ep->rbr); 416 417 spin_lock_irqsave(&ep->lock, flags); 418 if (ep_is_linked(&epi->rdllink)) 419 list_del_init(&epi->rdllink); 420 spin_unlock_irqrestore(&ep->lock, flags); 421 422 /* At this point it is safe to free the eventpoll item */ 423 kmem_cache_free(epi_cache, epi); 424 425 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_remove(%p, %p)\n", 426 current, ep, file)); 427 428 return 0; 429 } 430 431 static void ep_free(struct eventpoll *ep) 432 { 433 struct rb_node *rbp; 434 struct epitem *epi; 435 436 /* We need to release all tasks waiting for these file */ 437 if (waitqueue_active(&ep->poll_wait)) 438 ep_poll_safewake(&psw, &ep->poll_wait); 439 440 /* 441 * We need to lock this because we could be hit by 442 * eventpoll_release_file() while we're freeing the "struct eventpoll". 443 * We do not need to hold "ep->mtx" here because the epoll file 444 * is on the way to be removed and no one has references to it 445 * anymore. The only hit might come from eventpoll_release_file() but 446 * holding "epmutex" is sufficent here. 447 */ 448 mutex_lock(&epmutex); 449 450 /* 451 * Walks through the whole tree by unregistering poll callbacks. 452 */ 453 for (rbp = rb_first(&ep->rbr); rbp; rbp = rb_next(rbp)) { 454 epi = rb_entry(rbp, struct epitem, rbn); 455 456 ep_unregister_pollwait(ep, epi); 457 } 458 459 /* 460 * Walks through the whole tree by freeing each "struct epitem". At this 461 * point we are sure no poll callbacks will be lingering around, and also by 462 * holding "epmutex" we can be sure that no file cleanup code will hit 463 * us during this operation. So we can avoid the lock on "ep->lock". 464 */ 465 while ((rbp = rb_first(&ep->rbr)) != NULL) { 466 epi = rb_entry(rbp, struct epitem, rbn); 467 ep_remove(ep, epi); 468 } 469 470 mutex_unlock(&epmutex); 471 mutex_destroy(&ep->mtx); 472 kfree(ep); 473 } 474 475 static int ep_eventpoll_release(struct inode *inode, struct file *file) 476 { 477 struct eventpoll *ep = file->private_data; 478 479 if (ep) 480 ep_free(ep); 481 482 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: close() ep=%p\n", current, ep)); 483 return 0; 484 } 485 486 static unsigned int ep_eventpoll_poll(struct file *file, poll_table *wait) 487 { 488 unsigned int pollflags = 0; 489 unsigned long flags; 490 struct eventpoll *ep = file->private_data; 491 492 /* Insert inside our poll wait queue */ 493 poll_wait(file, &ep->poll_wait, wait); 494 495 /* Check our condition */ 496 spin_lock_irqsave(&ep->lock, flags); 497 if (!list_empty(&ep->rdllist)) 498 pollflags = POLLIN | POLLRDNORM; 499 spin_unlock_irqrestore(&ep->lock, flags); 500 501 return pollflags; 502 } 503 504 /* File callbacks that implement the eventpoll file behaviour */ 505 static const struct file_operations eventpoll_fops = { 506 .release = ep_eventpoll_release, 507 .poll = ep_eventpoll_poll 508 }; 509 510 /* Fast test to see if the file is an evenpoll file */ 511 static inline int is_file_epoll(struct file *f) 512 { 513 return f->f_op == &eventpoll_fops; 514 } 515 516 /* 517 * This is called from eventpoll_release() to unlink files from the eventpoll 518 * interface. We need to have this facility to cleanup correctly files that are 519 * closed without being removed from the eventpoll interface. 520 */ 521 void eventpoll_release_file(struct file *file) 522 { 523 struct list_head *lsthead = &file->f_ep_links; 524 struct eventpoll *ep; 525 struct epitem *epi; 526 527 /* 528 * We don't want to get "file->f_ep_lock" because it is not 529 * necessary. It is not necessary because we're in the "struct file" 530 * cleanup path, and this means that noone is using this file anymore. 531 * So, for example, epoll_ctl() cannot hit here sicne if we reach this 532 * point, the file counter already went to zero and fget() would fail. 533 * The only hit might come from ep_free() but by holding the mutex 534 * will correctly serialize the operation. We do need to acquire 535 * "ep->mtx" after "epmutex" because ep_remove() requires it when called 536 * from anywhere but ep_free(). 537 */ 538 mutex_lock(&epmutex); 539 540 while (!list_empty(lsthead)) { 541 epi = list_first_entry(lsthead, struct epitem, fllink); 542 543 ep = epi->ep; 544 list_del_init(&epi->fllink); 545 mutex_lock(&ep->mtx); 546 ep_remove(ep, epi); 547 mutex_unlock(&ep->mtx); 548 } 549 550 mutex_unlock(&epmutex); 551 } 552 553 static int ep_alloc(struct eventpoll **pep) 554 { 555 struct eventpoll *ep = kzalloc(sizeof(*ep), GFP_KERNEL); 556 557 if (!ep) 558 return -ENOMEM; 559 560 spin_lock_init(&ep->lock); 561 mutex_init(&ep->mtx); 562 init_waitqueue_head(&ep->wq); 563 init_waitqueue_head(&ep->poll_wait); 564 INIT_LIST_HEAD(&ep->rdllist); 565 ep->rbr = RB_ROOT; 566 ep->ovflist = EP_UNACTIVE_PTR; 567 568 *pep = ep; 569 570 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_alloc() ep=%p\n", 571 current, ep)); 572 return 0; 573 } 574 575 /* 576 * Search the file inside the eventpoll tree. The RB tree operations 577 * are protected by the "mtx" mutex, and ep_find() must be called with 578 * "mtx" held. 579 */ 580 static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd) 581 { 582 int kcmp; 583 struct rb_node *rbp; 584 struct epitem *epi, *epir = NULL; 585 struct epoll_filefd ffd; 586 587 ep_set_ffd(&ffd, file, fd); 588 for (rbp = ep->rbr.rb_node; rbp; ) { 589 epi = rb_entry(rbp, struct epitem, rbn); 590 kcmp = ep_cmp_ffd(&ffd, &epi->ffd); 591 if (kcmp > 0) 592 rbp = rbp->rb_right; 593 else if (kcmp < 0) 594 rbp = rbp->rb_left; 595 else { 596 epir = epi; 597 break; 598 } 599 } 600 601 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_find(%p) -> %p\n", 602 current, file, epir)); 603 604 return epir; 605 } 606 607 /* 608 * This is the callback that is passed to the wait queue wakeup 609 * machanism. It is called by the stored file descriptors when they 610 * have events to report. 611 */ 612 static int ep_poll_callback(wait_queue_t *wait, unsigned mode, int sync, void *key) 613 { 614 int pwake = 0; 615 unsigned long flags; 616 struct epitem *epi = ep_item_from_wait(wait); 617 struct eventpoll *ep = epi->ep; 618 619 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: poll_callback(%p) epi=%p ep=%p\n", 620 current, epi->ffd.file, epi, ep)); 621 622 spin_lock_irqsave(&ep->lock, flags); 623 624 /* 625 * If the event mask does not contain any poll(2) event, we consider the 626 * descriptor to be disabled. This condition is likely the effect of the 627 * EPOLLONESHOT bit that disables the descriptor when an event is received, 628 * until the next EPOLL_CTL_MOD will be issued. 629 */ 630 if (!(epi->event.events & ~EP_PRIVATE_BITS)) 631 goto out_unlock; 632 633 /* 634 * If we are trasfering events to userspace, we can hold no locks 635 * (because we're accessing user memory, and because of linux f_op->poll() 636 * semantics). All the events that happens during that period of time are 637 * chained in ep->ovflist and requeued later on. 638 */ 639 if (unlikely(ep->ovflist != EP_UNACTIVE_PTR)) { 640 if (epi->next == EP_UNACTIVE_PTR) { 641 epi->next = ep->ovflist; 642 ep->ovflist = epi; 643 } 644 goto out_unlock; 645 } 646 647 /* If this file is already in the ready list we exit soon */ 648 if (ep_is_linked(&epi->rdllink)) 649 goto is_linked; 650 651 list_add_tail(&epi->rdllink, &ep->rdllist); 652 653 is_linked: 654 /* 655 * Wake up ( if active ) both the eventpoll wait list and the ->poll() 656 * wait list. 657 */ 658 if (waitqueue_active(&ep->wq)) 659 wake_up_locked(&ep->wq); 660 if (waitqueue_active(&ep->poll_wait)) 661 pwake++; 662 663 out_unlock: 664 spin_unlock_irqrestore(&ep->lock, flags); 665 666 /* We have to call this outside the lock */ 667 if (pwake) 668 ep_poll_safewake(&psw, &ep->poll_wait); 669 670 return 1; 671 } 672 673 /* 674 * This is the callback that is used to add our wait queue to the 675 * target file wakeup lists. 676 */ 677 static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead, 678 poll_table *pt) 679 { 680 struct epitem *epi = ep_item_from_epqueue(pt); 681 struct eppoll_entry *pwq; 682 683 if (epi->nwait >= 0 && (pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL))) { 684 init_waitqueue_func_entry(&pwq->wait, ep_poll_callback); 685 pwq->whead = whead; 686 pwq->base = epi; 687 add_wait_queue(whead, &pwq->wait); 688 list_add_tail(&pwq->llink, &epi->pwqlist); 689 epi->nwait++; 690 } else { 691 /* We have to signal that an error occurred */ 692 epi->nwait = -1; 693 } 694 } 695 696 static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi) 697 { 698 int kcmp; 699 struct rb_node **p = &ep->rbr.rb_node, *parent = NULL; 700 struct epitem *epic; 701 702 while (*p) { 703 parent = *p; 704 epic = rb_entry(parent, struct epitem, rbn); 705 kcmp = ep_cmp_ffd(&epi->ffd, &epic->ffd); 706 if (kcmp > 0) 707 p = &parent->rb_right; 708 else 709 p = &parent->rb_left; 710 } 711 rb_link_node(&epi->rbn, parent, p); 712 rb_insert_color(&epi->rbn, &ep->rbr); 713 } 714 715 /* 716 * Must be called with "mtx" held. 717 */ 718 static int ep_insert(struct eventpoll *ep, struct epoll_event *event, 719 struct file *tfile, int fd) 720 { 721 int error, revents, pwake = 0; 722 unsigned long flags; 723 struct epitem *epi; 724 struct ep_pqueue epq; 725 726 error = -ENOMEM; 727 if (!(epi = kmem_cache_alloc(epi_cache, GFP_KERNEL))) 728 goto error_return; 729 730 /* Item initialization follow here ... */ 731 ep_rb_initnode(&epi->rbn); 732 INIT_LIST_HEAD(&epi->rdllink); 733 INIT_LIST_HEAD(&epi->fllink); 734 INIT_LIST_HEAD(&epi->pwqlist); 735 epi->ep = ep; 736 ep_set_ffd(&epi->ffd, tfile, fd); 737 epi->event = *event; 738 epi->nwait = 0; 739 epi->next = EP_UNACTIVE_PTR; 740 741 /* Initialize the poll table using the queue callback */ 742 epq.epi = epi; 743 init_poll_funcptr(&epq.pt, ep_ptable_queue_proc); 744 745 /* 746 * Attach the item to the poll hooks and get current event bits. 747 * We can safely use the file* here because its usage count has 748 * been increased by the caller of this function. Note that after 749 * this operation completes, the poll callback can start hitting 750 * the new item. 751 */ 752 revents = tfile->f_op->poll(tfile, &epq.pt); 753 754 /* 755 * We have to check if something went wrong during the poll wait queue 756 * install process. Namely an allocation for a wait queue failed due 757 * high memory pressure. 758 */ 759 if (epi->nwait < 0) 760 goto error_unregister; 761 762 /* Add the current item to the list of active epoll hook for this file */ 763 spin_lock(&tfile->f_ep_lock); 764 list_add_tail(&epi->fllink, &tfile->f_ep_links); 765 spin_unlock(&tfile->f_ep_lock); 766 767 /* 768 * Add the current item to the RB tree. All RB tree operations are 769 * protected by "mtx", and ep_insert() is called with "mtx" held. 770 */ 771 ep_rbtree_insert(ep, epi); 772 773 /* We have to drop the new item inside our item list to keep track of it */ 774 spin_lock_irqsave(&ep->lock, flags); 775 776 /* If the file is already "ready" we drop it inside the ready list */ 777 if ((revents & event->events) && !ep_is_linked(&epi->rdllink)) { 778 list_add_tail(&epi->rdllink, &ep->rdllist); 779 780 /* Notify waiting tasks that events are available */ 781 if (waitqueue_active(&ep->wq)) 782 wake_up_locked(&ep->wq); 783 if (waitqueue_active(&ep->poll_wait)) 784 pwake++; 785 } 786 787 spin_unlock_irqrestore(&ep->lock, flags); 788 789 /* We have to call this outside the lock */ 790 if (pwake) 791 ep_poll_safewake(&psw, &ep->poll_wait); 792 793 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: ep_insert(%p, %p, %d)\n", 794 current, ep, tfile, fd)); 795 796 return 0; 797 798 error_unregister: 799 ep_unregister_pollwait(ep, epi); 800 801 /* 802 * We need to do this because an event could have been arrived on some 803 * allocated wait queue. Note that we don't care about the ep->ovflist 804 * list, since that is used/cleaned only inside a section bound by "mtx". 805 * And ep_insert() is called with "mtx" held. 806 */ 807 spin_lock_irqsave(&ep->lock, flags); 808 if (ep_is_linked(&epi->rdllink)) 809 list_del_init(&epi->rdllink); 810 spin_unlock_irqrestore(&ep->lock, flags); 811 812 kmem_cache_free(epi_cache, epi); 813 error_return: 814 return error; 815 } 816 817 /* 818 * Modify the interest event mask by dropping an event if the new mask 819 * has a match in the current file status. Must be called with "mtx" held. 820 */ 821 static int ep_modify(struct eventpoll *ep, struct epitem *epi, struct epoll_event *event) 822 { 823 int pwake = 0; 824 unsigned int revents; 825 unsigned long flags; 826 827 /* 828 * Set the new event interest mask before calling f_op->poll(), otherwise 829 * a potential race might occur. In fact if we do this operation inside 830 * the lock, an event might happen between the f_op->poll() call and the 831 * new event set registering. 832 */ 833 epi->event.events = event->events; 834 835 /* 836 * Get current event bits. We can safely use the file* here because 837 * its usage count has been increased by the caller of this function. 838 */ 839 revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL); 840 841 spin_lock_irqsave(&ep->lock, flags); 842 843 /* Copy the data member from inside the lock */ 844 epi->event.data = event->data; 845 846 /* 847 * If the item is "hot" and it is not registered inside the ready 848 * list, push it inside. 849 */ 850 if (revents & event->events) { 851 if (!ep_is_linked(&epi->rdllink)) { 852 list_add_tail(&epi->rdllink, &ep->rdllist); 853 854 /* Notify waiting tasks that events are available */ 855 if (waitqueue_active(&ep->wq)) 856 wake_up_locked(&ep->wq); 857 if (waitqueue_active(&ep->poll_wait)) 858 pwake++; 859 } 860 } 861 spin_unlock_irqrestore(&ep->lock, flags); 862 863 /* We have to call this outside the lock */ 864 if (pwake) 865 ep_poll_safewake(&psw, &ep->poll_wait); 866 867 return 0; 868 } 869 870 static int ep_send_events(struct eventpoll *ep, struct epoll_event __user *events, 871 int maxevents) 872 { 873 int eventcnt, error = -EFAULT, pwake = 0; 874 unsigned int revents; 875 unsigned long flags; 876 struct epitem *epi, *nepi; 877 struct list_head txlist; 878 879 INIT_LIST_HEAD(&txlist); 880 881 /* 882 * We need to lock this because we could be hit by 883 * eventpoll_release_file() and epoll_ctl(EPOLL_CTL_DEL). 884 */ 885 mutex_lock(&ep->mtx); 886 887 /* 888 * Steal the ready list, and re-init the original one to the 889 * empty list. Also, set ep->ovflist to NULL so that events 890 * happening while looping w/out locks, are not lost. We cannot 891 * have the poll callback to queue directly on ep->rdllist, 892 * because we are doing it in the loop below, in a lockless way. 893 */ 894 spin_lock_irqsave(&ep->lock, flags); 895 list_splice(&ep->rdllist, &txlist); 896 INIT_LIST_HEAD(&ep->rdllist); 897 ep->ovflist = NULL; 898 spin_unlock_irqrestore(&ep->lock, flags); 899 900 /* 901 * We can loop without lock because this is a task private list. 902 * We just splice'd out the ep->rdllist in ep_collect_ready_items(). 903 * Items cannot vanish during the loop because we are holding "mtx". 904 */ 905 for (eventcnt = 0; !list_empty(&txlist) && eventcnt < maxevents;) { 906 epi = list_first_entry(&txlist, struct epitem, rdllink); 907 908 list_del_init(&epi->rdllink); 909 910 /* 911 * Get the ready file event set. We can safely use the file 912 * because we are holding the "mtx" and this will guarantee 913 * that both the file and the item will not vanish. 914 */ 915 revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL); 916 revents &= epi->event.events; 917 918 /* 919 * Is the event mask intersect the caller-requested one, 920 * deliver the event to userspace. Again, we are holding 921 * "mtx", so no operations coming from userspace can change 922 * the item. 923 */ 924 if (revents) { 925 if (__put_user(revents, 926 &events[eventcnt].events) || 927 __put_user(epi->event.data, 928 &events[eventcnt].data)) 929 goto errxit; 930 if (epi->event.events & EPOLLONESHOT) 931 epi->event.events &= EP_PRIVATE_BITS; 932 eventcnt++; 933 } 934 /* 935 * At this point, noone can insert into ep->rdllist besides 936 * us. The epoll_ctl() callers are locked out by us holding 937 * "mtx" and the poll callback will queue them in ep->ovflist. 938 */ 939 if (!(epi->event.events & EPOLLET) && 940 (revents & epi->event.events)) 941 list_add_tail(&epi->rdllink, &ep->rdllist); 942 } 943 error = 0; 944 945 errxit: 946 947 spin_lock_irqsave(&ep->lock, flags); 948 /* 949 * During the time we spent in the loop above, some other events 950 * might have been queued by the poll callback. We re-insert them 951 * here (in case they are not already queued, or they're one-shot). 952 */ 953 for (nepi = ep->ovflist; (epi = nepi) != NULL; 954 nepi = epi->next, epi->next = EP_UNACTIVE_PTR) { 955 if (!ep_is_linked(&epi->rdllink) && 956 (epi->event.events & ~EP_PRIVATE_BITS)) 957 list_add_tail(&epi->rdllink, &ep->rdllist); 958 } 959 /* 960 * We need to set back ep->ovflist to EP_UNACTIVE_PTR, so that after 961 * releasing the lock, events will be queued in the normal way inside 962 * ep->rdllist. 963 */ 964 ep->ovflist = EP_UNACTIVE_PTR; 965 966 /* 967 * In case of error in the event-send loop, or in case the number of 968 * ready events exceeds the userspace limit, we need to splice the 969 * "txlist" back inside ep->rdllist. 970 */ 971 list_splice(&txlist, &ep->rdllist); 972 973 if (!list_empty(&ep->rdllist)) { 974 /* 975 * Wake up (if active) both the eventpoll wait list and the ->poll() 976 * wait list (delayed after we release the lock). 977 */ 978 if (waitqueue_active(&ep->wq)) 979 wake_up_locked(&ep->wq); 980 if (waitqueue_active(&ep->poll_wait)) 981 pwake++; 982 } 983 spin_unlock_irqrestore(&ep->lock, flags); 984 985 mutex_unlock(&ep->mtx); 986 987 /* We have to call this outside the lock */ 988 if (pwake) 989 ep_poll_safewake(&psw, &ep->poll_wait); 990 991 return eventcnt == 0 ? error: eventcnt; 992 } 993 994 static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, 995 int maxevents, long timeout) 996 { 997 int res, eavail; 998 unsigned long flags; 999 long jtimeout; 1000 wait_queue_t wait; 1001 1002 /* 1003 * Calculate the timeout by checking for the "infinite" value ( -1 ) 1004 * and the overflow condition. The passed timeout is in milliseconds, 1005 * that why (t * HZ) / 1000. 1006 */ 1007 jtimeout = (timeout < 0 || timeout >= EP_MAX_MSTIMEO) ? 1008 MAX_SCHEDULE_TIMEOUT : (timeout * HZ + 999) / 1000; 1009 1010 retry: 1011 spin_lock_irqsave(&ep->lock, flags); 1012 1013 res = 0; 1014 if (list_empty(&ep->rdllist)) { 1015 /* 1016 * We don't have any available event to return to the caller. 1017 * We need to sleep here, and we will be wake up by 1018 * ep_poll_callback() when events will become available. 1019 */ 1020 init_waitqueue_entry(&wait, current); 1021 wait.flags |= WQ_FLAG_EXCLUSIVE; 1022 __add_wait_queue(&ep->wq, &wait); 1023 1024 for (;;) { 1025 /* 1026 * We don't want to sleep if the ep_poll_callback() sends us 1027 * a wakeup in between. That's why we set the task state 1028 * to TASK_INTERRUPTIBLE before doing the checks. 1029 */ 1030 set_current_state(TASK_INTERRUPTIBLE); 1031 if (!list_empty(&ep->rdllist) || !jtimeout) 1032 break; 1033 if (signal_pending(current)) { 1034 res = -EINTR; 1035 break; 1036 } 1037 1038 spin_unlock_irqrestore(&ep->lock, flags); 1039 jtimeout = schedule_timeout(jtimeout); 1040 spin_lock_irqsave(&ep->lock, flags); 1041 } 1042 __remove_wait_queue(&ep->wq, &wait); 1043 1044 set_current_state(TASK_RUNNING); 1045 } 1046 1047 /* Is it worth to try to dig for events ? */ 1048 eavail = !list_empty(&ep->rdllist); 1049 1050 spin_unlock_irqrestore(&ep->lock, flags); 1051 1052 /* 1053 * Try to transfer events to user space. In case we get 0 events and 1054 * there's still timeout left over, we go trying again in search of 1055 * more luck. 1056 */ 1057 if (!res && eavail && 1058 !(res = ep_send_events(ep, events, maxevents)) && jtimeout) 1059 goto retry; 1060 1061 return res; 1062 } 1063 1064 /* 1065 * It opens an eventpoll file descriptor. The "size" parameter is there 1066 * for historical reasons, when epoll was using an hash instead of an 1067 * RB tree. With the current implementation, the "size" parameter is ignored 1068 * (besides sanity checks). 1069 */ 1070 asmlinkage long sys_epoll_create(int size) 1071 { 1072 int error, fd = -1; 1073 struct eventpoll *ep; 1074 struct inode *inode; 1075 struct file *file; 1076 1077 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d)\n", 1078 current, size)); 1079 1080 /* 1081 * Sanity check on the size parameter, and create the internal data 1082 * structure ( "struct eventpoll" ). 1083 */ 1084 error = -EINVAL; 1085 if (size <= 0 || (error = ep_alloc(&ep)) != 0) 1086 goto error_return; 1087 1088 /* 1089 * Creates all the items needed to setup an eventpoll file. That is, 1090 * a file structure, and inode and a free file descriptor. 1091 */ 1092 error = anon_inode_getfd(&fd, &inode, &file, "[eventpoll]", 1093 &eventpoll_fops, ep); 1094 if (error) 1095 goto error_free; 1096 1097 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d) = %d\n", 1098 current, size, fd)); 1099 1100 return fd; 1101 1102 error_free: 1103 ep_free(ep); 1104 error_return: 1105 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_create(%d) = %d\n", 1106 current, size, error)); 1107 return error; 1108 } 1109 1110 /* 1111 * The following function implements the controller interface for 1112 * the eventpoll file that enables the insertion/removal/change of 1113 * file descriptors inside the interest set. 1114 */ 1115 asmlinkage long sys_epoll_ctl(int epfd, int op, int fd, 1116 struct epoll_event __user *event) 1117 { 1118 int error; 1119 struct file *file, *tfile; 1120 struct eventpoll *ep; 1121 struct epitem *epi; 1122 struct epoll_event epds; 1123 1124 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p)\n", 1125 current, epfd, op, fd, event)); 1126 1127 error = -EFAULT; 1128 if (ep_op_has_event(op) && 1129 copy_from_user(&epds, event, sizeof(struct epoll_event))) 1130 goto error_return; 1131 1132 /* Get the "struct file *" for the eventpoll file */ 1133 error = -EBADF; 1134 file = fget(epfd); 1135 if (!file) 1136 goto error_return; 1137 1138 /* Get the "struct file *" for the target file */ 1139 tfile = fget(fd); 1140 if (!tfile) 1141 goto error_fput; 1142 1143 /* The target file descriptor must support poll */ 1144 error = -EPERM; 1145 if (!tfile->f_op || !tfile->f_op->poll) 1146 goto error_tgt_fput; 1147 1148 /* 1149 * We have to check that the file structure underneath the file descriptor 1150 * the user passed to us _is_ an eventpoll file. And also we do not permit 1151 * adding an epoll file descriptor inside itself. 1152 */ 1153 error = -EINVAL; 1154 if (file == tfile || !is_file_epoll(file)) 1155 goto error_tgt_fput; 1156 1157 /* 1158 * At this point it is safe to assume that the "private_data" contains 1159 * our own data structure. 1160 */ 1161 ep = file->private_data; 1162 1163 mutex_lock(&ep->mtx); 1164 1165 /* 1166 * Try to lookup the file inside our RB tree, Since we grabbed "mtx" 1167 * above, we can be sure to be able to use the item looked up by 1168 * ep_find() till we release the mutex. 1169 */ 1170 epi = ep_find(ep, tfile, fd); 1171 1172 error = -EINVAL; 1173 switch (op) { 1174 case EPOLL_CTL_ADD: 1175 if (!epi) { 1176 epds.events |= POLLERR | POLLHUP; 1177 1178 error = ep_insert(ep, &epds, tfile, fd); 1179 } else 1180 error = -EEXIST; 1181 break; 1182 case EPOLL_CTL_DEL: 1183 if (epi) 1184 error = ep_remove(ep, epi); 1185 else 1186 error = -ENOENT; 1187 break; 1188 case EPOLL_CTL_MOD: 1189 if (epi) { 1190 epds.events |= POLLERR | POLLHUP; 1191 error = ep_modify(ep, epi, &epds); 1192 } else 1193 error = -ENOENT; 1194 break; 1195 } 1196 mutex_unlock(&ep->mtx); 1197 1198 error_tgt_fput: 1199 fput(tfile); 1200 error_fput: 1201 fput(file); 1202 error_return: 1203 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_ctl(%d, %d, %d, %p) = %d\n", 1204 current, epfd, op, fd, event, error)); 1205 1206 return error; 1207 } 1208 1209 /* 1210 * Implement the event wait interface for the eventpoll file. It is the kernel 1211 * part of the user space epoll_wait(2). 1212 */ 1213 asmlinkage long sys_epoll_wait(int epfd, struct epoll_event __user *events, 1214 int maxevents, int timeout) 1215 { 1216 int error; 1217 struct file *file; 1218 struct eventpoll *ep; 1219 1220 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d)\n", 1221 current, epfd, events, maxevents, timeout)); 1222 1223 /* The maximum number of event must be greater than zero */ 1224 if (maxevents <= 0 || maxevents > EP_MAX_EVENTS) 1225 return -EINVAL; 1226 1227 /* Verify that the area passed by the user is writeable */ 1228 if (!access_ok(VERIFY_WRITE, events, maxevents * sizeof(struct epoll_event))) { 1229 error = -EFAULT; 1230 goto error_return; 1231 } 1232 1233 /* Get the "struct file *" for the eventpoll file */ 1234 error = -EBADF; 1235 file = fget(epfd); 1236 if (!file) 1237 goto error_return; 1238 1239 /* 1240 * We have to check that the file structure underneath the fd 1241 * the user passed to us _is_ an eventpoll file. 1242 */ 1243 error = -EINVAL; 1244 if (!is_file_epoll(file)) 1245 goto error_fput; 1246 1247 /* 1248 * At this point it is safe to assume that the "private_data" contains 1249 * our own data structure. 1250 */ 1251 ep = file->private_data; 1252 1253 /* Time to fish for events ... */ 1254 error = ep_poll(ep, events, maxevents, timeout); 1255 1256 error_fput: 1257 fput(file); 1258 error_return: 1259 DNPRINTK(3, (KERN_INFO "[%p] eventpoll: sys_epoll_wait(%d, %p, %d, %d) = %d\n", 1260 current, epfd, events, maxevents, timeout, error)); 1261 1262 return error; 1263 } 1264 1265 #ifdef TIF_RESTORE_SIGMASK 1266 1267 /* 1268 * Implement the event wait interface for the eventpoll file. It is the kernel 1269 * part of the user space epoll_pwait(2). 1270 */ 1271 asmlinkage long sys_epoll_pwait(int epfd, struct epoll_event __user *events, 1272 int maxevents, int timeout, const sigset_t __user *sigmask, 1273 size_t sigsetsize) 1274 { 1275 int error; 1276 sigset_t ksigmask, sigsaved; 1277 1278 /* 1279 * If the caller wants a certain signal mask to be set during the wait, 1280 * we apply it here. 1281 */ 1282 if (sigmask) { 1283 if (sigsetsize != sizeof(sigset_t)) 1284 return -EINVAL; 1285 if (copy_from_user(&ksigmask, sigmask, sizeof(ksigmask))) 1286 return -EFAULT; 1287 sigdelsetmask(&ksigmask, sigmask(SIGKILL) | sigmask(SIGSTOP)); 1288 sigprocmask(SIG_SETMASK, &ksigmask, &sigsaved); 1289 } 1290 1291 error = sys_epoll_wait(epfd, events, maxevents, timeout); 1292 1293 /* 1294 * If we changed the signal mask, we need to restore the original one. 1295 * In case we've got a signal while waiting, we do not restore the 1296 * signal mask yet, and we allow do_signal() to deliver the signal on 1297 * the way back to userspace, before the signal mask is restored. 1298 */ 1299 if (sigmask) { 1300 if (error == -EINTR) { 1301 memcpy(¤t->saved_sigmask, &sigsaved, 1302 sizeof(sigsaved)); 1303 set_thread_flag(TIF_RESTORE_SIGMASK); 1304 } else 1305 sigprocmask(SIG_SETMASK, &sigsaved, NULL); 1306 } 1307 1308 return error; 1309 } 1310 1311 #endif /* #ifdef TIF_RESTORE_SIGMASK */ 1312 1313 static int __init eventpoll_init(void) 1314 { 1315 mutex_init(&epmutex); 1316 1317 /* Initialize the structure used to perform safe poll wait head wake ups */ 1318 ep_poll_safewake_init(&psw); 1319 1320 /* Allocates slab cache used to allocate "struct epitem" items */ 1321 epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 1322 0, SLAB_HWCACHE_ALIGN|EPI_SLAB_DEBUG|SLAB_PANIC, 1323 NULL); 1324 1325 /* Allocates slab cache used to allocate "struct eppoll_entry" */ 1326 pwq_cache = kmem_cache_create("eventpoll_pwq", 1327 sizeof(struct eppoll_entry), 0, 1328 EPI_SLAB_DEBUG|SLAB_PANIC, NULL); 1329 1330 return 0; 1331 } 1332 fs_initcall(eventpoll_init); 1333 1334