1 /* 2 * fs/eventpoll.c (Efficient event retrieval implementation) 3 * Copyright (C) 2001,...,2009 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 <linux/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 to epoll_ctl(EPOLL_CTL_DEL). 66 * It is also acquired when inserting an epoll fd onto another epoll 67 * fd. We do this so that we walk the epoll tree and ensure that this 68 * insertion does not create a cycle of epoll file descriptors, which 69 * could lead to deadlock. We need a global mutex to prevent two 70 * simultaneous inserts (A into B and B into A) from racing and 71 * constructing a cycle without either insert observing that it is 72 * going to. 73 * It is necessary to acquire multiple "ep->mtx"es at once in the 74 * case when one epoll fd is added to another. In this case, we 75 * always acquire the locks in the order of nesting (i.e. after 76 * epoll_ctl(e1, EPOLL_CTL_ADD, e2), e1->mtx will always be acquired 77 * before e2->mtx). Since we disallow cycles of epoll file 78 * descriptors, this ensures that the mutexes are well-ordered. In 79 * order to communicate this nesting to lockdep, when walking a tree 80 * of epoll file descriptors, we use the current recursion depth as 81 * the lockdep subkey. 82 * It is possible to drop the "ep->mtx" and to use the global 83 * mutex "epmutex" (together with "ep->lock") to have it working, 84 * but having "ep->mtx" will make the interface more scalable. 85 * Events that require holding "epmutex" are very rare, while for 86 * normal operations the epoll private "ep->mtx" will guarantee 87 * a better scalability. 88 */ 89 90 /* Epoll private bits inside the event mask */ 91 #define EP_PRIVATE_BITS (EPOLLONESHOT | EPOLLET) 92 93 /* Maximum number of nesting allowed inside epoll sets */ 94 #define EP_MAX_NESTS 4 95 96 #define EP_MAX_EVENTS (INT_MAX / sizeof(struct epoll_event)) 97 98 #define EP_UNACTIVE_PTR ((void *) -1L) 99 100 #define EP_ITEM_COST (sizeof(struct epitem) + sizeof(struct eppoll_entry)) 101 102 struct epoll_filefd { 103 struct file *file; 104 int fd; 105 }; 106 107 /* 108 * Structure used to track possible nested calls, for too deep recursions 109 * and loop cycles. 110 */ 111 struct nested_call_node { 112 struct list_head llink; 113 void *cookie; 114 void *ctx; 115 }; 116 117 /* 118 * This structure is used as collector for nested calls, to check for 119 * maximum recursion dept and loop cycles. 120 */ 121 struct nested_calls { 122 struct list_head tasks_call_list; 123 spinlock_t lock; 124 }; 125 126 /* 127 * Each file descriptor added to the eventpoll interface will 128 * have an entry of this type linked to the "rbr" RB tree. 129 */ 130 struct epitem { 131 /* RB tree node used to link this structure to the eventpoll RB tree */ 132 struct rb_node rbn; 133 134 /* List header used to link this structure to the eventpoll ready list */ 135 struct list_head rdllink; 136 137 /* 138 * Works together "struct eventpoll"->ovflist in keeping the 139 * single linked chain of items. 140 */ 141 struct epitem *next; 142 143 /* The file descriptor information this item refers to */ 144 struct epoll_filefd ffd; 145 146 /* Number of active wait queue attached to poll operations */ 147 int nwait; 148 149 /* List containing poll wait queues */ 150 struct list_head pwqlist; 151 152 /* The "container" of this item */ 153 struct eventpoll *ep; 154 155 /* List header used to link this item to the "struct file" items list */ 156 struct list_head fllink; 157 158 /* The structure that describe the interested events and the source fd */ 159 struct epoll_event event; 160 }; 161 162 /* 163 * This structure is stored inside the "private_data" member of the file 164 * structure and represents the main data structure for the eventpoll 165 * interface. 166 */ 167 struct eventpoll { 168 /* Protect the access to this structure */ 169 spinlock_t lock; 170 171 /* 172 * This mutex is used to ensure that files are not removed 173 * while epoll is using them. This is held during the event 174 * collection loop, the file cleanup path, the epoll file exit 175 * code and the ctl operations. 176 */ 177 struct mutex mtx; 178 179 /* Wait queue used by sys_epoll_wait() */ 180 wait_queue_head_t wq; 181 182 /* Wait queue used by file->poll() */ 183 wait_queue_head_t poll_wait; 184 185 /* List of ready file descriptors */ 186 struct list_head rdllist; 187 188 /* RB tree root used to store monitored fd structs */ 189 struct rb_root rbr; 190 191 /* 192 * This is a single linked list that chains all the "struct epitem" that 193 * happened while transferring ready events to userspace w/out 194 * holding ->lock. 195 */ 196 struct epitem *ovflist; 197 198 /* The user that created the eventpoll descriptor */ 199 struct user_struct *user; 200 201 struct file *file; 202 203 /* used to optimize loop detection check */ 204 int visited; 205 struct list_head visited_list_link; 206 }; 207 208 /* Wait structure used by the poll hooks */ 209 struct eppoll_entry { 210 /* List header used to link this structure to the "struct epitem" */ 211 struct list_head llink; 212 213 /* The "base" pointer is set to the container "struct epitem" */ 214 struct epitem *base; 215 216 /* 217 * Wait queue item that will be linked to the target file wait 218 * queue head. 219 */ 220 wait_queue_t wait; 221 222 /* The wait queue head that linked the "wait" wait queue item */ 223 wait_queue_head_t *whead; 224 }; 225 226 /* Wrapper struct used by poll queueing */ 227 struct ep_pqueue { 228 poll_table pt; 229 struct epitem *epi; 230 }; 231 232 /* Used by the ep_send_events() function as callback private data */ 233 struct ep_send_events_data { 234 int maxevents; 235 struct epoll_event __user *events; 236 }; 237 238 /* 239 * Configuration options available inside /proc/sys/fs/epoll/ 240 */ 241 /* Maximum number of epoll watched descriptors, per user */ 242 static long max_user_watches __read_mostly; 243 244 /* 245 * This mutex is used to serialize ep_free() and eventpoll_release_file(). 246 */ 247 static DEFINE_MUTEX(epmutex); 248 249 /* Used to check for epoll file descriptor inclusion loops */ 250 static struct nested_calls poll_loop_ncalls; 251 252 /* Used for safe wake up implementation */ 253 static struct nested_calls poll_safewake_ncalls; 254 255 /* Used to call file's f_op->poll() under the nested calls boundaries */ 256 static struct nested_calls poll_readywalk_ncalls; 257 258 /* Slab cache used to allocate "struct epitem" */ 259 static struct kmem_cache *epi_cache __read_mostly; 260 261 /* Slab cache used to allocate "struct eppoll_entry" */ 262 static struct kmem_cache *pwq_cache __read_mostly; 263 264 /* Visited nodes during ep_loop_check(), so we can unset them when we finish */ 265 static LIST_HEAD(visited_list); 266 267 /* 268 * List of files with newly added links, where we may need to limit the number 269 * of emanating paths. Protected by the epmutex. 270 */ 271 static LIST_HEAD(tfile_check_list); 272 273 #ifdef CONFIG_SYSCTL 274 275 #include <linux/sysctl.h> 276 277 static long zero; 278 static long long_max = LONG_MAX; 279 280 ctl_table epoll_table[] = { 281 { 282 .procname = "max_user_watches", 283 .data = &max_user_watches, 284 .maxlen = sizeof(max_user_watches), 285 .mode = 0644, 286 .proc_handler = proc_doulongvec_minmax, 287 .extra1 = &zero, 288 .extra2 = &long_max, 289 }, 290 { } 291 }; 292 #endif /* CONFIG_SYSCTL */ 293 294 static const struct file_operations eventpoll_fops; 295 296 static inline int is_file_epoll(struct file *f) 297 { 298 return f->f_op == &eventpoll_fops; 299 } 300 301 /* Setup the structure that is used as key for the RB tree */ 302 static inline void ep_set_ffd(struct epoll_filefd *ffd, 303 struct file *file, int fd) 304 { 305 ffd->file = file; 306 ffd->fd = fd; 307 } 308 309 /* Compare RB tree keys */ 310 static inline int ep_cmp_ffd(struct epoll_filefd *p1, 311 struct epoll_filefd *p2) 312 { 313 return (p1->file > p2->file ? +1: 314 (p1->file < p2->file ? -1 : p1->fd - p2->fd)); 315 } 316 317 /* Tells us if the item is currently linked */ 318 static inline int ep_is_linked(struct list_head *p) 319 { 320 return !list_empty(p); 321 } 322 323 static inline struct eppoll_entry *ep_pwq_from_wait(wait_queue_t *p) 324 { 325 return container_of(p, struct eppoll_entry, wait); 326 } 327 328 /* Get the "struct epitem" from a wait queue pointer */ 329 static inline struct epitem *ep_item_from_wait(wait_queue_t *p) 330 { 331 return container_of(p, struct eppoll_entry, wait)->base; 332 } 333 334 /* Get the "struct epitem" from an epoll queue wrapper */ 335 static inline struct epitem *ep_item_from_epqueue(poll_table *p) 336 { 337 return container_of(p, struct ep_pqueue, pt)->epi; 338 } 339 340 /* Tells if the epoll_ctl(2) operation needs an event copy from userspace */ 341 static inline int ep_op_has_event(int op) 342 { 343 return op != EPOLL_CTL_DEL; 344 } 345 346 /* Initialize the poll safe wake up structure */ 347 static void ep_nested_calls_init(struct nested_calls *ncalls) 348 { 349 INIT_LIST_HEAD(&ncalls->tasks_call_list); 350 spin_lock_init(&ncalls->lock); 351 } 352 353 /** 354 * ep_events_available - Checks if ready events might be available. 355 * 356 * @ep: Pointer to the eventpoll context. 357 * 358 * Returns: Returns a value different than zero if ready events are available, 359 * or zero otherwise. 360 */ 361 static inline int ep_events_available(struct eventpoll *ep) 362 { 363 return !list_empty(&ep->rdllist) || ep->ovflist != EP_UNACTIVE_PTR; 364 } 365 366 /** 367 * ep_call_nested - Perform a bound (possibly) nested call, by checking 368 * that the recursion limit is not exceeded, and that 369 * the same nested call (by the meaning of same cookie) is 370 * no re-entered. 371 * 372 * @ncalls: Pointer to the nested_calls structure to be used for this call. 373 * @max_nests: Maximum number of allowed nesting calls. 374 * @nproc: Nested call core function pointer. 375 * @priv: Opaque data to be passed to the @nproc callback. 376 * @cookie: Cookie to be used to identify this nested call. 377 * @ctx: This instance context. 378 * 379 * Returns: Returns the code returned by the @nproc callback, or -1 if 380 * the maximum recursion limit has been exceeded. 381 */ 382 static int ep_call_nested(struct nested_calls *ncalls, int max_nests, 383 int (*nproc)(void *, void *, int), void *priv, 384 void *cookie, void *ctx) 385 { 386 int error, call_nests = 0; 387 unsigned long flags; 388 struct list_head *lsthead = &ncalls->tasks_call_list; 389 struct nested_call_node *tncur; 390 struct nested_call_node tnode; 391 392 spin_lock_irqsave(&ncalls->lock, flags); 393 394 /* 395 * Try to see if the current task is already inside this wakeup call. 396 * We use a list here, since the population inside this set is always 397 * very much limited. 398 */ 399 list_for_each_entry(tncur, lsthead, llink) { 400 if (tncur->ctx == ctx && 401 (tncur->cookie == cookie || ++call_nests > max_nests)) { 402 /* 403 * Ops ... loop detected or maximum nest level reached. 404 * We abort this wake by breaking the cycle itself. 405 */ 406 error = -1; 407 goto out_unlock; 408 } 409 } 410 411 /* Add the current task and cookie to the list */ 412 tnode.ctx = ctx; 413 tnode.cookie = cookie; 414 list_add(&tnode.llink, lsthead); 415 416 spin_unlock_irqrestore(&ncalls->lock, flags); 417 418 /* Call the nested function */ 419 error = (*nproc)(priv, cookie, call_nests); 420 421 /* Remove the current task from the list */ 422 spin_lock_irqsave(&ncalls->lock, flags); 423 list_del(&tnode.llink); 424 out_unlock: 425 spin_unlock_irqrestore(&ncalls->lock, flags); 426 427 return error; 428 } 429 430 #ifdef CONFIG_DEBUG_LOCK_ALLOC 431 static inline void ep_wake_up_nested(wait_queue_head_t *wqueue, 432 unsigned long events, int subclass) 433 { 434 unsigned long flags; 435 436 spin_lock_irqsave_nested(&wqueue->lock, flags, subclass); 437 wake_up_locked_poll(wqueue, events); 438 spin_unlock_irqrestore(&wqueue->lock, flags); 439 } 440 #else 441 static inline void ep_wake_up_nested(wait_queue_head_t *wqueue, 442 unsigned long events, int subclass) 443 { 444 wake_up_poll(wqueue, events); 445 } 446 #endif 447 448 static int ep_poll_wakeup_proc(void *priv, void *cookie, int call_nests) 449 { 450 ep_wake_up_nested((wait_queue_head_t *) cookie, POLLIN, 451 1 + call_nests); 452 return 0; 453 } 454 455 /* 456 * Perform a safe wake up of the poll wait list. The problem is that 457 * with the new callback'd wake up system, it is possible that the 458 * poll callback is reentered from inside the call to wake_up() done 459 * on the poll wait queue head. The rule is that we cannot reenter the 460 * wake up code from the same task more than EP_MAX_NESTS times, 461 * and we cannot reenter the same wait queue head at all. This will 462 * enable to have a hierarchy of epoll file descriptor of no more than 463 * EP_MAX_NESTS deep. 464 */ 465 static void ep_poll_safewake(wait_queue_head_t *wq) 466 { 467 int this_cpu = get_cpu(); 468 469 ep_call_nested(&poll_safewake_ncalls, EP_MAX_NESTS, 470 ep_poll_wakeup_proc, NULL, wq, (void *) (long) this_cpu); 471 472 put_cpu(); 473 } 474 475 static void ep_remove_wait_queue(struct eppoll_entry *pwq) 476 { 477 wait_queue_head_t *whead; 478 479 rcu_read_lock(); 480 /* If it is cleared by POLLFREE, it should be rcu-safe */ 481 whead = rcu_dereference(pwq->whead); 482 if (whead) 483 remove_wait_queue(whead, &pwq->wait); 484 rcu_read_unlock(); 485 } 486 487 /* 488 * This function unregisters poll callbacks from the associated file 489 * descriptor. Must be called with "mtx" held (or "epmutex" if called from 490 * ep_free). 491 */ 492 static void ep_unregister_pollwait(struct eventpoll *ep, struct epitem *epi) 493 { 494 struct list_head *lsthead = &epi->pwqlist; 495 struct eppoll_entry *pwq; 496 497 while (!list_empty(lsthead)) { 498 pwq = list_first_entry(lsthead, struct eppoll_entry, llink); 499 500 list_del(&pwq->llink); 501 ep_remove_wait_queue(pwq); 502 kmem_cache_free(pwq_cache, pwq); 503 } 504 } 505 506 /** 507 * ep_scan_ready_list - Scans the ready list in a way that makes possible for 508 * the scan code, to call f_op->poll(). Also allows for 509 * O(NumReady) performance. 510 * 511 * @ep: Pointer to the epoll private data structure. 512 * @sproc: Pointer to the scan callback. 513 * @priv: Private opaque data passed to the @sproc callback. 514 * @depth: The current depth of recursive f_op->poll calls. 515 * 516 * Returns: The same integer error code returned by the @sproc callback. 517 */ 518 static int ep_scan_ready_list(struct eventpoll *ep, 519 int (*sproc)(struct eventpoll *, 520 struct list_head *, void *), 521 void *priv, 522 int depth) 523 { 524 int error, pwake = 0; 525 unsigned long flags; 526 struct epitem *epi, *nepi; 527 LIST_HEAD(txlist); 528 529 /* 530 * We need to lock this because we could be hit by 531 * eventpoll_release_file() and epoll_ctl(). 532 */ 533 mutex_lock_nested(&ep->mtx, depth); 534 535 /* 536 * Steal the ready list, and re-init the original one to the 537 * empty list. Also, set ep->ovflist to NULL so that events 538 * happening while looping w/out locks, are not lost. We cannot 539 * have the poll callback to queue directly on ep->rdllist, 540 * because we want the "sproc" callback to be able to do it 541 * in a lockless way. 542 */ 543 spin_lock_irqsave(&ep->lock, flags); 544 list_splice_init(&ep->rdllist, &txlist); 545 ep->ovflist = NULL; 546 spin_unlock_irqrestore(&ep->lock, flags); 547 548 /* 549 * Now call the callback function. 550 */ 551 error = (*sproc)(ep, &txlist, priv); 552 553 spin_lock_irqsave(&ep->lock, flags); 554 /* 555 * During the time we spent inside the "sproc" callback, some 556 * other events might have been queued by the poll callback. 557 * We re-insert them inside the main ready-list here. 558 */ 559 for (nepi = ep->ovflist; (epi = nepi) != NULL; 560 nepi = epi->next, epi->next = EP_UNACTIVE_PTR) { 561 /* 562 * We need to check if the item is already in the list. 563 * During the "sproc" callback execution time, items are 564 * queued into ->ovflist but the "txlist" might already 565 * contain them, and the list_splice() below takes care of them. 566 */ 567 if (!ep_is_linked(&epi->rdllink)) 568 list_add_tail(&epi->rdllink, &ep->rdllist); 569 } 570 /* 571 * We need to set back ep->ovflist to EP_UNACTIVE_PTR, so that after 572 * releasing the lock, events will be queued in the normal way inside 573 * ep->rdllist. 574 */ 575 ep->ovflist = EP_UNACTIVE_PTR; 576 577 /* 578 * Quickly re-inject items left on "txlist". 579 */ 580 list_splice(&txlist, &ep->rdllist); 581 582 if (!list_empty(&ep->rdllist)) { 583 /* 584 * Wake up (if active) both the eventpoll wait list and 585 * the ->poll() wait list (delayed after we release the lock). 586 */ 587 if (waitqueue_active(&ep->wq)) 588 wake_up_locked(&ep->wq); 589 if (waitqueue_active(&ep->poll_wait)) 590 pwake++; 591 } 592 spin_unlock_irqrestore(&ep->lock, flags); 593 594 mutex_unlock(&ep->mtx); 595 596 /* We have to call this outside the lock */ 597 if (pwake) 598 ep_poll_safewake(&ep->poll_wait); 599 600 return error; 601 } 602 603 /* 604 * Removes a "struct epitem" from the eventpoll RB tree and deallocates 605 * all the associated resources. Must be called with "mtx" held. 606 */ 607 static int ep_remove(struct eventpoll *ep, struct epitem *epi) 608 { 609 unsigned long flags; 610 struct file *file = epi->ffd.file; 611 612 /* 613 * Removes poll wait queue hooks. We _have_ to do this without holding 614 * the "ep->lock" otherwise a deadlock might occur. This because of the 615 * sequence of the lock acquisition. Here we do "ep->lock" then the wait 616 * queue head lock when unregistering the wait queue. The wakeup callback 617 * will run by holding the wait queue head lock and will call our callback 618 * that will try to get "ep->lock". 619 */ 620 ep_unregister_pollwait(ep, epi); 621 622 /* Remove the current item from the list of epoll hooks */ 623 spin_lock(&file->f_lock); 624 if (ep_is_linked(&epi->fllink)) 625 list_del_init(&epi->fllink); 626 spin_unlock(&file->f_lock); 627 628 rb_erase(&epi->rbn, &ep->rbr); 629 630 spin_lock_irqsave(&ep->lock, flags); 631 if (ep_is_linked(&epi->rdllink)) 632 list_del_init(&epi->rdllink); 633 spin_unlock_irqrestore(&ep->lock, flags); 634 635 /* At this point it is safe to free the eventpoll item */ 636 kmem_cache_free(epi_cache, epi); 637 638 atomic_long_dec(&ep->user->epoll_watches); 639 640 return 0; 641 } 642 643 static void ep_free(struct eventpoll *ep) 644 { 645 struct rb_node *rbp; 646 struct epitem *epi; 647 648 /* We need to release all tasks waiting for these file */ 649 if (waitqueue_active(&ep->poll_wait)) 650 ep_poll_safewake(&ep->poll_wait); 651 652 /* 653 * We need to lock this because we could be hit by 654 * eventpoll_release_file() while we're freeing the "struct eventpoll". 655 * We do not need to hold "ep->mtx" here because the epoll file 656 * is on the way to be removed and no one has references to it 657 * anymore. The only hit might come from eventpoll_release_file() but 658 * holding "epmutex" is sufficient here. 659 */ 660 mutex_lock(&epmutex); 661 662 /* 663 * Walks through the whole tree by unregistering poll callbacks. 664 */ 665 for (rbp = rb_first(&ep->rbr); rbp; rbp = rb_next(rbp)) { 666 epi = rb_entry(rbp, struct epitem, rbn); 667 668 ep_unregister_pollwait(ep, epi); 669 } 670 671 /* 672 * Walks through the whole tree by freeing each "struct epitem". At this 673 * point we are sure no poll callbacks will be lingering around, and also by 674 * holding "epmutex" we can be sure that no file cleanup code will hit 675 * us during this operation. So we can avoid the lock on "ep->lock". 676 */ 677 while ((rbp = rb_first(&ep->rbr)) != NULL) { 678 epi = rb_entry(rbp, struct epitem, rbn); 679 ep_remove(ep, epi); 680 } 681 682 mutex_unlock(&epmutex); 683 mutex_destroy(&ep->mtx); 684 free_uid(ep->user); 685 kfree(ep); 686 } 687 688 static int ep_eventpoll_release(struct inode *inode, struct file *file) 689 { 690 struct eventpoll *ep = file->private_data; 691 692 if (ep) 693 ep_free(ep); 694 695 return 0; 696 } 697 698 static int ep_read_events_proc(struct eventpoll *ep, struct list_head *head, 699 void *priv) 700 { 701 struct epitem *epi, *tmp; 702 703 list_for_each_entry_safe(epi, tmp, head, rdllink) { 704 if (epi->ffd.file->f_op->poll(epi->ffd.file, NULL) & 705 epi->event.events) 706 return POLLIN | POLLRDNORM; 707 else { 708 /* 709 * Item has been dropped into the ready list by the poll 710 * callback, but it's not actually ready, as far as 711 * caller requested events goes. We can remove it here. 712 */ 713 list_del_init(&epi->rdllink); 714 } 715 } 716 717 return 0; 718 } 719 720 static int ep_poll_readyevents_proc(void *priv, void *cookie, int call_nests) 721 { 722 return ep_scan_ready_list(priv, ep_read_events_proc, NULL, call_nests + 1); 723 } 724 725 static unsigned int ep_eventpoll_poll(struct file *file, poll_table *wait) 726 { 727 int pollflags; 728 struct eventpoll *ep = file->private_data; 729 730 /* Insert inside our poll wait queue */ 731 poll_wait(file, &ep->poll_wait, wait); 732 733 /* 734 * Proceed to find out if wanted events are really available inside 735 * the ready list. This need to be done under ep_call_nested() 736 * supervision, since the call to f_op->poll() done on listed files 737 * could re-enter here. 738 */ 739 pollflags = ep_call_nested(&poll_readywalk_ncalls, EP_MAX_NESTS, 740 ep_poll_readyevents_proc, ep, ep, current); 741 742 return pollflags != -1 ? pollflags : 0; 743 } 744 745 /* File callbacks that implement the eventpoll file behaviour */ 746 static const struct file_operations eventpoll_fops = { 747 .release = ep_eventpoll_release, 748 .poll = ep_eventpoll_poll, 749 .llseek = noop_llseek, 750 }; 751 752 /* 753 * This is called from eventpoll_release() to unlink files from the eventpoll 754 * interface. We need to have this facility to cleanup correctly files that are 755 * closed without being removed from the eventpoll interface. 756 */ 757 void eventpoll_release_file(struct file *file) 758 { 759 struct list_head *lsthead = &file->f_ep_links; 760 struct eventpoll *ep; 761 struct epitem *epi; 762 763 /* 764 * We don't want to get "file->f_lock" because it is not 765 * necessary. It is not necessary because we're in the "struct file" 766 * cleanup path, and this means that no one is using this file anymore. 767 * So, for example, epoll_ctl() cannot hit here since if we reach this 768 * point, the file counter already went to zero and fget() would fail. 769 * The only hit might come from ep_free() but by holding the mutex 770 * will correctly serialize the operation. We do need to acquire 771 * "ep->mtx" after "epmutex" because ep_remove() requires it when called 772 * from anywhere but ep_free(). 773 * 774 * Besides, ep_remove() acquires the lock, so we can't hold it here. 775 */ 776 mutex_lock(&epmutex); 777 778 while (!list_empty(lsthead)) { 779 epi = list_first_entry(lsthead, struct epitem, fllink); 780 781 ep = epi->ep; 782 list_del_init(&epi->fllink); 783 mutex_lock_nested(&ep->mtx, 0); 784 ep_remove(ep, epi); 785 mutex_unlock(&ep->mtx); 786 } 787 788 mutex_unlock(&epmutex); 789 } 790 791 static int ep_alloc(struct eventpoll **pep) 792 { 793 int error; 794 struct user_struct *user; 795 struct eventpoll *ep; 796 797 user = get_current_user(); 798 error = -ENOMEM; 799 ep = kzalloc(sizeof(*ep), GFP_KERNEL); 800 if (unlikely(!ep)) 801 goto free_uid; 802 803 spin_lock_init(&ep->lock); 804 mutex_init(&ep->mtx); 805 init_waitqueue_head(&ep->wq); 806 init_waitqueue_head(&ep->poll_wait); 807 INIT_LIST_HEAD(&ep->rdllist); 808 ep->rbr = RB_ROOT; 809 ep->ovflist = EP_UNACTIVE_PTR; 810 ep->user = user; 811 812 *pep = ep; 813 814 return 0; 815 816 free_uid: 817 free_uid(user); 818 return error; 819 } 820 821 /* 822 * Search the file inside the eventpoll tree. The RB tree operations 823 * are protected by the "mtx" mutex, and ep_find() must be called with 824 * "mtx" held. 825 */ 826 static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd) 827 { 828 int kcmp; 829 struct rb_node *rbp; 830 struct epitem *epi, *epir = NULL; 831 struct epoll_filefd ffd; 832 833 ep_set_ffd(&ffd, file, fd); 834 for (rbp = ep->rbr.rb_node; rbp; ) { 835 epi = rb_entry(rbp, struct epitem, rbn); 836 kcmp = ep_cmp_ffd(&ffd, &epi->ffd); 837 if (kcmp > 0) 838 rbp = rbp->rb_right; 839 else if (kcmp < 0) 840 rbp = rbp->rb_left; 841 else { 842 epir = epi; 843 break; 844 } 845 } 846 847 return epir; 848 } 849 850 /* 851 * This is the callback that is passed to the wait queue wakeup 852 * mechanism. It is called by the stored file descriptors when they 853 * have events to report. 854 */ 855 static int ep_poll_callback(wait_queue_t *wait, unsigned mode, int sync, void *key) 856 { 857 int pwake = 0; 858 unsigned long flags; 859 struct epitem *epi = ep_item_from_wait(wait); 860 struct eventpoll *ep = epi->ep; 861 862 if ((unsigned long)key & POLLFREE) { 863 ep_pwq_from_wait(wait)->whead = NULL; 864 /* 865 * whead = NULL above can race with ep_remove_wait_queue() 866 * which can do another remove_wait_queue() after us, so we 867 * can't use __remove_wait_queue(). whead->lock is held by 868 * the caller. 869 */ 870 list_del_init(&wait->task_list); 871 } 872 873 spin_lock_irqsave(&ep->lock, flags); 874 875 /* 876 * If the event mask does not contain any poll(2) event, we consider the 877 * descriptor to be disabled. This condition is likely the effect of the 878 * EPOLLONESHOT bit that disables the descriptor when an event is received, 879 * until the next EPOLL_CTL_MOD will be issued. 880 */ 881 if (!(epi->event.events & ~EP_PRIVATE_BITS)) 882 goto out_unlock; 883 884 /* 885 * Check the events coming with the callback. At this stage, not 886 * every device reports the events in the "key" parameter of the 887 * callback. We need to be able to handle both cases here, hence the 888 * test for "key" != NULL before the event match test. 889 */ 890 if (key && !((unsigned long) key & epi->event.events)) 891 goto out_unlock; 892 893 /* 894 * If we are transferring events to userspace, we can hold no locks 895 * (because we're accessing user memory, and because of linux f_op->poll() 896 * semantics). All the events that happen during that period of time are 897 * chained in ep->ovflist and requeued later on. 898 */ 899 if (unlikely(ep->ovflist != EP_UNACTIVE_PTR)) { 900 if (epi->next == EP_UNACTIVE_PTR) { 901 epi->next = ep->ovflist; 902 ep->ovflist = epi; 903 } 904 goto out_unlock; 905 } 906 907 /* If this file is already in the ready list we exit soon */ 908 if (!ep_is_linked(&epi->rdllink)) 909 list_add_tail(&epi->rdllink, &ep->rdllist); 910 911 /* 912 * Wake up ( if active ) both the eventpoll wait list and the ->poll() 913 * wait list. 914 */ 915 if (waitqueue_active(&ep->wq)) 916 wake_up_locked(&ep->wq); 917 if (waitqueue_active(&ep->poll_wait)) 918 pwake++; 919 920 out_unlock: 921 spin_unlock_irqrestore(&ep->lock, flags); 922 923 /* We have to call this outside the lock */ 924 if (pwake) 925 ep_poll_safewake(&ep->poll_wait); 926 927 return 1; 928 } 929 930 /* 931 * This is the callback that is used to add our wait queue to the 932 * target file wakeup lists. 933 */ 934 static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead, 935 poll_table *pt) 936 { 937 struct epitem *epi = ep_item_from_epqueue(pt); 938 struct eppoll_entry *pwq; 939 940 if (epi->nwait >= 0 && (pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL))) { 941 init_waitqueue_func_entry(&pwq->wait, ep_poll_callback); 942 pwq->whead = whead; 943 pwq->base = epi; 944 add_wait_queue(whead, &pwq->wait); 945 list_add_tail(&pwq->llink, &epi->pwqlist); 946 epi->nwait++; 947 } else { 948 /* We have to signal that an error occurred */ 949 epi->nwait = -1; 950 } 951 } 952 953 static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi) 954 { 955 int kcmp; 956 struct rb_node **p = &ep->rbr.rb_node, *parent = NULL; 957 struct epitem *epic; 958 959 while (*p) { 960 parent = *p; 961 epic = rb_entry(parent, struct epitem, rbn); 962 kcmp = ep_cmp_ffd(&epi->ffd, &epic->ffd); 963 if (kcmp > 0) 964 p = &parent->rb_right; 965 else 966 p = &parent->rb_left; 967 } 968 rb_link_node(&epi->rbn, parent, p); 969 rb_insert_color(&epi->rbn, &ep->rbr); 970 } 971 972 973 974 #define PATH_ARR_SIZE 5 975 /* 976 * These are the number paths of length 1 to 5, that we are allowing to emanate 977 * from a single file of interest. For example, we allow 1000 paths of length 978 * 1, to emanate from each file of interest. This essentially represents the 979 * potential wakeup paths, which need to be limited in order to avoid massive 980 * uncontrolled wakeup storms. The common use case should be a single ep which 981 * is connected to n file sources. In this case each file source has 1 path 982 * of length 1. Thus, the numbers below should be more than sufficient. These 983 * path limits are enforced during an EPOLL_CTL_ADD operation, since a modify 984 * and delete can't add additional paths. Protected by the epmutex. 985 */ 986 static const int path_limits[PATH_ARR_SIZE] = { 1000, 500, 100, 50, 10 }; 987 static int path_count[PATH_ARR_SIZE]; 988 989 static int path_count_inc(int nests) 990 { 991 if (++path_count[nests] > path_limits[nests]) 992 return -1; 993 return 0; 994 } 995 996 static void path_count_init(void) 997 { 998 int i; 999 1000 for (i = 0; i < PATH_ARR_SIZE; i++) 1001 path_count[i] = 0; 1002 } 1003 1004 static int reverse_path_check_proc(void *priv, void *cookie, int call_nests) 1005 { 1006 int error = 0; 1007 struct file *file = priv; 1008 struct file *child_file; 1009 struct epitem *epi; 1010 1011 list_for_each_entry(epi, &file->f_ep_links, fllink) { 1012 child_file = epi->ep->file; 1013 if (is_file_epoll(child_file)) { 1014 if (list_empty(&child_file->f_ep_links)) { 1015 if (path_count_inc(call_nests)) { 1016 error = -1; 1017 break; 1018 } 1019 } else { 1020 error = ep_call_nested(&poll_loop_ncalls, 1021 EP_MAX_NESTS, 1022 reverse_path_check_proc, 1023 child_file, child_file, 1024 current); 1025 } 1026 if (error != 0) 1027 break; 1028 } else { 1029 printk(KERN_ERR "reverse_path_check_proc: " 1030 "file is not an ep!\n"); 1031 } 1032 } 1033 return error; 1034 } 1035 1036 /** 1037 * reverse_path_check - The tfile_check_list is list of file *, which have 1038 * links that are proposed to be newly added. We need to 1039 * make sure that those added links don't add too many 1040 * paths such that we will spend all our time waking up 1041 * eventpoll objects. 1042 * 1043 * Returns: Returns zero if the proposed links don't create too many paths, 1044 * -1 otherwise. 1045 */ 1046 static int reverse_path_check(void) 1047 { 1048 int length = 0; 1049 int error = 0; 1050 struct file *current_file; 1051 1052 /* let's call this for all tfiles */ 1053 list_for_each_entry(current_file, &tfile_check_list, f_tfile_llink) { 1054 length++; 1055 path_count_init(); 1056 error = ep_call_nested(&poll_loop_ncalls, EP_MAX_NESTS, 1057 reverse_path_check_proc, current_file, 1058 current_file, current); 1059 if (error) 1060 break; 1061 } 1062 return error; 1063 } 1064 1065 /* 1066 * Must be called with "mtx" held. 1067 */ 1068 static int ep_insert(struct eventpoll *ep, struct epoll_event *event, 1069 struct file *tfile, int fd) 1070 { 1071 int error, revents, pwake = 0; 1072 unsigned long flags; 1073 long user_watches; 1074 struct epitem *epi; 1075 struct ep_pqueue epq; 1076 1077 user_watches = atomic_long_read(&ep->user->epoll_watches); 1078 if (unlikely(user_watches >= max_user_watches)) 1079 return -ENOSPC; 1080 if (!(epi = kmem_cache_alloc(epi_cache, GFP_KERNEL))) 1081 return -ENOMEM; 1082 1083 /* Item initialization follow here ... */ 1084 INIT_LIST_HEAD(&epi->rdllink); 1085 INIT_LIST_HEAD(&epi->fllink); 1086 INIT_LIST_HEAD(&epi->pwqlist); 1087 epi->ep = ep; 1088 ep_set_ffd(&epi->ffd, tfile, fd); 1089 epi->event = *event; 1090 epi->nwait = 0; 1091 epi->next = EP_UNACTIVE_PTR; 1092 1093 /* Initialize the poll table using the queue callback */ 1094 epq.epi = epi; 1095 init_poll_funcptr(&epq.pt, ep_ptable_queue_proc); 1096 1097 /* 1098 * Attach the item to the poll hooks and get current event bits. 1099 * We can safely use the file* here because its usage count has 1100 * been increased by the caller of this function. Note that after 1101 * this operation completes, the poll callback can start hitting 1102 * the new item. 1103 */ 1104 revents = tfile->f_op->poll(tfile, &epq.pt); 1105 1106 /* 1107 * We have to check if something went wrong during the poll wait queue 1108 * install process. Namely an allocation for a wait queue failed due 1109 * high memory pressure. 1110 */ 1111 error = -ENOMEM; 1112 if (epi->nwait < 0) 1113 goto error_unregister; 1114 1115 /* Add the current item to the list of active epoll hook for this file */ 1116 spin_lock(&tfile->f_lock); 1117 list_add_tail(&epi->fllink, &tfile->f_ep_links); 1118 spin_unlock(&tfile->f_lock); 1119 1120 /* 1121 * Add the current item to the RB tree. All RB tree operations are 1122 * protected by "mtx", and ep_insert() is called with "mtx" held. 1123 */ 1124 ep_rbtree_insert(ep, epi); 1125 1126 /* now check if we've created too many backpaths */ 1127 error = -EINVAL; 1128 if (reverse_path_check()) 1129 goto error_remove_epi; 1130 1131 /* We have to drop the new item inside our item list to keep track of it */ 1132 spin_lock_irqsave(&ep->lock, flags); 1133 1134 /* If the file is already "ready" we drop it inside the ready list */ 1135 if ((revents & event->events) && !ep_is_linked(&epi->rdllink)) { 1136 list_add_tail(&epi->rdllink, &ep->rdllist); 1137 1138 /* Notify waiting tasks that events are available */ 1139 if (waitqueue_active(&ep->wq)) 1140 wake_up_locked(&ep->wq); 1141 if (waitqueue_active(&ep->poll_wait)) 1142 pwake++; 1143 } 1144 1145 spin_unlock_irqrestore(&ep->lock, flags); 1146 1147 atomic_long_inc(&ep->user->epoll_watches); 1148 1149 /* We have to call this outside the lock */ 1150 if (pwake) 1151 ep_poll_safewake(&ep->poll_wait); 1152 1153 return 0; 1154 1155 error_remove_epi: 1156 spin_lock(&tfile->f_lock); 1157 if (ep_is_linked(&epi->fllink)) 1158 list_del_init(&epi->fllink); 1159 spin_unlock(&tfile->f_lock); 1160 1161 rb_erase(&epi->rbn, &ep->rbr); 1162 1163 error_unregister: 1164 ep_unregister_pollwait(ep, epi); 1165 1166 /* 1167 * We need to do this because an event could have been arrived on some 1168 * allocated wait queue. Note that we don't care about the ep->ovflist 1169 * list, since that is used/cleaned only inside a section bound by "mtx". 1170 * And ep_insert() is called with "mtx" held. 1171 */ 1172 spin_lock_irqsave(&ep->lock, flags); 1173 if (ep_is_linked(&epi->rdllink)) 1174 list_del_init(&epi->rdllink); 1175 spin_unlock_irqrestore(&ep->lock, flags); 1176 1177 kmem_cache_free(epi_cache, epi); 1178 1179 return error; 1180 } 1181 1182 /* 1183 * Modify the interest event mask by dropping an event if the new mask 1184 * has a match in the current file status. Must be called with "mtx" held. 1185 */ 1186 static int ep_modify(struct eventpoll *ep, struct epitem *epi, struct epoll_event *event) 1187 { 1188 int pwake = 0; 1189 unsigned int revents; 1190 1191 /* 1192 * Set the new event interest mask before calling f_op->poll(); 1193 * otherwise we might miss an event that happens between the 1194 * f_op->poll() call and the new event set registering. 1195 */ 1196 epi->event.events = event->events; 1197 epi->event.data = event->data; /* protected by mtx */ 1198 1199 /* 1200 * Get current event bits. We can safely use the file* here because 1201 * its usage count has been increased by the caller of this function. 1202 */ 1203 revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL); 1204 1205 /* 1206 * If the item is "hot" and it is not registered inside the ready 1207 * list, push it inside. 1208 */ 1209 if (revents & event->events) { 1210 spin_lock_irq(&ep->lock); 1211 if (!ep_is_linked(&epi->rdllink)) { 1212 list_add_tail(&epi->rdllink, &ep->rdllist); 1213 1214 /* Notify waiting tasks that events are available */ 1215 if (waitqueue_active(&ep->wq)) 1216 wake_up_locked(&ep->wq); 1217 if (waitqueue_active(&ep->poll_wait)) 1218 pwake++; 1219 } 1220 spin_unlock_irq(&ep->lock); 1221 } 1222 1223 /* We have to call this outside the lock */ 1224 if (pwake) 1225 ep_poll_safewake(&ep->poll_wait); 1226 1227 return 0; 1228 } 1229 1230 static int ep_send_events_proc(struct eventpoll *ep, struct list_head *head, 1231 void *priv) 1232 { 1233 struct ep_send_events_data *esed = priv; 1234 int eventcnt; 1235 unsigned int revents; 1236 struct epitem *epi; 1237 struct epoll_event __user *uevent; 1238 1239 /* 1240 * We can loop without lock because we are passed a task private list. 1241 * Items cannot vanish during the loop because ep_scan_ready_list() is 1242 * holding "mtx" during this call. 1243 */ 1244 for (eventcnt = 0, uevent = esed->events; 1245 !list_empty(head) && eventcnt < esed->maxevents;) { 1246 epi = list_first_entry(head, struct epitem, rdllink); 1247 1248 list_del_init(&epi->rdllink); 1249 1250 revents = epi->ffd.file->f_op->poll(epi->ffd.file, NULL) & 1251 epi->event.events; 1252 1253 /* 1254 * If the event mask intersect the caller-requested one, 1255 * deliver the event to userspace. Again, ep_scan_ready_list() 1256 * is holding "mtx", so no operations coming from userspace 1257 * can change the item. 1258 */ 1259 if (revents) { 1260 if (__put_user(revents, &uevent->events) || 1261 __put_user(epi->event.data, &uevent->data)) { 1262 list_add(&epi->rdllink, head); 1263 return eventcnt ? eventcnt : -EFAULT; 1264 } 1265 eventcnt++; 1266 uevent++; 1267 if (epi->event.events & EPOLLONESHOT) 1268 epi->event.events &= EP_PRIVATE_BITS; 1269 else if (!(epi->event.events & EPOLLET)) { 1270 /* 1271 * If this file has been added with Level 1272 * Trigger mode, we need to insert back inside 1273 * the ready list, so that the next call to 1274 * epoll_wait() will check again the events 1275 * availability. At this point, no one can insert 1276 * into ep->rdllist besides us. The epoll_ctl() 1277 * callers are locked out by 1278 * ep_scan_ready_list() holding "mtx" and the 1279 * poll callback will queue them in ep->ovflist. 1280 */ 1281 list_add_tail(&epi->rdllink, &ep->rdllist); 1282 } 1283 } 1284 } 1285 1286 return eventcnt; 1287 } 1288 1289 static int ep_send_events(struct eventpoll *ep, 1290 struct epoll_event __user *events, int maxevents) 1291 { 1292 struct ep_send_events_data esed; 1293 1294 esed.maxevents = maxevents; 1295 esed.events = events; 1296 1297 return ep_scan_ready_list(ep, ep_send_events_proc, &esed, 0); 1298 } 1299 1300 static inline struct timespec ep_set_mstimeout(long ms) 1301 { 1302 struct timespec now, ts = { 1303 .tv_sec = ms / MSEC_PER_SEC, 1304 .tv_nsec = NSEC_PER_MSEC * (ms % MSEC_PER_SEC), 1305 }; 1306 1307 ktime_get_ts(&now); 1308 return timespec_add_safe(now, ts); 1309 } 1310 1311 /** 1312 * ep_poll - Retrieves ready events, and delivers them to the caller supplied 1313 * event buffer. 1314 * 1315 * @ep: Pointer to the eventpoll context. 1316 * @events: Pointer to the userspace buffer where the ready events should be 1317 * stored. 1318 * @maxevents: Size (in terms of number of events) of the caller event buffer. 1319 * @timeout: Maximum timeout for the ready events fetch operation, in 1320 * milliseconds. If the @timeout is zero, the function will not block, 1321 * while if the @timeout is less than zero, the function will block 1322 * until at least one event has been retrieved (or an error 1323 * occurred). 1324 * 1325 * Returns: Returns the number of ready events which have been fetched, or an 1326 * error code, in case of error. 1327 */ 1328 static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, 1329 int maxevents, long timeout) 1330 { 1331 int res = 0, eavail, timed_out = 0; 1332 unsigned long flags; 1333 long slack = 0; 1334 wait_queue_t wait; 1335 ktime_t expires, *to = NULL; 1336 1337 if (timeout > 0) { 1338 struct timespec end_time = ep_set_mstimeout(timeout); 1339 1340 slack = select_estimate_accuracy(&end_time); 1341 to = &expires; 1342 *to = timespec_to_ktime(end_time); 1343 } else if (timeout == 0) { 1344 /* 1345 * Avoid the unnecessary trip to the wait queue loop, if the 1346 * caller specified a non blocking operation. 1347 */ 1348 timed_out = 1; 1349 spin_lock_irqsave(&ep->lock, flags); 1350 goto check_events; 1351 } 1352 1353 fetch_events: 1354 spin_lock_irqsave(&ep->lock, flags); 1355 1356 if (!ep_events_available(ep)) { 1357 /* 1358 * We don't have any available event to return to the caller. 1359 * We need to sleep here, and we will be wake up by 1360 * ep_poll_callback() when events will become available. 1361 */ 1362 init_waitqueue_entry(&wait, current); 1363 __add_wait_queue_exclusive(&ep->wq, &wait); 1364 1365 for (;;) { 1366 /* 1367 * We don't want to sleep if the ep_poll_callback() sends us 1368 * a wakeup in between. That's why we set the task state 1369 * to TASK_INTERRUPTIBLE before doing the checks. 1370 */ 1371 set_current_state(TASK_INTERRUPTIBLE); 1372 if (ep_events_available(ep) || timed_out) 1373 break; 1374 if (signal_pending(current)) { 1375 res = -EINTR; 1376 break; 1377 } 1378 1379 spin_unlock_irqrestore(&ep->lock, flags); 1380 if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS)) 1381 timed_out = 1; 1382 1383 spin_lock_irqsave(&ep->lock, flags); 1384 } 1385 __remove_wait_queue(&ep->wq, &wait); 1386 1387 set_current_state(TASK_RUNNING); 1388 } 1389 check_events: 1390 /* Is it worth to try to dig for events ? */ 1391 eavail = ep_events_available(ep); 1392 1393 spin_unlock_irqrestore(&ep->lock, flags); 1394 1395 /* 1396 * Try to transfer events to user space. In case we get 0 events and 1397 * there's still timeout left over, we go trying again in search of 1398 * more luck. 1399 */ 1400 if (!res && eavail && 1401 !(res = ep_send_events(ep, events, maxevents)) && !timed_out) 1402 goto fetch_events; 1403 1404 return res; 1405 } 1406 1407 /** 1408 * ep_loop_check_proc - Callback function to be passed to the @ep_call_nested() 1409 * API, to verify that adding an epoll file inside another 1410 * epoll structure, does not violate the constraints, in 1411 * terms of closed loops, or too deep chains (which can 1412 * result in excessive stack usage). 1413 * 1414 * @priv: Pointer to the epoll file to be currently checked. 1415 * @cookie: Original cookie for this call. This is the top-of-the-chain epoll 1416 * data structure pointer. 1417 * @call_nests: Current dept of the @ep_call_nested() call stack. 1418 * 1419 * Returns: Returns zero if adding the epoll @file inside current epoll 1420 * structure @ep does not violate the constraints, or -1 otherwise. 1421 */ 1422 static int ep_loop_check_proc(void *priv, void *cookie, int call_nests) 1423 { 1424 int error = 0; 1425 struct file *file = priv; 1426 struct eventpoll *ep = file->private_data; 1427 struct eventpoll *ep_tovisit; 1428 struct rb_node *rbp; 1429 struct epitem *epi; 1430 1431 mutex_lock_nested(&ep->mtx, call_nests + 1); 1432 ep->visited = 1; 1433 list_add(&ep->visited_list_link, &visited_list); 1434 for (rbp = rb_first(&ep->rbr); rbp; rbp = rb_next(rbp)) { 1435 epi = rb_entry(rbp, struct epitem, rbn); 1436 if (unlikely(is_file_epoll(epi->ffd.file))) { 1437 ep_tovisit = epi->ffd.file->private_data; 1438 if (ep_tovisit->visited) 1439 continue; 1440 error = ep_call_nested(&poll_loop_ncalls, EP_MAX_NESTS, 1441 ep_loop_check_proc, epi->ffd.file, 1442 ep_tovisit, current); 1443 if (error != 0) 1444 break; 1445 } else { 1446 /* 1447 * If we've reached a file that is not associated with 1448 * an ep, then we need to check if the newly added 1449 * links are going to add too many wakeup paths. We do 1450 * this by adding it to the tfile_check_list, if it's 1451 * not already there, and calling reverse_path_check() 1452 * during ep_insert(). 1453 */ 1454 if (list_empty(&epi->ffd.file->f_tfile_llink)) 1455 list_add(&epi->ffd.file->f_tfile_llink, 1456 &tfile_check_list); 1457 } 1458 } 1459 mutex_unlock(&ep->mtx); 1460 1461 return error; 1462 } 1463 1464 /** 1465 * ep_loop_check - Performs a check to verify that adding an epoll file (@file) 1466 * another epoll file (represented by @ep) does not create 1467 * closed loops or too deep chains. 1468 * 1469 * @ep: Pointer to the epoll private data structure. 1470 * @file: Pointer to the epoll file to be checked. 1471 * 1472 * Returns: Returns zero if adding the epoll @file inside current epoll 1473 * structure @ep does not violate the constraints, or -1 otherwise. 1474 */ 1475 static int ep_loop_check(struct eventpoll *ep, struct file *file) 1476 { 1477 int ret; 1478 struct eventpoll *ep_cur, *ep_next; 1479 1480 ret = ep_call_nested(&poll_loop_ncalls, EP_MAX_NESTS, 1481 ep_loop_check_proc, file, ep, current); 1482 /* clear visited list */ 1483 list_for_each_entry_safe(ep_cur, ep_next, &visited_list, 1484 visited_list_link) { 1485 ep_cur->visited = 0; 1486 list_del(&ep_cur->visited_list_link); 1487 } 1488 return ret; 1489 } 1490 1491 static void clear_tfile_check_list(void) 1492 { 1493 struct file *file; 1494 1495 /* first clear the tfile_check_list */ 1496 while (!list_empty(&tfile_check_list)) { 1497 file = list_first_entry(&tfile_check_list, struct file, 1498 f_tfile_llink); 1499 list_del_init(&file->f_tfile_llink); 1500 } 1501 INIT_LIST_HEAD(&tfile_check_list); 1502 } 1503 1504 /* 1505 * Open an eventpoll file descriptor. 1506 */ 1507 SYSCALL_DEFINE1(epoll_create1, int, flags) 1508 { 1509 int error, fd; 1510 struct eventpoll *ep = NULL; 1511 struct file *file; 1512 1513 /* Check the EPOLL_* constant for consistency. */ 1514 BUILD_BUG_ON(EPOLL_CLOEXEC != O_CLOEXEC); 1515 1516 if (flags & ~EPOLL_CLOEXEC) 1517 return -EINVAL; 1518 /* 1519 * Create the internal data structure ("struct eventpoll"). 1520 */ 1521 error = ep_alloc(&ep); 1522 if (error < 0) 1523 return error; 1524 /* 1525 * Creates all the items needed to setup an eventpoll file. That is, 1526 * a file structure and a free file descriptor. 1527 */ 1528 fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC)); 1529 if (fd < 0) { 1530 error = fd; 1531 goto out_free_ep; 1532 } 1533 file = anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep, 1534 O_RDWR | (flags & O_CLOEXEC)); 1535 if (IS_ERR(file)) { 1536 error = PTR_ERR(file); 1537 goto out_free_fd; 1538 } 1539 fd_install(fd, file); 1540 ep->file = file; 1541 return fd; 1542 1543 out_free_fd: 1544 put_unused_fd(fd); 1545 out_free_ep: 1546 ep_free(ep); 1547 return error; 1548 } 1549 1550 SYSCALL_DEFINE1(epoll_create, int, size) 1551 { 1552 if (size <= 0) 1553 return -EINVAL; 1554 1555 return sys_epoll_create1(0); 1556 } 1557 1558 /* 1559 * The following function implements the controller interface for 1560 * the eventpoll file that enables the insertion/removal/change of 1561 * file descriptors inside the interest set. 1562 */ 1563 SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd, 1564 struct epoll_event __user *, event) 1565 { 1566 int error; 1567 int did_lock_epmutex = 0; 1568 struct file *file, *tfile; 1569 struct eventpoll *ep; 1570 struct epitem *epi; 1571 struct epoll_event epds; 1572 1573 error = -EFAULT; 1574 if (ep_op_has_event(op) && 1575 copy_from_user(&epds, event, sizeof(struct epoll_event))) 1576 goto error_return; 1577 1578 /* Get the "struct file *" for the eventpoll file */ 1579 error = -EBADF; 1580 file = fget(epfd); 1581 if (!file) 1582 goto error_return; 1583 1584 /* Get the "struct file *" for the target file */ 1585 tfile = fget(fd); 1586 if (!tfile) 1587 goto error_fput; 1588 1589 /* The target file descriptor must support poll */ 1590 error = -EPERM; 1591 if (!tfile->f_op || !tfile->f_op->poll) 1592 goto error_tgt_fput; 1593 1594 /* 1595 * We have to check that the file structure underneath the file descriptor 1596 * the user passed to us _is_ an eventpoll file. And also we do not permit 1597 * adding an epoll file descriptor inside itself. 1598 */ 1599 error = -EINVAL; 1600 if (file == tfile || !is_file_epoll(file)) 1601 goto error_tgt_fput; 1602 1603 /* 1604 * At this point it is safe to assume that the "private_data" contains 1605 * our own data structure. 1606 */ 1607 ep = file->private_data; 1608 1609 /* 1610 * When we insert an epoll file descriptor, inside another epoll file 1611 * descriptor, there is the change of creating closed loops, which are 1612 * better be handled here, than in more critical paths. While we are 1613 * checking for loops we also determine the list of files reachable 1614 * and hang them on the tfile_check_list, so we can check that we 1615 * haven't created too many possible wakeup paths. 1616 * 1617 * We need to hold the epmutex across both ep_insert and ep_remove 1618 * b/c we want to make sure we are looking at a coherent view of 1619 * epoll network. 1620 */ 1621 if (op == EPOLL_CTL_ADD || op == EPOLL_CTL_DEL) { 1622 mutex_lock(&epmutex); 1623 did_lock_epmutex = 1; 1624 } 1625 if (op == EPOLL_CTL_ADD) { 1626 if (is_file_epoll(tfile)) { 1627 error = -ELOOP; 1628 if (ep_loop_check(ep, tfile) != 0) 1629 goto error_tgt_fput; 1630 } else 1631 list_add(&tfile->f_tfile_llink, &tfile_check_list); 1632 } 1633 1634 mutex_lock_nested(&ep->mtx, 0); 1635 1636 /* 1637 * Try to lookup the file inside our RB tree, Since we grabbed "mtx" 1638 * above, we can be sure to be able to use the item looked up by 1639 * ep_find() till we release the mutex. 1640 */ 1641 epi = ep_find(ep, tfile, fd); 1642 1643 error = -EINVAL; 1644 switch (op) { 1645 case EPOLL_CTL_ADD: 1646 if (!epi) { 1647 epds.events |= POLLERR | POLLHUP; 1648 error = ep_insert(ep, &epds, tfile, fd); 1649 } else 1650 error = -EEXIST; 1651 clear_tfile_check_list(); 1652 break; 1653 case EPOLL_CTL_DEL: 1654 if (epi) 1655 error = ep_remove(ep, epi); 1656 else 1657 error = -ENOENT; 1658 break; 1659 case EPOLL_CTL_MOD: 1660 if (epi) { 1661 epds.events |= POLLERR | POLLHUP; 1662 error = ep_modify(ep, epi, &epds); 1663 } else 1664 error = -ENOENT; 1665 break; 1666 } 1667 mutex_unlock(&ep->mtx); 1668 1669 error_tgt_fput: 1670 if (did_lock_epmutex) 1671 mutex_unlock(&epmutex); 1672 1673 fput(tfile); 1674 error_fput: 1675 fput(file); 1676 error_return: 1677 1678 return error; 1679 } 1680 1681 /* 1682 * Implement the event wait interface for the eventpoll file. It is the kernel 1683 * part of the user space epoll_wait(2). 1684 */ 1685 SYSCALL_DEFINE4(epoll_wait, int, epfd, struct epoll_event __user *, events, 1686 int, maxevents, int, timeout) 1687 { 1688 int error; 1689 struct file *file; 1690 struct eventpoll *ep; 1691 1692 /* The maximum number of event must be greater than zero */ 1693 if (maxevents <= 0 || maxevents > EP_MAX_EVENTS) 1694 return -EINVAL; 1695 1696 /* Verify that the area passed by the user is writeable */ 1697 if (!access_ok(VERIFY_WRITE, events, maxevents * sizeof(struct epoll_event))) { 1698 error = -EFAULT; 1699 goto error_return; 1700 } 1701 1702 /* Get the "struct file *" for the eventpoll file */ 1703 error = -EBADF; 1704 file = fget(epfd); 1705 if (!file) 1706 goto error_return; 1707 1708 /* 1709 * We have to check that the file structure underneath the fd 1710 * the user passed to us _is_ an eventpoll file. 1711 */ 1712 error = -EINVAL; 1713 if (!is_file_epoll(file)) 1714 goto error_fput; 1715 1716 /* 1717 * At this point it is safe to assume that the "private_data" contains 1718 * our own data structure. 1719 */ 1720 ep = file->private_data; 1721 1722 /* Time to fish for events ... */ 1723 error = ep_poll(ep, events, maxevents, timeout); 1724 1725 error_fput: 1726 fput(file); 1727 error_return: 1728 1729 return error; 1730 } 1731 1732 #ifdef HAVE_SET_RESTORE_SIGMASK 1733 1734 /* 1735 * Implement the event wait interface for the eventpoll file. It is the kernel 1736 * part of the user space epoll_pwait(2). 1737 */ 1738 SYSCALL_DEFINE6(epoll_pwait, int, epfd, struct epoll_event __user *, events, 1739 int, maxevents, int, timeout, const sigset_t __user *, sigmask, 1740 size_t, sigsetsize) 1741 { 1742 int error; 1743 sigset_t ksigmask, sigsaved; 1744 1745 /* 1746 * If the caller wants a certain signal mask to be set during the wait, 1747 * we apply it here. 1748 */ 1749 if (sigmask) { 1750 if (sigsetsize != sizeof(sigset_t)) 1751 return -EINVAL; 1752 if (copy_from_user(&ksigmask, sigmask, sizeof(ksigmask))) 1753 return -EFAULT; 1754 sigdelsetmask(&ksigmask, sigmask(SIGKILL) | sigmask(SIGSTOP)); 1755 sigprocmask(SIG_SETMASK, &ksigmask, &sigsaved); 1756 } 1757 1758 error = sys_epoll_wait(epfd, events, maxevents, timeout); 1759 1760 /* 1761 * If we changed the signal mask, we need to restore the original one. 1762 * In case we've got a signal while waiting, we do not restore the 1763 * signal mask yet, and we allow do_signal() to deliver the signal on 1764 * the way back to userspace, before the signal mask is restored. 1765 */ 1766 if (sigmask) { 1767 if (error == -EINTR) { 1768 memcpy(¤t->saved_sigmask, &sigsaved, 1769 sizeof(sigsaved)); 1770 set_restore_sigmask(); 1771 } else 1772 sigprocmask(SIG_SETMASK, &sigsaved, NULL); 1773 } 1774 1775 return error; 1776 } 1777 1778 #endif /* HAVE_SET_RESTORE_SIGMASK */ 1779 1780 static int __init eventpoll_init(void) 1781 { 1782 struct sysinfo si; 1783 1784 si_meminfo(&si); 1785 /* 1786 * Allows top 4% of lomem to be allocated for epoll watches (per user). 1787 */ 1788 max_user_watches = (((si.totalram - si.totalhigh) / 25) << PAGE_SHIFT) / 1789 EP_ITEM_COST; 1790 BUG_ON(max_user_watches < 0); 1791 1792 /* 1793 * Initialize the structure used to perform epoll file descriptor 1794 * inclusion loops checks. 1795 */ 1796 ep_nested_calls_init(&poll_loop_ncalls); 1797 1798 /* Initialize the structure used to perform safe poll wait head wake ups */ 1799 ep_nested_calls_init(&poll_safewake_ncalls); 1800 1801 /* Initialize the structure used to perform file's f_op->poll() calls */ 1802 ep_nested_calls_init(&poll_readywalk_ncalls); 1803 1804 /* Allocates slab cache used to allocate "struct epitem" items */ 1805 epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem), 1806 0, SLAB_HWCACHE_ALIGN | SLAB_PANIC, NULL); 1807 1808 /* Allocates slab cache used to allocate "struct eppoll_entry" */ 1809 pwq_cache = kmem_cache_create("eventpoll_pwq", 1810 sizeof(struct eppoll_entry), 0, SLAB_PANIC, NULL); 1811 1812 return 0; 1813 } 1814 fs_initcall(eventpoll_init); 1815