eventpoll.c

   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 *  fs/eventpoll.c (Efficient event retrieval implementation)
   4 *  Copyright (C) 2001,...,2009	 Davide Libenzi
   5 *
   6 *  Davide Libenzi <davidel@xmailserver.org>
   7 */
   8
   9#include <linux/init.h>
  10#include <linux/kernel.h>
  11#include <linux/sched/signal.h>
  12#include <linux/fs.h>
  13#include <linux/file.h>
  14#include <linux/signal.h>
  15#include <linux/errno.h>
  16#include <linux/mm.h>
  17#include <linux/slab.h>
  18#include <linux/poll.h>
  19#include <linux/string.h>
  20#include <linux/list.h>
  21#include <linux/hash.h>
  22#include <linux/spinlock.h>
  23#include <linux/syscalls.h>
  24#include <linux/rbtree.h>
  25#include <linux/wait.h>
  26#include <linux/eventpoll.h>
  27#include <linux/mount.h>
  28#include <linux/bitops.h>
  29#include <linux/mutex.h>
  30#include <linux/anon_inodes.h>
  31#include <linux/device.h>
  32#include <linux/uaccess.h>
  33#include <asm/io.h>
  34#include <asm/mman.h>
  35#include <linux/atomic.h>
  36#include <linux/proc_fs.h>
  37#include <linux/seq_file.h>
  38#include <linux/compat.h>
  39#include <linux/rculist.h>
  40#include <linux/capability.h>
  41#include <net/busy_poll.h>
  42
  43/*
  44 * LOCKING:
  45 * There are three level of locking required by epoll :
  46 *
  47 * 1) epnested_mutex (mutex)
  48 * 2) ep->mtx (mutex)
  49 * 3) ep->lock (spinlock)
  50 *
  51 * The acquire order is the one listed above, from 1 to 3.
  52 * We need a spinlock (ep->lock) because we manipulate objects
  53 * from inside the poll callback, that might be triggered from
  54 * a wake_up() that in turn might be called from IRQ context.
  55 * So we can't sleep inside the poll callback and hence we need
  56 * a spinlock. During the event transfer loop (from kernel to
  57 * user space) we could end up sleeping due a copy_to_user(), so
  58 * we need a lock that will allow us to sleep. This lock is a
  59 * mutex (ep->mtx). It is acquired during the event transfer loop,
  60 * during epoll_ctl(EPOLL_CTL_DEL) and during eventpoll_release_file().
  61 * The epnested_mutex is acquired when inserting an epoll fd onto another
  62 * epoll fd. We do this so that we walk the epoll tree and ensure that this
  63 * insertion does not create a cycle of epoll file descriptors, which
  64 * could lead to deadlock. We need a global mutex to prevent two
  65 * simultaneous inserts (A into B and B into A) from racing and
  66 * constructing a cycle without either insert observing that it is
  67 * going to.
  68 * It is necessary to acquire multiple "ep->mtx"es at once in the
  69 * case when one epoll fd is added to another. In this case, we
  70 * always acquire the locks in the order of nesting (i.e. after
  71 * epoll_ctl(e1, EPOLL_CTL_ADD, e2), e1->mtx will always be acquired
  72 * before e2->mtx). Since we disallow cycles of epoll file
  73 * descriptors, this ensures that the mutexes are well-ordered. In
  74 * order to communicate this nesting to lockdep, when walking a tree
  75 * of epoll file descriptors, we use the current recursion depth as
  76 * the lockdep subkey.
  77 * It is possible to drop the "ep->mtx" and to use the global
  78 * mutex "epnested_mutex" (together with "ep->lock") to have it working,
  79 * but having "ep->mtx" will make the interface more scalable.
  80 * Events that require holding "epnested_mutex" are very rare, while for
  81 * normal operations the epoll private "ep->mtx" will guarantee
  82 * a better scalability.
  83 */
  84
  85/* Epoll private bits inside the event mask */
  86#define EP_PRIVATE_BITS (EPOLLWAKEUP | EPOLLONESHOT | EPOLLET | EPOLLEXCLUSIVE)
  87
  88#define EPOLLINOUT_BITS (EPOLLIN | EPOLLOUT)
  89
  90#define EPOLLEXCLUSIVE_OK_BITS (EPOLLINOUT_BITS | EPOLLERR | EPOLLHUP | \
  91				EPOLLWAKEUP | EPOLLET | EPOLLEXCLUSIVE)
  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
 102struct epoll_filefd {
 103	struct file *file;
 104	int fd;
 105} __packed;
 106
 107/* Wait structure used by the poll hooks */
 108struct eppoll_entry {
 109	/* List header used to link this structure to the "struct epitem" */
 110	struct eppoll_entry *next;
 111
 112	/* The "base" pointer is set to the container "struct epitem" */
 113	struct epitem *base;
 114
 115	/*
 116	 * Wait queue item that will be linked to the target file wait
 117	 * queue head.
 118	 */
 119	wait_queue_entry_t wait;
 120
 121	/* The wait queue head that linked the "wait" wait queue item */
 122	wait_queue_head_t *whead;
 123};
 124
 125/*
 126 * Each file descriptor added to the eventpoll interface will
 127 * have an entry of this type linked to the "rbr" RB tree.
 128 * Avoid increasing the size of this struct, there can be many thousands
 129 * of these on a server and we do not want this to take another cache line.
 130 */
 131struct epitem {
 132	union {
 133		/* RB tree node links this structure to the eventpoll RB tree */
 134		struct rb_node rbn;
 135		/* Used to free the struct epitem */
 136		struct rcu_head rcu;
 137	};
 138
 139	/* List header used to link this structure to the eventpoll ready list */
 140	struct list_head rdllink;
 141
 142	/*
 143	 * Works together "struct eventpoll"->ovflist in keeping the
 144	 * single linked chain of items.
 145	 */
 146	struct epitem *next;
 147
 148	/* The file descriptor information this item refers to */
 149	struct epoll_filefd ffd;
 150
 151	/*
 152	 * Protected by file->f_lock, true for to-be-released epitem already
 153	 * removed from the "struct file" items list; together with
 154	 * eventpoll->refcount orchestrates "struct eventpoll" disposal
 155	 */
 156	bool dying;
 157
 158	/* List containing poll wait queues */
 159	struct eppoll_entry *pwqlist;
 160
 161	/* The "container" of this item */
 162	struct eventpoll *ep;
 163
 164	/* List header used to link this item to the "struct file" items list */
 165	struct hlist_node fllink;
 166
 167	/* wakeup_source used when EPOLLWAKEUP is set */
 168	struct wakeup_source __rcu *ws;
 169
 170	/* The structure that describe the interested events and the source fd */
 171	struct epoll_event event;
 172};
 173
 174/*
 175 * This structure is stored inside the "private_data" member of the file
 176 * structure and represents the main data structure for the eventpoll
 177 * interface.
 178 */
 179struct eventpoll {
 180	/*
 181	 * This mutex is used to ensure that files are not removed
 182	 * while epoll is using them. This is held during the event
 183	 * collection loop, the file cleanup path, the epoll file exit
 184	 * code and the ctl operations.
 185	 */
 186	struct mutex mtx;
 187
 188	/* Wait queue used by sys_epoll_wait() */
 189	wait_queue_head_t wq;
 190
 191	/* Wait queue used by file->poll() */
 192	wait_queue_head_t poll_wait;
 193
 194	/* List of ready file descriptors */
 195	struct list_head rdllist;
 196
 197	/* Lock which protects rdllist and ovflist */
 198	spinlock_t lock;
 199
 200	/* RB tree root used to store monitored fd structs */
 201	struct rb_root_cached rbr;
 202
 203	/*
 204	 * This is a single linked list that chains all the "struct epitem" that
 205	 * happened while transferring ready events to userspace w/out
 206	 * holding ->lock.
 207	 */
 208	struct epitem *ovflist;
 209
 210	/* wakeup_source used when ep_send_events or __ep_eventpoll_poll is running */
 211	struct wakeup_source *ws;
 212
 213	/* The user that created the eventpoll descriptor */
 214	struct user_struct *user;
 215
 216	struct file *file;
 217
 218	/* used to optimize loop detection check */
 219	u64 gen;
 220	struct hlist_head refs;
 221	u8 loop_check_depth;
 222
 223	/*
 224	 * usage count, used together with epitem->dying to
 225	 * orchestrate the disposal of this struct
 226	 */
 227	refcount_t refcount;
 228
 229	/* used to defer freeing past ep_get_upwards_depth_proc() RCU walk */
 230	struct rcu_head rcu;
 231
 232#ifdef CONFIG_NET_RX_BUSY_POLL
 233	/* used to track busy poll napi_id */
 234	unsigned int napi_id;
 235	/* busy poll timeout */
 236	u32 busy_poll_usecs;
 237	/* busy poll packet budget */
 238	u16 busy_poll_budget;
 239	bool prefer_busy_poll;
 240#endif
 241
 242#ifdef CONFIG_DEBUG_LOCK_ALLOC
 243	/* tracks wakeup nests for lockdep validation */
 244	u8 nests;
 245#endif
 246};
 247
 248/* Wrapper struct used by poll queueing */
 249struct ep_pqueue {
 250	poll_table pt;
 251	struct epitem *epi;
 252};
 253
 254/*
 255 * Configuration options available inside /proc/sys/fs/epoll/
 256 */
 257/* Maximum number of epoll watched descriptors, per user */
 258static long max_user_watches __read_mostly;
 259
 260/* Used for cycles detection */
 261static DEFINE_MUTEX(epnested_mutex);
 262
 263static u64 loop_check_gen = 0;
 264
 265/* Used to check for epoll file descriptor inclusion loops */
 266static struct eventpoll *inserting_into;
 267
 268/* Slab cache used to allocate "struct epitem" */
 269static struct kmem_cache *epi_cache __ro_after_init;
 270
 271/* Slab cache used to allocate "struct eppoll_entry" */
 272static struct kmem_cache *pwq_cache __ro_after_init;
 273
 274/*
 275 * List of files with newly added links, where we may need to limit the number
 276 * of emanating paths. Protected by the epnested_mutex.
 277 */
 278struct epitems_head {
 279	struct hlist_head epitems;
 280	struct epitems_head *next;
 281};
 282static struct epitems_head *tfile_check_list = EP_UNACTIVE_PTR;
 283
 284static struct kmem_cache *ephead_cache __ro_after_init;
 285
 286static inline void free_ephead(struct epitems_head *head)
 287{
 288	if (head)
 289		kmem_cache_free(ephead_cache, head);
 290}
 291
 292static void list_file(struct file *file)
 293{
 294	struct epitems_head *head;
 295
 296	head = container_of(file->f_ep, struct epitems_head, epitems);
 297	if (!head->next) {
 298		head->next = tfile_check_list;
 299		tfile_check_list = head;
 300	}
 301}
 302
 303static void unlist_file(struct epitems_head *head)
 304{
 305	struct epitems_head *to_free = head;
 306	struct hlist_node *p = rcu_dereference(hlist_first_rcu(&head->epitems));
 307	if (p) {
 308		struct epitem *epi= container_of(p, struct epitem, fllink);
 309		spin_lock(&epi->ffd.file->f_lock);
 310		if (!hlist_empty(&head->epitems))
 311			to_free = NULL;
 312		head->next = NULL;
 313		spin_unlock(&epi->ffd.file->f_lock);
 314	}
 315	free_ephead(to_free);
 316}
 317
 318#ifdef CONFIG_SYSCTL
 319
 320#include <linux/sysctl.h>
 321
 322static long long_zero;
 323static long long_max = LONG_MAX;
 324
 325static const struct ctl_table epoll_table[] = {
 326	{
 327		.procname	= "max_user_watches",
 328		.data		= &max_user_watches,
 329		.maxlen		= sizeof(max_user_watches),
 330		.mode		= 0644,
 331		.proc_handler	= proc_doulongvec_minmax,
 332		.extra1		= &long_zero,
 333		.extra2		= &long_max,
 334	},
 335};
 336
 337static void __init epoll_sysctls_init(void)
 338{
 339	register_sysctl("fs/epoll", epoll_table);
 340}
 341#else
 342#define epoll_sysctls_init() do { } while (0)
 343#endif /* CONFIG_SYSCTL */
 344
 345static const struct file_operations eventpoll_fops;
 346
 347static inline int is_file_epoll(struct file *f)
 348{
 349	return f->f_op == &eventpoll_fops;
 350}
 351
 352/* Setup the structure that is used as key for the RB tree */
 353static inline void ep_set_ffd(struct epoll_filefd *ffd,
 354			      struct file *file, int fd)
 355{
 356	ffd->file = file;
 357	ffd->fd = fd;
 358}
 359
 360/* Compare RB tree keys */
 361static inline int ep_cmp_ffd(struct epoll_filefd *p1,
 362			     struct epoll_filefd *p2)
 363{
 364	return (p1->file > p2->file ? +1:
 365	        (p1->file < p2->file ? -1 : p1->fd - p2->fd));
 366}
 367
 368/* Tells us if the item is currently linked */
 369static inline int ep_is_linked(struct epitem *epi)
 370{
 371	return !list_empty(&epi->rdllink);
 372}
 373
 374static inline struct eppoll_entry *ep_pwq_from_wait(wait_queue_entry_t *p)
 375{
 376	return container_of(p, struct eppoll_entry, wait);
 377}
 378
 379/* Get the "struct epitem" from a wait queue pointer */
 380static inline struct epitem *ep_item_from_wait(wait_queue_entry_t *p)
 381{
 382	return container_of(p, struct eppoll_entry, wait)->base;
 383}
 384
 385/**
 386 * ep_events_available - Checks if ready events might be available.
 387 *
 388 * @ep: Pointer to the eventpoll context.
 389 *
 390 * Return: a value different than %zero if ready events are available,
 391 *          or %zero otherwise.
 392 */
 393static inline int ep_events_available(struct eventpoll *ep)
 394{
 395	return !list_empty_careful(&ep->rdllist) ||
 396		READ_ONCE(ep->ovflist) != EP_UNACTIVE_PTR;
 397}
 398
 399#ifdef CONFIG_NET_RX_BUSY_POLL
 400/**
 401 * busy_loop_ep_timeout - check if busy poll has timed out. The timeout value
 402 * from the epoll instance ep is preferred, but if it is not set fallback to
 403 * the system-wide global via busy_loop_timeout.
 404 *
 405 * @start_time: The start time used to compute the remaining time until timeout.
 406 * @ep: Pointer to the eventpoll context.
 407 *
 408 * Return: true if the timeout has expired, false otherwise.
 409 */
 410static bool busy_loop_ep_timeout(unsigned long start_time,
 411				 struct eventpoll *ep)
 412{
 413	unsigned long bp_usec = READ_ONCE(ep->busy_poll_usecs);
 414
 415	if (bp_usec) {
 416		unsigned long end_time = start_time + bp_usec;
 417		unsigned long now = busy_loop_current_time();
 418
 419		return time_after(now, end_time);
 420	} else {
 421		return busy_loop_timeout(start_time);
 422	}
 423}
 424
 425static bool ep_busy_loop_on(struct eventpoll *ep)
 426{
 427	return !!READ_ONCE(ep->busy_poll_usecs) ||
 428	       READ_ONCE(ep->prefer_busy_poll) ||
 429	       net_busy_loop_on();
 430}
 431
 432static bool ep_busy_loop_end(void *p, unsigned long start_time)
 433{
 434	struct eventpoll *ep = p;
 435
 436	return ep_events_available(ep) || busy_loop_ep_timeout(start_time, ep);
 437}
 438
 439/*
 440 * Busy poll if globally on and supporting sockets found && no events,
 441 * busy loop will return if need_resched or ep_events_available.
 442 *
 443 * we must do our busy polling with irqs enabled
 444 */
 445static bool ep_busy_loop(struct eventpoll *ep)
 446{
 447	unsigned int napi_id = READ_ONCE(ep->napi_id);
 448	u16 budget = READ_ONCE(ep->busy_poll_budget);
 449	bool prefer_busy_poll = READ_ONCE(ep->prefer_busy_poll);
 450
 451	if (!budget)
 452		budget = BUSY_POLL_BUDGET;
 453
 454	if (napi_id_valid(napi_id) && ep_busy_loop_on(ep)) {
 455		napi_busy_loop(napi_id, ep_busy_loop_end,
 456			       ep, prefer_busy_poll, budget);
 457		if (ep_events_available(ep))
 458			return true;
 459		/*
 460		 * Busy poll timed out.  Drop NAPI ID for now, we can add
 461		 * it back in when we have moved a socket with a valid NAPI
 462		 * ID onto the ready list.
 463		 */
 464		if (prefer_busy_poll)
 465			napi_resume_irqs(napi_id);
 466		ep->napi_id = 0;
 467		return false;
 468	}
 469	return false;
 470}
 471
 472/*
 473 * Set epoll busy poll NAPI ID from sk.
 474 */
 475static inline void ep_set_busy_poll_napi_id(struct epitem *epi)
 476{
 477	struct eventpoll *ep = epi->ep;
 478	unsigned int napi_id;
 479	struct socket *sock;
 480	struct sock *sk;
 481
 482	if (!ep_busy_loop_on(ep))
 483		return;
 484
 485	sock = sock_from_file(epi->ffd.file);
 486	if (!sock)
 487		return;
 488
 489	sk = sock->sk;
 490	if (!sk)
 491		return;
 492
 493	napi_id = READ_ONCE(sk->sk_napi_id);
 494
 495	/* Non-NAPI IDs can be rejected
 496	 *	or
 497	 * Nothing to do if we already have this ID
 498	 */
 499	if (!napi_id_valid(napi_id) || napi_id == ep->napi_id)
 500		return;
 501
 502	/* record NAPI ID for use in next busy poll */
 503	ep->napi_id = napi_id;
 504}
 505
 506static long ep_eventpoll_bp_ioctl(struct file *file, unsigned int cmd,
 507				  unsigned long arg)
 508{
 509	struct eventpoll *ep = file->private_data;
 510	void __user *uarg = (void __user *)arg;
 511	struct epoll_params epoll_params;
 512
 513	switch (cmd) {
 514	case EPIOCSPARAMS:
 515		if (copy_from_user(&epoll_params, uarg, sizeof(epoll_params)))
 516			return -EFAULT;
 517
 518		/* pad byte must be zero */
 519		if (epoll_params.__pad)
 520			return -EINVAL;
 521
 522		if (epoll_params.busy_poll_usecs > S32_MAX)
 523			return -EINVAL;
 524
 525		if (epoll_params.prefer_busy_poll > 1)
 526			return -EINVAL;
 527
 528		if (epoll_params.busy_poll_budget > NAPI_POLL_WEIGHT &&
 529		    !capable(CAP_NET_ADMIN))
 530			return -EPERM;
 531
 532		WRITE_ONCE(ep->busy_poll_usecs, epoll_params.busy_poll_usecs);
 533		WRITE_ONCE(ep->busy_poll_budget, epoll_params.busy_poll_budget);
 534		WRITE_ONCE(ep->prefer_busy_poll, epoll_params.prefer_busy_poll);
 535		return 0;
 536	case EPIOCGPARAMS:
 537		memset(&epoll_params, 0, sizeof(epoll_params));
 538		epoll_params.busy_poll_usecs = READ_ONCE(ep->busy_poll_usecs);
 539		epoll_params.busy_poll_budget = READ_ONCE(ep->busy_poll_budget);
 540		epoll_params.prefer_busy_poll = READ_ONCE(ep->prefer_busy_poll);
 541		if (copy_to_user(uarg, &epoll_params, sizeof(epoll_params)))
 542			return -EFAULT;
 543		return 0;
 544	default:
 545		return -ENOIOCTLCMD;
 546	}
 547}
 548
 549static void ep_suspend_napi_irqs(struct eventpoll *ep)
 550{
 551	unsigned int napi_id = READ_ONCE(ep->napi_id);
 552
 553	if (napi_id_valid(napi_id) && READ_ONCE(ep->prefer_busy_poll))
 554		napi_suspend_irqs(napi_id);
 555}
 556
 557static void ep_resume_napi_irqs(struct eventpoll *ep)
 558{
 559	unsigned int napi_id = READ_ONCE(ep->napi_id);
 560
 561	if (napi_id_valid(napi_id) && READ_ONCE(ep->prefer_busy_poll))
 562		napi_resume_irqs(napi_id);
 563}
 564
 565#else
 566
 567static inline bool ep_busy_loop(struct eventpoll *ep)
 568{
 569	return false;
 570}
 571
 572static inline void ep_set_busy_poll_napi_id(struct epitem *epi)
 573{
 574}
 575
 576static long ep_eventpoll_bp_ioctl(struct file *file, unsigned int cmd,
 577				  unsigned long arg)
 578{
 579	return -EOPNOTSUPP;
 580}
 581
 582static void ep_suspend_napi_irqs(struct eventpoll *ep)
 583{
 584}
 585
 586static void ep_resume_napi_irqs(struct eventpoll *ep)
 587{
 588}
 589
 590#endif /* CONFIG_NET_RX_BUSY_POLL */
 591
 592/*
 593 * As described in commit 0ccf831cb lockdep: annotate epoll
 594 * the use of wait queues used by epoll is done in a very controlled
 595 * manner. Wake ups can nest inside each other, but are never done
 596 * with the same locking. For example:
 597 *
 598 *   dfd = socket(...);
 599 *   efd1 = epoll_create();
 600 *   efd2 = epoll_create();
 601 *   epoll_ctl(efd1, EPOLL_CTL_ADD, dfd, ...);
 602 *   epoll_ctl(efd2, EPOLL_CTL_ADD, efd1, ...);
 603 *
 604 * When a packet arrives to the device underneath "dfd", the net code will
 605 * issue a wake_up() on its poll wake list. Epoll (efd1) has installed a
 606 * callback wakeup entry on that queue, and the wake_up() performed by the
 607 * "dfd" net code will end up in ep_poll_callback(). At this point epoll
 608 * (efd1) notices that it may have some event ready, so it needs to wake up
 609 * the waiters on its poll wait list (efd2). So it calls ep_poll_safewake()
 610 * that ends up in another wake_up(), after having checked about the
 611 * recursion constraints. That are, no more than EP_MAX_NESTS, to avoid
 612 * stack blasting.
 613 *
 614 * When CONFIG_DEBUG_LOCK_ALLOC is enabled, make sure lockdep can handle
 615 * this special case of epoll.
 616 */
 617#ifdef CONFIG_DEBUG_LOCK_ALLOC
 618
 619static void ep_poll_safewake(struct eventpoll *ep, struct epitem *epi,
 620			     unsigned pollflags)
 621{
 622	struct eventpoll *ep_src;
 623	unsigned long flags;
 624	u8 nests = 0;
 625
 626	/*
 627	 * To set the subclass or nesting level for spin_lock_irqsave_nested()
 628	 * it might be natural to create a per-cpu nest count. However, since
 629	 * we can recurse on ep->poll_wait.lock, and a non-raw spinlock can
 630	 * schedule() in the -rt kernel, the per-cpu variable are no longer
 631	 * protected. Thus, we are introducing a per eventpoll nest field.
 632	 * If we are not being call from ep_poll_callback(), epi is NULL and
 633	 * we are at the first level of nesting, 0. Otherwise, we are being
 634	 * called from ep_poll_callback() and if a previous wakeup source is
 635	 * not an epoll file itself, we are at depth 1 since the wakeup source
 636	 * is depth 0. If the wakeup source is a previous epoll file in the
 637	 * wakeup chain then we use its nests value and record ours as
 638	 * nests + 1. The previous epoll file nests value is stable since its
 639	 * already holding its own poll_wait.lock.
 640	 */
 641	if (epi) {
 642		if ((is_file_epoll(epi->ffd.file))) {
 643			ep_src = epi->ffd.file->private_data;
 644			nests = ep_src->nests;
 645		} else {
 646			nests = 1;
 647		}
 648	}
 649	spin_lock_irqsave_nested(&ep->poll_wait.lock, flags, nests);
 650	ep->nests = nests + 1;
 651	wake_up_locked_poll(&ep->poll_wait, EPOLLIN | pollflags);
 652	ep->nests = 0;
 653	spin_unlock_irqrestore(&ep->poll_wait.lock, flags);
 654}
 655
 656#else
 657
 658static void ep_poll_safewake(struct eventpoll *ep, struct epitem *epi,
 659			     __poll_t pollflags)
 660{
 661	wake_up_poll(&ep->poll_wait, EPOLLIN | pollflags);
 662}
 663
 664#endif
 665
 666static void ep_remove_wait_queue(struct eppoll_entry *pwq)
 667{
 668	wait_queue_head_t *whead;
 669
 670	rcu_read_lock();
 671	/*
 672	 * If it is cleared by POLLFREE, it should be rcu-safe.
 673	 * If we read NULL we need a barrier paired with
 674	 * smp_store_release() in ep_poll_callback(), otherwise
 675	 * we rely on whead->lock.
 676	 */
 677	whead = smp_load_acquire(&pwq->whead);
 678	if (whead)
 679		remove_wait_queue(whead, &pwq->wait);
 680	rcu_read_unlock();
 681}
 682
 683/*
 684 * This function unregisters poll callbacks from the associated file
 685 * descriptor.  Must be called with "mtx" held.
 686 */
 687static void ep_unregister_pollwait(struct eventpoll *ep, struct epitem *epi)
 688{
 689	struct eppoll_entry **p = &epi->pwqlist;
 690	struct eppoll_entry *pwq;
 691
 692	while ((pwq = *p) != NULL) {
 693		*p = pwq->next;
 694		ep_remove_wait_queue(pwq);
 695		kmem_cache_free(pwq_cache, pwq);
 696	}
 697}
 698
 699/* call only when ep->mtx is held */
 700static inline struct wakeup_source *ep_wakeup_source(struct epitem *epi)
 701{
 702	return rcu_dereference_check(epi->ws, lockdep_is_held(&epi->ep->mtx));
 703}
 704
 705/* call only when ep->mtx is held */
 706static inline void ep_pm_stay_awake(struct epitem *epi)
 707{
 708	struct wakeup_source *ws = ep_wakeup_source(epi);
 709
 710	if (ws)
 711		__pm_stay_awake(ws);
 712}
 713
 714static inline bool ep_has_wakeup_source(struct epitem *epi)
 715{
 716	return rcu_access_pointer(epi->ws) ? true : false;
 717}
 718
 719/* call when ep->mtx cannot be held (ep_poll_callback) */
 720static inline void ep_pm_stay_awake_rcu(struct epitem *epi)
 721{
 722	struct wakeup_source *ws;
 723
 724	rcu_read_lock();
 725	ws = rcu_dereference(epi->ws);
 726	if (ws)
 727		__pm_stay_awake(ws);
 728	rcu_read_unlock();
 729}
 730
 731
 732/*
 733 * ep->mutex needs to be held because we could be hit by
 734 * eventpoll_release_file() and epoll_ctl().
 735 */
 736static void ep_start_scan(struct eventpoll *ep, struct list_head *txlist)
 737{
 738	/*
 739	 * Steal the ready list, and re-init the original one to the
 740	 * empty list. Also, set ep->ovflist to NULL so that events
 741	 * happening while looping w/out locks, are not lost. We cannot
 742	 * have the poll callback to queue directly on ep->rdllist,
 743	 * because we want the "sproc" callback to be able to do it
 744	 * in a lockless way.
 745	 */
 746	lockdep_assert_irqs_enabled();
 747	spin_lock_irq(&ep->lock);
 748	list_splice_init(&ep->rdllist, txlist);
 749	WRITE_ONCE(ep->ovflist, NULL);
 750	spin_unlock_irq(&ep->lock);
 751}
 752
 753static void ep_done_scan(struct eventpoll *ep,
 754			 struct list_head *txlist)
 755{
 756	struct epitem *epi, *nepi;
 757
 758	spin_lock_irq(&ep->lock);
 759	/*
 760	 * During the time we spent inside the "sproc" callback, some
 761	 * other events might have been queued by the poll callback.
 762	 * We re-insert them inside the main ready-list here.
 763	 */
 764	for (nepi = READ_ONCE(ep->ovflist); (epi = nepi) != NULL;
 765	     nepi = epi->next, epi->next = EP_UNACTIVE_PTR) {
 766		/*
 767		 * We need to check if the item is already in the list.
 768		 * During the "sproc" callback execution time, items are
 769		 * queued into ->ovflist but the "txlist" might already
 770		 * contain them, and the list_splice() below takes care of them.
 771		 */
 772		if (!ep_is_linked(epi)) {
 773			/*
 774			 * ->ovflist is LIFO, so we have to reverse it in order
 775			 * to keep in FIFO.
 776			 */
 777			list_add(&epi->rdllink, &ep->rdllist);
 778			ep_pm_stay_awake(epi);
 779		}
 780	}
 781	/*
 782	 * We need to set back ep->ovflist to EP_UNACTIVE_PTR, so that after
 783	 * releasing the lock, events will be queued in the normal way inside
 784	 * ep->rdllist.
 785	 */
 786	WRITE_ONCE(ep->ovflist, EP_UNACTIVE_PTR);
 787
 788	/*
 789	 * Quickly re-inject items left on "txlist".
 790	 */
 791	list_splice(txlist, &ep->rdllist);
 792	__pm_relax(ep->ws);
 793
 794	if (!list_empty(&ep->rdllist)) {
 795		if (waitqueue_active(&ep->wq))
 796			wake_up(&ep->wq);
 797	}
 798
 799	spin_unlock_irq(&ep->lock);
 800}
 801
 802static void ep_get(struct eventpoll *ep)
 803{
 804	refcount_inc(&ep->refcount);
 805}
 806
 807/*
 808 * Returns true if the event poll can be disposed
 809 */
 810static bool ep_refcount_dec_and_test(struct eventpoll *ep)
 811{
 812	if (!refcount_dec_and_test(&ep->refcount))
 813		return false;
 814
 815	WARN_ON_ONCE(!RB_EMPTY_ROOT(&ep->rbr.rb_root));
 816	return true;
 817}
 818
 819static void ep_free(struct eventpoll *ep)
 820{
 821	ep_resume_napi_irqs(ep);
 822	mutex_destroy(&ep->mtx);
 823	free_uid(ep->user);
 824	wakeup_source_unregister(ep->ws);
 825	/* ep_get_upwards_depth_proc() may still hold epi->ep under RCU */
 826	kfree_rcu(ep, rcu);
 827}
 828
 829/*
 830 * Removes a "struct epitem" from the eventpoll RB tree and deallocates
 831 * all the associated resources. Must be called with "mtx" held.
 832 * If the dying flag is set, do the removal only if force is true.
 833 * This prevents ep_clear_and_put() from dropping all the ep references
 834 * while running concurrently with eventpoll_release_file().
 835 * Returns true if the eventpoll can be disposed.
 836 */
 837static bool __ep_remove(struct eventpoll *ep, struct epitem *epi, bool force)
 838{
 839	struct file *file = epi->ffd.file;
 840	struct epitems_head *to_free;
 841	struct hlist_head *head;
 842
 843	lockdep_assert_irqs_enabled();
 844
 845	/*
 846	 * Removes poll wait queue hooks.
 847	 */
 848	ep_unregister_pollwait(ep, epi);
 849
 850	/* Remove the current item from the list of epoll hooks */
 851	spin_lock(&file->f_lock);
 852	if (epi->dying && !force) {
 853		spin_unlock(&file->f_lock);
 854		return false;
 855	}
 856
 857	to_free = NULL;
 858	head = file->f_ep;
 859	if (head->first == &epi->fllink && !epi->fllink.next) {
 860		/* See eventpoll_release() for details. */
 861		WRITE_ONCE(file->f_ep, NULL);
 862		if (!is_file_epoll(file)) {
 863			struct epitems_head *v;
 864			v = container_of(head, struct epitems_head, epitems);
 865			if (!smp_load_acquire(&v->next))
 866				to_free = v;
 867		}
 868	}
 869	hlist_del_rcu(&epi->fllink);
 870	spin_unlock(&file->f_lock);
 871	free_ephead(to_free);
 872
 873	rb_erase_cached(&epi->rbn, &ep->rbr);
 874
 875	spin_lock_irq(&ep->lock);
 876	if (ep_is_linked(epi))
 877		list_del_init(&epi->rdllink);
 878	spin_unlock_irq(&ep->lock);
 879
 880	wakeup_source_unregister(ep_wakeup_source(epi));
 881	/*
 882	 * At this point it is safe to free the eventpoll item. Use the union
 883	 * field epi->rcu, since we are trying to minimize the size of
 884	 * 'struct epitem'. The 'rbn' field is no longer in use. Protected by
 885	 * ep->mtx. The rcu read side, reverse_path_check_proc(), does not make
 886	 * use of the rbn field.
 887	 */
 888	kfree_rcu(epi, rcu);
 889
 890	percpu_counter_dec(&ep->user->epoll_watches);
 891	return true;
 892}
 893
 894/*
 895 * ep_remove variant for callers owing an additional reference to the ep
 896 */
 897static void ep_remove_safe(struct eventpoll *ep, struct epitem *epi)
 898{
 899	if (__ep_remove(ep, epi, false))
 900		WARN_ON_ONCE(ep_refcount_dec_and_test(ep));
 901}
 902
 903static void ep_clear_and_put(struct eventpoll *ep)
 904{
 905	struct rb_node *rbp, *next;
 906	struct epitem *epi;
 907
 908	/* We need to release all tasks waiting for these file */
 909	if (waitqueue_active(&ep->poll_wait))
 910		ep_poll_safewake(ep, NULL, 0);
 911
 912	mutex_lock(&ep->mtx);
 913
 914	/*
 915	 * Walks through the whole tree by unregistering poll callbacks.
 916	 */
 917	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
 918		epi = rb_entry(rbp, struct epitem, rbn);
 919
 920		ep_unregister_pollwait(ep, epi);
 921		cond_resched();
 922	}
 923
 924	/*
 925	 * Walks through the whole tree and try to free each "struct epitem".
 926	 * Note that ep_remove_safe() will not remove the epitem in case of a
 927	 * racing eventpoll_release_file(); the latter will do the removal.
 928	 * At this point we are sure no poll callbacks will be lingering around.
 929	 * Since we still own a reference to the eventpoll struct, the loop can't
 930	 * dispose it.
 931	 */
 932	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = next) {
 933		next = rb_next(rbp);
 934		epi = rb_entry(rbp, struct epitem, rbn);
 935		ep_remove_safe(ep, epi);
 936		cond_resched();
 937	}
 938
 939	mutex_unlock(&ep->mtx);
 940	if (ep_refcount_dec_and_test(ep))
 941		ep_free(ep);
 942}
 943
 944static long ep_eventpoll_ioctl(struct file *file, unsigned int cmd,
 945			       unsigned long arg)
 946{
 947	int ret;
 948
 949	if (!is_file_epoll(file))
 950		return -EINVAL;
 951
 952	switch (cmd) {
 953	case EPIOCSPARAMS:
 954	case EPIOCGPARAMS:
 955		ret = ep_eventpoll_bp_ioctl(file, cmd, arg);
 956		break;
 957	default:
 958		ret = -EINVAL;
 959		break;
 960	}
 961
 962	return ret;
 963}
 964
 965static int ep_eventpoll_release(struct inode *inode, struct file *file)
 966{
 967	struct eventpoll *ep = file->private_data;
 968
 969	if (ep)
 970		ep_clear_and_put(ep);
 971
 972	return 0;
 973}
 974
 975static __poll_t ep_item_poll(const struct epitem *epi, poll_table *pt, int depth);
 976
 977static __poll_t __ep_eventpoll_poll(struct file *file, poll_table *wait, int depth)
 978{
 979	struct eventpoll *ep = file->private_data;
 980	LIST_HEAD(txlist);
 981	struct epitem *epi, *tmp;
 982	poll_table pt;
 983	__poll_t res = 0;
 984
 985	init_poll_funcptr(&pt, NULL);
 986
 987	/* Insert inside our poll wait queue */
 988	poll_wait(file, &ep->poll_wait, wait);
 989
 990	/*
 991	 * Proceed to find out if wanted events are really available inside
 992	 * the ready list.
 993	 */
 994	mutex_lock_nested(&ep->mtx, depth);
 995	ep_start_scan(ep, &txlist);
 996	list_for_each_entry_safe(epi, tmp, &txlist, rdllink) {
 997		if (ep_item_poll(epi, &pt, depth + 1)) {
 998			res = EPOLLIN | EPOLLRDNORM;
 999			break;
1000		} else {
1001			/*
1002			 * Item has been dropped into the ready list by the poll
1003			 * callback, but it's not actually ready, as far as
1004			 * caller requested events goes. We can remove it here.
1005			 */
1006			__pm_relax(ep_wakeup_source(epi));
1007			list_del_init(&epi->rdllink);
1008		}
1009	}
1010	ep_done_scan(ep, &txlist);
1011	mutex_unlock(&ep->mtx);
1012	return res;
1013}
1014
1015/*
1016 * The ffd.file pointer may be in the process of being torn down due to
1017 * being closed, but we may not have finished eventpoll_release() yet.
1018 *
1019 * Normally, even with the atomic_long_inc_not_zero, the file may have
1020 * been free'd and then gotten re-allocated to something else (since
1021 * files are not RCU-delayed, they are SLAB_TYPESAFE_BY_RCU).
1022 *
1023 * But for epoll, users hold the ep->mtx mutex, and as such any file in
1024 * the process of being free'd will block in eventpoll_release_file()
1025 * and thus the underlying file allocation will not be free'd, and the
1026 * file re-use cannot happen.
1027 *
1028 * For the same reason we can avoid a rcu_read_lock() around the
1029 * operation - 'ffd.file' cannot go away even if the refcount has
1030 * reached zero (but we must still not call out to ->poll() functions
1031 * etc).
1032 */
1033static struct file *epi_fget(const struct epitem *epi)
1034{
1035	struct file *file;
1036
1037	file = epi->ffd.file;
1038	if (!file_ref_get(&file->f_ref))
1039		file = NULL;
1040	return file;
1041}
1042
1043/*
1044 * Differs from ep_eventpoll_poll() in that internal callers already have
1045 * the ep->mtx so we need to start from depth=1, such that mutex_lock_nested()
1046 * is correctly annotated.
1047 */
1048static __poll_t ep_item_poll(const struct epitem *epi, poll_table *pt,
1049				 int depth)
1050{
1051	struct file *file = epi_fget(epi);
1052	__poll_t res;
1053
1054	/*
1055	 * We could return EPOLLERR | EPOLLHUP or something, but let's
1056	 * treat this more as "file doesn't exist, poll didn't happen".
1057	 */
1058	if (!file)
1059		return 0;
1060
1061	pt->_key = epi->event.events;
1062	if (!is_file_epoll(file))
1063		res = vfs_poll(file, pt);
1064	else
1065		res = __ep_eventpoll_poll(file, pt, depth);
1066	fput(file);
1067	return res & epi->event.events;
1068}
1069
1070static __poll_t ep_eventpoll_poll(struct file *file, poll_table *wait)
1071{
1072	return __ep_eventpoll_poll(file, wait, 0);
1073}
1074
1075#ifdef CONFIG_PROC_FS
1076static void ep_show_fdinfo(struct seq_file *m, struct file *f)
1077{
1078	struct eventpoll *ep = f->private_data;
1079	struct rb_node *rbp;
1080
1081	mutex_lock(&ep->mtx);
1082	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
1083		struct epitem *epi = rb_entry(rbp, struct epitem, rbn);
1084		struct inode *inode = file_inode(epi->ffd.file);
1085
1086		seq_printf(m, "tfd: %8d events: %8x data: %16llx "
1087			   " pos:%lli ino:%lx sdev:%x\n",
1088			   epi->ffd.fd, epi->event.events,
1089			   (long long)epi->event.data,
1090			   (long long)epi->ffd.file->f_pos,
1091			   inode->i_ino, inode->i_sb->s_dev);
1092		if (seq_has_overflowed(m))
1093			break;
1094	}
1095	mutex_unlock(&ep->mtx);
1096}
1097#endif
1098
1099/* File callbacks that implement the eventpoll file behaviour */
1100static const struct file_operations eventpoll_fops = {
1101#ifdef CONFIG_PROC_FS
1102	.show_fdinfo	= ep_show_fdinfo,
1103#endif
1104	.release	= ep_eventpoll_release,
1105	.poll		= ep_eventpoll_poll,
1106	.llseek		= noop_llseek,
1107	.unlocked_ioctl	= ep_eventpoll_ioctl,
1108	.compat_ioctl   = compat_ptr_ioctl,
1109};
1110
1111/*
1112 * This is called from eventpoll_release() to unlink files from the eventpoll
1113 * interface. We need to have this facility to cleanup correctly files that are
1114 * closed without being removed from the eventpoll interface.
1115 */
1116void eventpoll_release_file(struct file *file)
1117{
1118	struct eventpoll *ep;
1119	struct epitem *epi;
1120	bool dispose;
1121
1122	/*
1123	 * Use the 'dying' flag to prevent a concurrent ep_clear_and_put() from
1124	 * touching the epitems list before eventpoll_release_file() can access
1125	 * the ep->mtx.
1126	 */
1127again:
1128	spin_lock(&file->f_lock);
1129	if (file->f_ep && file->f_ep->first) {
1130		epi = hlist_entry(file->f_ep->first, struct epitem, fllink);
1131		epi->dying = true;
1132		spin_unlock(&file->f_lock);
1133
1134		/*
1135		 * ep access is safe as we still own a reference to the ep
1136		 * struct
1137		 */
1138		ep = epi->ep;
1139		mutex_lock(&ep->mtx);
1140		dispose = __ep_remove(ep, epi, true);
1141		mutex_unlock(&ep->mtx);
1142
1143		if (dispose && ep_refcount_dec_and_test(ep))
1144			ep_free(ep);
1145		goto again;
1146	}
1147	spin_unlock(&file->f_lock);
1148}
1149
1150static int ep_alloc(struct eventpoll **pep)
1151{
1152	struct eventpoll *ep;
1153
1154	ep = kzalloc(sizeof(*ep), GFP_KERNEL);
1155	if (unlikely(!ep))
1156		return -ENOMEM;
1157
1158	mutex_init(&ep->mtx);
1159	spin_lock_init(&ep->lock);
1160	init_waitqueue_head(&ep->wq);
1161	init_waitqueue_head(&ep->poll_wait);
1162	INIT_LIST_HEAD(&ep->rdllist);
1163	ep->rbr = RB_ROOT_CACHED;
1164	ep->ovflist = EP_UNACTIVE_PTR;
1165	ep->user = get_current_user();
1166	refcount_set(&ep->refcount, 1);
1167
1168	*pep = ep;
1169
1170	return 0;
1171}
1172
1173/*
1174 * Search the file inside the eventpoll tree. The RB tree operations
1175 * are protected by the "mtx" mutex, and ep_find() must be called with
1176 * "mtx" held.
1177 */
1178static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
1179{
1180	int kcmp;
1181	struct rb_node *rbp;
1182	struct epitem *epi, *epir = NULL;
1183	struct epoll_filefd ffd;
1184
1185	ep_set_ffd(&ffd, file, fd);
1186	for (rbp = ep->rbr.rb_root.rb_node; rbp; ) {
1187		epi = rb_entry(rbp, struct epitem, rbn);
1188		kcmp = ep_cmp_ffd(&ffd, &epi->ffd);
1189		if (kcmp > 0)
1190			rbp = rbp->rb_right;
1191		else if (kcmp < 0)
1192			rbp = rbp->rb_left;
1193		else {
1194			epir = epi;
1195			break;
1196		}
1197	}
1198
1199	return epir;
1200}
1201
1202#ifdef CONFIG_KCMP
1203static struct epitem *ep_find_tfd(struct eventpoll *ep, int tfd, unsigned long toff)
1204{
1205	struct rb_node *rbp;
1206	struct epitem *epi;
1207
1208	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
1209		epi = rb_entry(rbp, struct epitem, rbn);
1210		if (epi->ffd.fd == tfd) {
1211			if (toff == 0)
1212				return epi;
1213			else
1214				toff--;
1215		}
1216		cond_resched();
1217	}
1218
1219	return NULL;
1220}
1221
1222struct file *get_epoll_tfile_raw_ptr(struct file *file, int tfd,
1223				     unsigned long toff)
1224{
1225	struct file *file_raw;
1226	struct eventpoll *ep;
1227	struct epitem *epi;
1228
1229	if (!is_file_epoll(file))
1230		return ERR_PTR(-EINVAL);
1231
1232	ep = file->private_data;
1233
1234	mutex_lock(&ep->mtx);
1235	epi = ep_find_tfd(ep, tfd, toff);
1236	if (epi)
1237		file_raw = epi->ffd.file;
1238	else
1239		file_raw = ERR_PTR(-ENOENT);
1240	mutex_unlock(&ep->mtx);
1241
1242	return file_raw;
1243}
1244#endif /* CONFIG_KCMP */
1245
1246/*
1247 * This is the callback that is passed to the wait queue wakeup
1248 * mechanism. It is called by the stored file descriptors when they
1249 * have events to report.
1250 */
1251static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)
1252{
1253	int pwake = 0;
1254	struct epitem *epi = ep_item_from_wait(wait);
1255	struct eventpoll *ep = epi->ep;
1256	__poll_t pollflags = key_to_poll(key);
1257	unsigned long flags;
1258	int ewake = 0;
1259
1260	spin_lock_irqsave(&ep->lock, flags);
1261
1262	ep_set_busy_poll_napi_id(epi);
1263
1264	/*
1265	 * If the event mask does not contain any poll(2) event, we consider the
1266	 * descriptor to be disabled. This condition is likely the effect of the
1267	 * EPOLLONESHOT bit that disables the descriptor when an event is received,
1268	 * until the next EPOLL_CTL_MOD will be issued.
1269	 */
1270	if (!(epi->event.events & ~EP_PRIVATE_BITS))
1271		goto out_unlock;
1272
1273	/*
1274	 * Check the events coming with the callback. At this stage, not
1275	 * every device reports the events in the "key" parameter of the
1276	 * callback. We need to be able to handle both cases here, hence the
1277	 * test for "key" != NULL before the event match test.
1278	 */
1279	if (pollflags && !(pollflags & epi->event.events))
1280		goto out_unlock;
1281
1282	/*
1283	 * If we are transferring events to userspace, we can hold no locks
1284	 * (because we're accessing user memory, and because of linux f_op->poll()
1285	 * semantics). All the events that happen during that period of time are
1286	 * chained in ep->ovflist and requeued later on.
1287	 */
1288	if (READ_ONCE(ep->ovflist) != EP_UNACTIVE_PTR) {
1289		if (epi->next == EP_UNACTIVE_PTR) {
1290			epi->next = READ_ONCE(ep->ovflist);
1291			WRITE_ONCE(ep->ovflist, epi);
1292			ep_pm_stay_awake_rcu(epi);
1293		}
1294	} else if (!ep_is_linked(epi)) {
1295		/* In the usual case, add event to ready list. */
1296		list_add_tail(&epi->rdllink, &ep->rdllist);
1297		ep_pm_stay_awake_rcu(epi);
1298	}
1299
1300	/*
1301	 * Wake up ( if active ) both the eventpoll wait list and the ->poll()
1302	 * wait list.
1303	 */
1304	if (waitqueue_active(&ep->wq)) {
1305		if ((epi->event.events & EPOLLEXCLUSIVE) &&
1306					!(pollflags & POLLFREE)) {
1307			switch (pollflags & EPOLLINOUT_BITS) {
1308			case EPOLLIN:
1309				if (epi->event.events & EPOLLIN)
1310					ewake = 1;
1311				break;
1312			case EPOLLOUT:
1313				if (epi->event.events & EPOLLOUT)
1314					ewake = 1;
1315				break;
1316			case 0:
1317				ewake = 1;
1318				break;
1319			}
1320		}
1321		if (sync)
1322			wake_up_sync(&ep->wq);
1323		else
1324			wake_up(&ep->wq);
1325	}
1326	if (waitqueue_active(&ep->poll_wait))
1327		pwake++;
1328
1329out_unlock:
1330	spin_unlock_irqrestore(&ep->lock, flags);
1331
1332	/* We have to call this outside the lock */
1333	if (pwake)
1334		ep_poll_safewake(ep, epi, pollflags & EPOLL_URING_WAKE);
1335
1336	if (!(epi->event.events & EPOLLEXCLUSIVE))
1337		ewake = 1;
1338
1339	if (pollflags & POLLFREE) {
1340		/*
1341		 * If we race with ep_remove_wait_queue() it can miss
1342		 * ->whead = NULL and do another remove_wait_queue() after
1343		 * us, so we can't use __remove_wait_queue().
1344		 */
1345		list_del_init(&wait->entry);
1346		/*
1347		 * ->whead != NULL protects us from the race with
1348		 * ep_clear_and_put() or ep_remove(), ep_remove_wait_queue()
1349		 * takes whead->lock held by the caller. Once we nullify it,
1350		 * nothing protects ep/epi or even wait.
1351		 */
1352		smp_store_release(&ep_pwq_from_wait(wait)->whead, NULL);
1353	}
1354
1355	return ewake;
1356}
1357
1358/*
1359 * This is the callback that is used to add our wait queue to the
1360 * target file wakeup lists.
1361 */
1362static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
1363				 poll_table *pt)
1364{
1365	struct ep_pqueue *epq = container_of(pt, struct ep_pqueue, pt);
1366	struct epitem *epi = epq->epi;
1367	struct eppoll_entry *pwq;
1368
1369	if (unlikely(!epi))	// an earlier allocation has failed
1370		return;
1371
1372	pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL);
1373	if (unlikely(!pwq)) {
1374		epq->epi = NULL;
1375		return;
1376	}
1377
1378	init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
1379	pwq->whead = whead;
1380	pwq->base = epi;
1381	if (epi->event.events & EPOLLEXCLUSIVE)
1382		add_wait_queue_exclusive(whead, &pwq->wait);
1383	else
1384		add_wait_queue(whead, &pwq->wait);
1385	pwq->next = epi->pwqlist;
1386	epi->pwqlist = pwq;
1387}
1388
1389static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi)
1390{
1391	int kcmp;
1392	struct rb_node **p = &ep->rbr.rb_root.rb_node, *parent = NULL;
1393	struct epitem *epic;
1394	bool leftmost = true;
1395
1396	while (*p) {
1397		parent = *p;
1398		epic = rb_entry(parent, struct epitem, rbn);
1399		kcmp = ep_cmp_ffd(&epi->ffd, &epic->ffd);
1400		if (kcmp > 0) {
1401			p = &parent->rb_right;
1402			leftmost = false;
1403		} else
1404			p = &parent->rb_left;
1405	}
1406	rb_link_node(&epi->rbn, parent, p);
1407	rb_insert_color_cached(&epi->rbn, &ep->rbr, leftmost);
1408}
1409
1410
1411
1412#define PATH_ARR_SIZE 5
1413/*
1414 * These are the number paths of length 1 to 5, that we are allowing to emanate
1415 * from a single file of interest. For example, we allow 1000 paths of length
1416 * 1, to emanate from each file of interest. This essentially represents the
1417 * potential wakeup paths, which need to be limited in order to avoid massive
1418 * uncontrolled wakeup storms. The common use case should be a single ep which
1419 * is connected to n file sources. In this case each file source has 1 path
1420 * of length 1. Thus, the numbers below should be more than sufficient. These
1421 * path limits are enforced during an EPOLL_CTL_ADD operation, since a modify
1422 * and delete can't add additional paths. Protected by the epnested_mutex.
1423 */
1424static const int path_limits[PATH_ARR_SIZE] = { 1000, 500, 100, 50, 10 };
1425static int path_count[PATH_ARR_SIZE];
1426
1427static int path_count_inc(int nests)
1428{
1429	/* Allow an arbitrary number of depth 1 paths */
1430	if (nests == 0)
1431		return 0;
1432
1433	if (++path_count[nests] > path_limits[nests])
1434		return -1;
1435	return 0;
1436}
1437
1438static void path_count_init(void)
1439{
1440	int i;
1441
1442	for (i = 0; i < PATH_ARR_SIZE; i++)
1443		path_count[i] = 0;
1444}
1445
1446static int reverse_path_check_proc(struct hlist_head *refs, int depth)
1447{
1448	int error = 0;
1449	struct epitem *epi;
1450
1451	if (depth > EP_MAX_NESTS) /* too deep nesting */
1452		return -1;
1453
1454	/* CTL_DEL can remove links here, but that can't increase our count */
1455	hlist_for_each_entry_rcu(epi, refs, fllink) {
1456		struct hlist_head *refs = &epi->ep->refs;
1457		if (hlist_empty(refs))
1458			error = path_count_inc(depth);
1459		else
1460			error = reverse_path_check_proc(refs, depth + 1);
1461		if (error != 0)
1462			break;
1463	}
1464	return error;
1465}
1466
1467/**
1468 * reverse_path_check - The tfile_check_list is list of epitem_head, which have
1469 *                      links that are proposed to be newly added. We need to
1470 *                      make sure that those added links don't add too many
1471 *                      paths such that we will spend all our time waking up
1472 *                      eventpoll objects.
1473 *
1474 * Return: %zero if the proposed links don't create too many paths,
1475 *	    %-1 otherwise.
1476 */
1477static int reverse_path_check(void)
1478{
1479	struct epitems_head *p;
1480
1481	for (p = tfile_check_list; p != EP_UNACTIVE_PTR; p = p->next) {
1482		int error;
1483		path_count_init();
1484		rcu_read_lock();
1485		error = reverse_path_check_proc(&p->epitems, 0);
1486		rcu_read_unlock();
1487		if (error)
1488			return error;
1489	}
1490	return 0;
1491}
1492
1493static int ep_create_wakeup_source(struct epitem *epi)
1494{
1495	struct name_snapshot n;
1496	struct wakeup_source *ws;
1497
1498	if (!epi->ep->ws) {
1499		epi->ep->ws = wakeup_source_register(NULL, "eventpoll");
1500		if (!epi->ep->ws)
1501			return -ENOMEM;
1502	}
1503
1504	take_dentry_name_snapshot(&n, epi->ffd.file->f_path.dentry);
1505	ws = wakeup_source_register(NULL, n.name.name);
1506	release_dentry_name_snapshot(&n);
1507
1508	if (!ws)
1509		return -ENOMEM;
1510	rcu_assign_pointer(epi->ws, ws);
1511
1512	return 0;
1513}
1514
1515/* rare code path, only used when EPOLL_CTL_MOD removes a wakeup source */
1516static noinline void ep_destroy_wakeup_source(struct epitem *epi)
1517{
1518	struct wakeup_source *ws = ep_wakeup_source(epi);
1519
1520	RCU_INIT_POINTER(epi->ws, NULL);
1521
1522	/*
1523	 * wait for ep_pm_stay_awake_rcu to finish, synchronize_rcu is
1524	 * used internally by wakeup_source_remove, too (called by
1525	 * wakeup_source_unregister), so we cannot use call_rcu
1526	 */
1527	synchronize_rcu();
1528	wakeup_source_unregister(ws);
1529}
1530
1531static int attach_epitem(struct file *file, struct epitem *epi)
1532{
1533	struct epitems_head *to_free = NULL;
1534	struct hlist_head *head = NULL;
1535	struct eventpoll *ep = NULL;
1536
1537	if (is_file_epoll(file))
1538		ep = file->private_data;
1539
1540	if (ep) {
1541		head = &ep->refs;
1542	} else if (!READ_ONCE(file->f_ep)) {
1543allocate:
1544		to_free = kmem_cache_zalloc(ephead_cache, GFP_KERNEL);
1545		if (!to_free)
1546			return -ENOMEM;
1547		head = &to_free->epitems;
1548	}
1549	spin_lock(&file->f_lock);
1550	if (!file->f_ep) {
1551		if (unlikely(!head)) {
1552			spin_unlock(&file->f_lock);
1553			goto allocate;
1554		}
1555		/* See eventpoll_release() for details. */
1556		WRITE_ONCE(file->f_ep, head);
1557		to_free = NULL;
1558	}
1559	hlist_add_head_rcu(&epi->fllink, file->f_ep);
1560	spin_unlock(&file->f_lock);
1561	free_ephead(to_free);
1562	return 0;
1563}
1564
1565/*
1566 * Must be called with "mtx" held.
1567 */
1568static int ep_insert(struct eventpoll *ep, const struct epoll_event *event,
1569		     struct file *tfile, int fd, int full_check)
1570{
1571	int error, pwake = 0;
1572	__poll_t revents;
1573	struct epitem *epi;
1574	struct ep_pqueue epq;
1575	struct eventpoll *tep = NULL;
1576
1577	if (is_file_epoll(tfile))
1578		tep = tfile->private_data;
1579
1580	lockdep_assert_irqs_enabled();
1581
1582	if (unlikely(percpu_counter_compare(&ep->user->epoll_watches,
1583					    max_user_watches) >= 0))
1584		return -ENOSPC;
1585	percpu_counter_inc(&ep->user->epoll_watches);
1586
1587	if (!(epi = kmem_cache_zalloc(epi_cache, GFP_KERNEL))) {
1588		percpu_counter_dec(&ep->user->epoll_watches);
1589		return -ENOMEM;
1590	}
1591
1592	/* Item initialization follow here ... */
1593	INIT_LIST_HEAD(&epi->rdllink);
1594	epi->ep = ep;
1595	ep_set_ffd(&epi->ffd, tfile, fd);
1596	epi->event = *event;
1597	epi->next = EP_UNACTIVE_PTR;
1598
1599	if (tep)
1600		mutex_lock_nested(&tep->mtx, 1);
1601	/* Add the current item to the list of active epoll hook for this file */
1602	if (unlikely(attach_epitem(tfile, epi) < 0)) {
1603		if (tep)
1604			mutex_unlock(&tep->mtx);
1605		kmem_cache_free(epi_cache, epi);
1606		percpu_counter_dec(&ep->user->epoll_watches);
1607		return -ENOMEM;
1608	}
1609
1610	if (full_check && !tep)
1611		list_file(tfile);
1612
1613	/*
1614	 * Add the current item to the RB tree. All RB tree operations are
1615	 * protected by "mtx", and ep_insert() is called with "mtx" held.
1616	 */
1617	ep_rbtree_insert(ep, epi);
1618	if (tep)
1619		mutex_unlock(&tep->mtx);
1620
1621	/*
1622	 * ep_remove_safe() calls in the later error paths can't lead to
1623	 * ep_free() as the ep file itself still holds an ep reference.
1624	 */
1625	ep_get(ep);
1626
1627	/* now check if we've created too many backpaths */
1628	if (unlikely(full_check && reverse_path_check())) {
1629		ep_remove_safe(ep, epi);
1630		return -EINVAL;
1631	}
1632
1633	if (epi->event.events & EPOLLWAKEUP) {
1634		error = ep_create_wakeup_source(epi);
1635		if (error) {
1636			ep_remove_safe(ep, epi);
1637			return error;
1638		}
1639	}
1640
1641	/* Initialize the poll table using the queue callback */
1642	epq.epi = epi;
1643	init_poll_funcptr(&epq.pt, ep_ptable_queue_proc);
1644
1645	/*
1646	 * Attach the item to the poll hooks and get current event bits.
1647	 * We can safely use the file* here because its usage count has
1648	 * been increased by the caller of this function. Note that after
1649	 * this operation completes, the poll callback can start hitting
1650	 * the new item.
1651	 */
1652	revents = ep_item_poll(epi, &epq.pt, 1);
1653
1654	/*
1655	 * We have to check if something went wrong during the poll wait queue
1656	 * install process. Namely an allocation for a wait queue failed due
1657	 * high memory pressure.
1658	 */
1659	if (unlikely(!epq.epi)) {
1660		ep_remove_safe(ep, epi);
1661		return -ENOMEM;
1662	}
1663
1664	/* We have to drop the new item inside our item list to keep track of it */
1665	spin_lock_irq(&ep->lock);
1666
1667	/* record NAPI ID of new item if present */
1668	ep_set_busy_poll_napi_id(epi);
1669
1670	/* If the file is already "ready" we drop it inside the ready list */
1671	if (revents && !ep_is_linked(epi)) {
1672		list_add_tail(&epi->rdllink, &ep->rdllist);
1673		ep_pm_stay_awake(epi);
1674
1675		/* Notify waiting tasks that events are available */
1676		if (waitqueue_active(&ep->wq))
1677			wake_up(&ep->wq);
1678		if (waitqueue_active(&ep->poll_wait))
1679			pwake++;
1680	}
1681
1682	spin_unlock_irq(&ep->lock);
1683
1684	/* We have to call this outside the lock */
1685	if (pwake)
1686		ep_poll_safewake(ep, NULL, 0);
1687
1688	return 0;
1689}
1690
1691/*
1692 * Modify the interest event mask by dropping an event if the new mask
1693 * has a match in the current file status. Must be called with "mtx" held.
1694 */
1695static int ep_modify(struct eventpoll *ep, struct epitem *epi,
1696		     const struct epoll_event *event)
1697{
1698	int pwake = 0;
1699	poll_table pt;
1700
1701	lockdep_assert_irqs_enabled();
1702
1703	init_poll_funcptr(&pt, NULL);
1704
1705	/*
1706	 * Set the new event interest mask before calling f_op->poll();
1707	 * otherwise we might miss an event that happens between the
1708	 * f_op->poll() call and the new event set registering.
1709	 */
1710	epi->event.events = event->events; /* need barrier below */
1711	epi->event.data = event->data; /* protected by mtx */
1712	if (epi->event.events & EPOLLWAKEUP) {
1713		if (!ep_has_wakeup_source(epi))
1714			ep_create_wakeup_source(epi);
1715	} else if (ep_has_wakeup_source(epi)) {
1716		ep_destroy_wakeup_source(epi);
1717	}
1718
1719	/*
1720	 * The following barrier has two effects:
1721	 *
1722	 * 1) Flush epi changes above to other CPUs.  This ensures
1723	 *    we do not miss events from ep_poll_callback if an
1724	 *    event occurs immediately after we call f_op->poll().
1725	 *    We need this because we did not take ep->lock while
1726	 *    changing epi above (but ep_poll_callback does take
1727	 *    ep->lock).
1728	 *
1729	 * 2) We also need to ensure we do not miss _past_ events
1730	 *    when calling f_op->poll().  This barrier also
1731	 *    pairs with the barrier in wq_has_sleeper (see
1732	 *    comments for wq_has_sleeper).
1733	 *
1734	 * This barrier will now guarantee ep_poll_callback or f_op->poll
1735	 * (or both) will notice the readiness of an item.
1736	 */
1737	smp_mb();
1738
1739	/*
1740	 * Get current event bits. We can safely use the file* here because
1741	 * its usage count has been increased by the caller of this function.
1742	 * If the item is "hot" and it is not registered inside the ready
1743	 * list, push it inside.
1744	 */
1745	if (ep_item_poll(epi, &pt, 1)) {
1746		spin_lock_irq(&ep->lock);
1747		if (!ep_is_linked(epi)) {
1748			list_add_tail(&epi->rdllink, &ep->rdllist);
1749			ep_pm_stay_awake(epi);
1750
1751			/* Notify waiting tasks that events are available */
1752			if (waitqueue_active(&ep->wq))
1753				wake_up(&ep->wq);
1754			if (waitqueue_active(&ep->poll_wait))
1755				pwake++;
1756		}
1757		spin_unlock_irq(&ep->lock);
1758	}
1759
1760	/* We have to call this outside the lock */
1761	if (pwake)
1762		ep_poll_safewake(ep, NULL, 0);
1763
1764	return 0;
1765}
1766
1767static int ep_send_events(struct eventpoll *ep,
1768			  struct epoll_event __user *events, int maxevents)
1769{
1770	struct epitem *epi, *tmp;
1771	LIST_HEAD(txlist);
1772	poll_table pt;
1773	int res = 0;
1774
1775	/*
1776	 * Always short-circuit for fatal signals to allow threads to make a
1777	 * timely exit without the chance of finding more events available and
1778	 * fetching repeatedly.
1779	 */
1780	if (fatal_signal_pending(current))
1781		return -EINTR;
1782
1783	init_poll_funcptr(&pt, NULL);
1784
1785	mutex_lock(&ep->mtx);
1786	ep_start_scan(ep, &txlist);
1787
1788	/*
1789	 * We can loop without lock because we are passed a task private list.
1790	 * Items cannot vanish during the loop we are holding ep->mtx.
1791	 */
1792	list_for_each_entry_safe(epi, tmp, &txlist, rdllink) {
1793		struct wakeup_source *ws;
1794		__poll_t revents;
1795
1796		if (res >= maxevents)
1797			break;
1798
1799		/*
1800		 * Activate ep->ws before deactivating epi->ws to prevent
1801		 * triggering auto-suspend here (in case we reactive epi->ws
1802		 * below).
1803		 *
1804		 * This could be rearranged to delay the deactivation of epi->ws
1805		 * instead, but then epi->ws would temporarily be out of sync
1806		 * with ep_is_linked().
1807		 */
1808		ws = ep_wakeup_source(epi);
1809		if (ws) {
1810			if (ws->active)
1811				__pm_stay_awake(ep->ws);
1812			__pm_relax(ws);
1813		}
1814
1815		list_del_init(&epi->rdllink);
1816
1817		/*
1818		 * If the event mask intersect the caller-requested one,
1819		 * deliver the event to userspace. Again, we are holding ep->mtx,
1820		 * so no operations coming from userspace can change the item.
1821		 */
1822		revents = ep_item_poll(epi, &pt, 1);
1823		if (!revents)
1824			continue;
1825
1826		events = epoll_put_uevent(revents, epi->event.data, events);
1827		if (!events) {
1828			list_add(&epi->rdllink, &txlist);
1829			ep_pm_stay_awake(epi);
1830			if (!res)
1831				res = -EFAULT;
1832			break;
1833		}
1834		res++;
1835		if (epi->event.events & EPOLLONESHOT)
1836			epi->event.events &= EP_PRIVATE_BITS;
1837		else if (!(epi->event.events & EPOLLET)) {
1838			/*
1839			 * If this file has been added with Level
1840			 * Trigger mode, we need to insert back inside
1841			 * the ready list, so that the next call to
1842			 * epoll_wait() will check again the events
1843			 * availability. At this point, no one can insert
1844			 * into ep->rdllist besides us. The epoll_ctl()
1845			 * callers are locked out by
1846			 * ep_send_events() holding "mtx" and the
1847			 * poll callback will queue them in ep->ovflist.
1848			 */
1849			list_add_tail(&epi->rdllink, &ep->rdllist);
1850			ep_pm_stay_awake(epi);
1851		}
1852	}
1853	ep_done_scan(ep, &txlist);
1854	mutex_unlock(&ep->mtx);
1855
1856	return res;
1857}
1858
1859static struct timespec64 *ep_timeout_to_timespec(struct timespec64 *to, long ms)
1860{
1861	struct timespec64 now;
1862
1863	if (ms < 0)
1864		return NULL;
1865
1866	if (!ms) {
1867		to->tv_sec = 0;
1868		to->tv_nsec = 0;
1869		return to;
1870	}
1871
1872	to->tv_sec = ms / MSEC_PER_SEC;
1873	to->tv_nsec = NSEC_PER_MSEC * (ms % MSEC_PER_SEC);
1874
1875	ktime_get_ts64(&now);
1876	*to = timespec64_add_safe(now, *to);
1877	return to;
1878}
1879
1880/*
1881 * autoremove_wake_function, but remove even on failure to wake up, because we
1882 * know that default_wake_function/ttwu will only fail if the thread is already
1883 * woken, and in that case the ep_poll loop will remove the entry anyways, not
1884 * try to reuse it.
1885 */
1886static int ep_autoremove_wake_function(struct wait_queue_entry *wq_entry,
1887				       unsigned int mode, int sync, void *key)
1888{
1889	int ret = default_wake_function(wq_entry, mode, sync, key);
1890
1891	/*
1892	 * Pairs with list_empty_careful in ep_poll, and ensures future loop
1893	 * iterations see the cause of this wakeup.
1894	 */
1895	list_del_init_careful(&wq_entry->entry);
1896	return ret;
1897}
1898
1899static int ep_try_send_events(struct eventpoll *ep,
1900			      struct epoll_event __user *events, int maxevents)
1901{
1902	int res;
1903
1904	/*
1905	 * Try to transfer events to user space. In case we get 0 events and
1906	 * there's still timeout left over, we go trying again in search of
1907	 * more luck.
1908	 */
1909	res = ep_send_events(ep, events, maxevents);
1910	if (res > 0)
1911		ep_suspend_napi_irqs(ep);
1912	return res;
1913}
1914
1915static int ep_schedule_timeout(ktime_t *to)
1916{
1917	if (to)
1918		return ktime_after(*to, ktime_get());
1919	else
1920		return 1;
1921}
1922
1923/**
1924 * ep_poll - Retrieves ready events, and delivers them to the caller-supplied
1925 *           event buffer.
1926 *
1927 * @ep: Pointer to the eventpoll context.
1928 * @events: Pointer to the userspace buffer where the ready events should be
1929 *          stored.
1930 * @maxevents: Size (in terms of number of events) of the caller event buffer.
1931 * @timeout: Maximum timeout for the ready events fetch operation, in
1932 *           timespec. If the timeout is zero, the function will not block,
1933 *           while if the @timeout ptr is NULL, the function will block
1934 *           until at least one event has been retrieved (or an error
1935 *           occurred).
1936 *
1937 * Return: the number of ready events which have been fetched, or an
1938 *          error code, in case of error.
1939 */
1940static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
1941		   int maxevents, struct timespec64 *timeout)
1942{
1943	int res, eavail, timed_out = 0;
1944	u64 slack = 0;
1945	wait_queue_entry_t wait;
1946	ktime_t expires, *to = NULL;
1947
1948	lockdep_assert_irqs_enabled();
1949
1950	if (timeout && (timeout->tv_sec | timeout->tv_nsec)) {
1951		slack = select_estimate_accuracy(timeout);
1952		to = &expires;
1953		*to = timespec64_to_ktime(*timeout);
1954	} else if (timeout) {
1955		/*
1956		 * Avoid the unnecessary trip to the wait queue loop, if the
1957		 * caller specified a non blocking operation.
1958		 */
1959		timed_out = 1;
1960	}
1961
1962	/*
1963	 * This call is racy: We may or may not see events that are being added
1964	 * to the ready list under the lock (e.g., in IRQ callbacks). For cases
1965	 * with a non-zero timeout, this thread will check the ready list under
1966	 * lock and will add to the wait queue.  For cases with a zero
1967	 * timeout, the user by definition should not care and will have to
1968	 * recheck again.
1969	 */
1970	eavail = ep_events_available(ep);
1971
1972	while (1) {
1973		if (eavail) {
1974			res = ep_try_send_events(ep, events, maxevents);
1975			if (res)
1976				return res;
1977		}
1978
1979		if (timed_out)
1980			return 0;
1981
1982		eavail = ep_busy_loop(ep);
1983		if (eavail)
1984			continue;
1985
1986		if (signal_pending(current))
1987			return -EINTR;
1988
1989		/*
1990		 * Internally init_wait() uses autoremove_wake_function(),
1991		 * thus wait entry is removed from the wait queue on each
1992		 * wakeup. Why it is important? In case of several waiters
1993		 * each new wakeup will hit the next waiter, giving it the
1994		 * chance to harvest new event. Otherwise wakeup can be
1995		 * lost. This is also good performance-wise, because on
1996		 * normal wakeup path no need to call __remove_wait_queue()
1997		 * explicitly, thus ep->lock is not taken, which halts the
1998		 * event delivery.
1999		 *
2000		 * In fact, we now use an even more aggressive function that
2001		 * unconditionally removes, because we don't reuse the wait
2002		 * entry between loop iterations. This lets us also avoid the
2003		 * performance issue if a process is killed, causing all of its
2004		 * threads to wake up without being removed normally.
2005		 */
2006		init_wait(&wait);
2007		wait.func = ep_autoremove_wake_function;
2008
2009		spin_lock_irq(&ep->lock);
2010		/*
2011		 * Barrierless variant, waitqueue_active() is called under
2012		 * the same lock on wakeup ep_poll_callback() side, so it
2013		 * is safe to avoid an explicit barrier.
2014		 */
2015		__set_current_state(TASK_INTERRUPTIBLE);
2016
2017		/*
2018		 * Do the final check under the lock. ep_start/done_scan()
2019		 * plays with two lists (->rdllist and ->ovflist) and there
2020		 * is always a race when both lists are empty for short
2021		 * period of time although events are pending, so lock is
2022		 * important.
2023		 */
2024		eavail = ep_events_available(ep);
2025		if (!eavail)
2026			__add_wait_queue_exclusive(&ep->wq, &wait);
2027
2028		spin_unlock_irq(&ep->lock);
2029
2030		if (!eavail)
2031			timed_out = !ep_schedule_timeout(to) ||
2032				!schedule_hrtimeout_range(to, slack,
2033							  HRTIMER_MODE_ABS);
2034		__set_current_state(TASK_RUNNING);
2035
2036		/*
2037		 * We were woken up, thus go and try to harvest some events.
2038		 * If timed out and still on the wait queue, recheck eavail
2039		 * carefully under lock, below.
2040		 */
2041		eavail = 1;
2042
2043		if (!list_empty_careful(&wait.entry)) {
2044			spin_lock_irq(&ep->lock);
2045			/*
2046			 * If the thread timed out and is not on the wait queue,
2047			 * it means that the thread was woken up after its
2048			 * timeout expired before it could reacquire the lock.
2049			 * Thus, when wait.entry is empty, it needs to harvest
2050			 * events.
2051			 */
2052			if (timed_out)
2053				eavail = list_empty(&wait.entry);
2054			__remove_wait_queue(&ep->wq, &wait);
2055			spin_unlock_irq(&ep->lock);
2056		}
2057	}
2058}
2059
2060/**
2061 * ep_loop_check_proc - verify that adding an epoll file @ep inside another
2062 *                      epoll file does not create closed loops, and
2063 *                      determine the depth of the subtree starting at @ep
2064 *
2065 * @ep: the &struct eventpoll to be currently checked.
2066 * @depth: Current depth of the path being checked.
2067 *
2068 * Return: depth of the subtree, or a value bigger than EP_MAX_NESTS if we found
2069 * a loop or went too deep.
2070 */
2071static int ep_loop_check_proc(struct eventpoll *ep, int depth)
2072{
2073	int result = 0;
2074	struct rb_node *rbp;
2075	struct epitem *epi;
2076
2077	if (ep->gen == loop_check_gen)
2078		return ep->loop_check_depth;
2079
2080	mutex_lock_nested(&ep->mtx, depth + 1);
2081	ep->gen = loop_check_gen;
2082	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
2083		epi = rb_entry(rbp, struct epitem, rbn);
2084		if (unlikely(is_file_epoll(epi->ffd.file))) {
2085			struct eventpoll *ep_tovisit;
2086			ep_tovisit = epi->ffd.file->private_data;
2087			if (ep_tovisit == inserting_into || depth > EP_MAX_NESTS)
2088				result = EP_MAX_NESTS+1;
2089			else
2090				result = max(result, ep_loop_check_proc(ep_tovisit, depth + 1) + 1);
2091			if (result > EP_MAX_NESTS)
2092				break;
2093		} else {
2094			/*
2095			 * If we've reached a file that is not associated with
2096			 * an ep, then we need to check if the newly added
2097			 * links are going to add too many wakeup paths. We do
2098			 * this by adding it to the tfile_check_list, if it's
2099			 * not already there, and calling reverse_path_check()
2100			 * during ep_insert().
2101			 */
2102			list_file(epi->ffd.file);
2103		}
2104	}
2105	ep->loop_check_depth = result;
2106	mutex_unlock(&ep->mtx);
2107
2108	return result;
2109}
2110
2111/* ep_get_upwards_depth_proc - determine depth of @ep when traversed upwards */
2112static int ep_get_upwards_depth_proc(struct eventpoll *ep, int depth)
2113{
2114	int result = 0;
2115	struct epitem *epi;
2116
2117	if (ep->gen == loop_check_gen)
2118		return ep->loop_check_depth;
2119	hlist_for_each_entry_rcu(epi, &ep->refs, fllink)
2120		result = max(result, ep_get_upwards_depth_proc(epi->ep, depth + 1) + 1);
2121	ep->gen = loop_check_gen;
2122	ep->loop_check_depth = result;
2123	return result;
2124}
2125
2126/**
2127 * ep_loop_check - Performs a check to verify that adding an epoll file (@to)
2128 *                 into another epoll file (represented by @ep) does not create
2129 *                 closed loops or too deep chains.
2130 *
2131 * @ep: Pointer to the epoll we are inserting into.
2132 * @to: Pointer to the epoll to be inserted.
2133 *
2134 * Return: %zero if adding the epoll @to inside the epoll @from
2135 * does not violate the constraints, or %-1 otherwise.
2136 */
2137static int ep_loop_check(struct eventpoll *ep, struct eventpoll *to)
2138{
2139	int depth, upwards_depth;
2140
2141	inserting_into = ep;
2142	/*
2143	 * Check how deep down we can get from @to, and whether it is possible
2144	 * to loop up to @ep.
2145	 */
2146	depth = ep_loop_check_proc(to, 0);
2147	if (depth > EP_MAX_NESTS)
2148		return -1;
2149	/* Check how far up we can go from @ep. */
2150	rcu_read_lock();
2151	upwards_depth = ep_get_upwards_depth_proc(ep, 0);
2152	rcu_read_unlock();
2153
2154	return (depth+1+upwards_depth > EP_MAX_NESTS) ? -1 : 0;
2155}
2156
2157static void clear_tfile_check_list(void)
2158{
2159	rcu_read_lock();
2160	while (tfile_check_list != EP_UNACTIVE_PTR) {
2161		struct epitems_head *head = tfile_check_list;
2162		tfile_check_list = head->next;
2163		unlist_file(head);
2164	}
2165	rcu_read_unlock();
2166}
2167
2168/*
2169 * Open an eventpoll file descriptor.
2170 */
2171static int do_epoll_create(int flags)
2172{
2173	int error;
2174	struct eventpoll *ep;
2175
2176	/* Check the EPOLL_* constant for consistency.  */
2177	BUILD_BUG_ON(EPOLL_CLOEXEC != O_CLOEXEC);
2178
2179	if (flags & ~EPOLL_CLOEXEC)
2180		return -EINVAL;
2181	/*
2182	 * Create the internal data structure ("struct eventpoll").
2183	 */
2184	error = ep_alloc(&ep);
2185	if (error < 0)
2186		return error;
2187	/*
2188	 * Creates all the items needed to setup an eventpoll file. That is,
2189	 * a file structure and a free file descriptor.
2190	 */
2191	FD_PREPARE(fdf, O_RDWR | (flags & O_CLOEXEC),
2192		   anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep,
2193				      O_RDWR | (flags & O_CLOEXEC)));
2194	if (fdf.err) {
2195		ep_clear_and_put(ep);
2196		return fdf.err;
2197	}
2198	ep->file = fd_prepare_file(fdf);
2199	return fd_publish(fdf);
2200}
2201
2202SYSCALL_DEFINE1(epoll_create1, int, flags)
2203{
2204	return do_epoll_create(flags);
2205}
2206
2207SYSCALL_DEFINE1(epoll_create, int, size)
2208{
2209	if (size <= 0)
2210		return -EINVAL;
2211
2212	return do_epoll_create(0);
2213}
2214
2215#ifdef CONFIG_PM_SLEEP
2216static inline void ep_take_care_of_epollwakeup(struct epoll_event *epev)
2217{
2218	if ((epev->events & EPOLLWAKEUP) && !capable(CAP_BLOCK_SUSPEND))
2219		epev->events &= ~EPOLLWAKEUP;
2220}
2221#else
2222static inline void ep_take_care_of_epollwakeup(struct epoll_event *epev)
2223{
2224	epev->events &= ~EPOLLWAKEUP;
2225}
2226#endif
2227
2228static inline int epoll_mutex_lock(struct mutex *mutex, int depth,
2229				   bool nonblock)
2230{
2231	if (!nonblock) {
2232		mutex_lock_nested(mutex, depth);
2233		return 0;
2234	}
2235	if (mutex_trylock(mutex))
2236		return 0;
2237	return -EAGAIN;
2238}
2239
2240int do_epoll_ctl(int epfd, int op, int fd, struct epoll_event *epds,
2241		 bool nonblock)
2242{
2243	int error;
2244	int full_check = 0;
2245	struct eventpoll *ep;
2246	struct epitem *epi;
2247	struct eventpoll *tep = NULL;
2248
2249	CLASS(fd, f)(epfd);
2250	if (fd_empty(f))
2251		return -EBADF;
2252
2253	/* Get the "struct file *" for the target file */
2254	CLASS(fd, tf)(fd);
2255	if (fd_empty(tf))
2256		return -EBADF;
2257
2258	/* The target file descriptor must support poll */
2259	if (!file_can_poll(fd_file(tf)))
2260		return -EPERM;
2261
2262	/* Check if EPOLLWAKEUP is allowed */
2263	if (ep_op_has_event(op))
2264		ep_take_care_of_epollwakeup(epds);
2265
2266	/*
2267	 * We have to check that the file structure underneath the file descriptor
2268	 * the user passed to us _is_ an eventpoll file. And also we do not permit
2269	 * adding an epoll file descriptor inside itself.
2270	 */
2271	error = -EINVAL;
2272	if (fd_file(f) == fd_file(tf) || !is_file_epoll(fd_file(f)))
2273		goto error_tgt_fput;
2274
2275	/*
2276	 * epoll adds to the wakeup queue at EPOLL_CTL_ADD time only,
2277	 * so EPOLLEXCLUSIVE is not allowed for a EPOLL_CTL_MOD operation.
2278	 * Also, we do not currently supported nested exclusive wakeups.
2279	 */
2280	if (ep_op_has_event(op) && (epds->events & EPOLLEXCLUSIVE)) {
2281		if (op == EPOLL_CTL_MOD)
2282			goto error_tgt_fput;
2283		if (op == EPOLL_CTL_ADD && (is_file_epoll(fd_file(tf)) ||
2284				(epds->events & ~EPOLLEXCLUSIVE_OK_BITS)))
2285			goto error_tgt_fput;
2286	}
2287
2288	/*
2289	 * At this point it is safe to assume that the "private_data" contains
2290	 * our own data structure.
2291	 */
2292	ep = fd_file(f)->private_data;
2293
2294	/*
2295	 * When we insert an epoll file descriptor inside another epoll file
2296	 * descriptor, there is the chance of creating closed loops, which are
2297	 * better be handled here, than in more critical paths. While we are
2298	 * checking for loops we also determine the list of files reachable
2299	 * and hang them on the tfile_check_list, so we can check that we
2300	 * haven't created too many possible wakeup paths.
2301	 *
2302	 * We do not need to take the global 'epumutex' on EPOLL_CTL_ADD when
2303	 * the epoll file descriptor is attaching directly to a wakeup source,
2304	 * unless the epoll file descriptor is nested. The purpose of taking the
2305	 * 'epnested_mutex' on add is to prevent complex toplogies such as loops and
2306	 * deep wakeup paths from forming in parallel through multiple
2307	 * EPOLL_CTL_ADD operations.
2308	 */
2309	error = epoll_mutex_lock(&ep->mtx, 0, nonblock);
2310	if (error)
2311		goto error_tgt_fput;
2312	if (op == EPOLL_CTL_ADD) {
2313		if (READ_ONCE(fd_file(f)->f_ep) || ep->gen == loop_check_gen ||
2314		    is_file_epoll(fd_file(tf))) {
2315			mutex_unlock(&ep->mtx);
2316			error = epoll_mutex_lock(&epnested_mutex, 0, nonblock);
2317			if (error)
2318				goto error_tgt_fput;
2319			loop_check_gen++;
2320			full_check = 1;
2321			if (is_file_epoll(fd_file(tf))) {
2322				tep = fd_file(tf)->private_data;
2323				error = -ELOOP;
2324				if (ep_loop_check(ep, tep) != 0)
2325					goto error_tgt_fput;
2326			}
2327			error = epoll_mutex_lock(&ep->mtx, 0, nonblock);
2328			if (error)
2329				goto error_tgt_fput;
2330		}
2331	}
2332
2333	/*
2334	 * Try to lookup the file inside our RB tree. Since we grabbed "mtx"
2335	 * above, we can be sure to be able to use the item looked up by
2336	 * ep_find() till we release the mutex.
2337	 */
2338	epi = ep_find(ep, fd_file(tf), fd);
2339
2340	error = -EINVAL;
2341	switch (op) {
2342	case EPOLL_CTL_ADD:
2343		if (!epi) {
2344			epds->events |= EPOLLERR | EPOLLHUP;
2345			error = ep_insert(ep, epds, fd_file(tf), fd, full_check);
2346		} else
2347			error = -EEXIST;
2348		break;
2349	case EPOLL_CTL_DEL:
2350		if (epi) {
2351			/*
2352			 * The eventpoll itself is still alive: the refcount
2353			 * can't go to zero here.
2354			 */
2355			ep_remove_safe(ep, epi);
2356			error = 0;
2357		} else {
2358			error = -ENOENT;
2359		}
2360		break;
2361	case EPOLL_CTL_MOD:
2362		if (epi) {
2363			if (!(epi->event.events & EPOLLEXCLUSIVE)) {
2364				epds->events |= EPOLLERR | EPOLLHUP;
2365				error = ep_modify(ep, epi, epds);
2366			}
2367		} else
2368			error = -ENOENT;
2369		break;
2370	}
2371	mutex_unlock(&ep->mtx);
2372
2373error_tgt_fput:
2374	if (full_check) {
2375		clear_tfile_check_list();
2376		loop_check_gen++;
2377		mutex_unlock(&epnested_mutex);
2378	}
2379	return error;
2380}
2381
2382/*
2383 * The following function implements the controller interface for
2384 * the eventpoll file that enables the insertion/removal/change of
2385 * file descriptors inside the interest set.
2386 */
2387SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd,
2388		struct epoll_event __user *, event)
2389{
2390	struct epoll_event epds;
2391
2392	if (ep_op_has_event(op) &&
2393	    copy_from_user(&epds, event, sizeof(struct epoll_event)))
2394		return -EFAULT;
2395
2396	return do_epoll_ctl(epfd, op, fd, &epds, false);
2397}
2398
2399static int ep_check_params(struct file *file, struct epoll_event __user *evs,
2400			   int maxevents)
2401{
2402	/* The maximum number of event must be greater than zero */
2403	if (maxevents <= 0 || maxevents > EP_MAX_EVENTS)
2404		return -EINVAL;
2405
2406	/* Verify that the area passed by the user is writeable */
2407	if (!access_ok(evs, maxevents * sizeof(struct epoll_event)))
2408		return -EFAULT;
2409
2410	/*
2411	 * We have to check that the file structure underneath the fd
2412	 * the user passed to us _is_ an eventpoll file.
2413	 */
2414	if (!is_file_epoll(file))
2415		return -EINVAL;
2416
2417	return 0;
2418}
2419
2420int epoll_sendevents(struct file *file, struct epoll_event __user *events,
2421		     int maxevents)
2422{
2423	struct eventpoll *ep;
2424	int ret;
2425
2426	ret = ep_check_params(file, events, maxevents);
2427	if (unlikely(ret))
2428		return ret;
2429
2430	ep = file->private_data;
2431	/*
2432	 * Racy call, but that's ok - it should get retried based on
2433	 * poll readiness anyway.
2434	 */
2435	if (ep_events_available(ep))
2436		return ep_try_send_events(ep, events, maxevents);
2437	return 0;
2438}
2439
2440/*
2441 * Implement the event wait interface for the eventpoll file. It is the kernel
2442 * part of the user space epoll_wait(2).
2443 */
2444static int do_epoll_wait(int epfd, struct epoll_event __user *events,
2445			 int maxevents, struct timespec64 *to)
2446{
2447	struct eventpoll *ep;
2448	int ret;
2449
2450	/* Get the "struct file *" for the eventpoll file */
2451	CLASS(fd, f)(epfd);
2452	if (fd_empty(f))
2453		return -EBADF;
2454
2455	ret = ep_check_params(fd_file(f), events, maxevents);
2456	if (unlikely(ret))
2457		return ret;
2458
2459	/*
2460	 * At this point it is safe to assume that the "private_data" contains
2461	 * our own data structure.
2462	 */
2463	ep = fd_file(f)->private_data;
2464
2465	/* Time to fish for events ... */
2466	return ep_poll(ep, events, maxevents, to);
2467}
2468
2469SYSCALL_DEFINE4(epoll_wait, int, epfd, struct epoll_event __user *, events,
2470		int, maxevents, int, timeout)
2471{
2472	struct timespec64 to;
2473
2474	return do_epoll_wait(epfd, events, maxevents,
2475			     ep_timeout_to_timespec(&to, timeout));
2476}
2477
2478/*
2479 * Implement the event wait interface for the eventpoll file. It is the kernel
2480 * part of the user space epoll_pwait(2).
2481 */
2482static int do_epoll_pwait(int epfd, struct epoll_event __user *events,
2483			  int maxevents, struct timespec64 *to,
2484			  const sigset_t __user *sigmask, size_t sigsetsize)
2485{
2486	int error;
2487
2488	/*
2489	 * If the caller wants a certain signal mask to be set during the wait,
2490	 * we apply it here.
2491	 */
2492	error = set_user_sigmask(sigmask, sigsetsize);
2493	if (error)
2494		return error;
2495
2496	error = do_epoll_wait(epfd, events, maxevents, to);
2497
2498	restore_saved_sigmask_unless(error == -EINTR);
2499
2500	return error;
2501}
2502
2503SYSCALL_DEFINE6(epoll_pwait, int, epfd, struct epoll_event __user *, events,
2504		int, maxevents, int, timeout, const sigset_t __user *, sigmask,
2505		size_t, sigsetsize)
2506{
2507	struct timespec64 to;
2508
2509	return do_epoll_pwait(epfd, events, maxevents,
2510			      ep_timeout_to_timespec(&to, timeout),
2511			      sigmask, sigsetsize);
2512}
2513
2514SYSCALL_DEFINE6(epoll_pwait2, int, epfd, struct epoll_event __user *, events,
2515		int, maxevents, const struct __kernel_timespec __user *, timeout,
2516		const sigset_t __user *, sigmask, size_t, sigsetsize)
2517{
2518	struct timespec64 ts, *to = NULL;
2519
2520	if (timeout) {
2521		if (get_timespec64(&ts, timeout))
2522			return -EFAULT;
2523		to = &ts;
2524		if (poll_select_set_timeout(to, ts.tv_sec, ts.tv_nsec))
2525			return -EINVAL;
2526	}
2527
2528	return do_epoll_pwait(epfd, events, maxevents, to,
2529			      sigmask, sigsetsize);
2530}
2531
2532#ifdef CONFIG_COMPAT
2533static int do_compat_epoll_pwait(int epfd, struct epoll_event __user *events,
2534				 int maxevents, struct timespec64 *timeout,
2535				 const compat_sigset_t __user *sigmask,
2536				 compat_size_t sigsetsize)
2537{
2538	long err;
2539
2540	/*
2541	 * If the caller wants a certain signal mask to be set during the wait,
2542	 * we apply it here.
2543	 */
2544	err = set_compat_user_sigmask(sigmask, sigsetsize);
2545	if (err)
2546		return err;
2547
2548	err = do_epoll_wait(epfd, events, maxevents, timeout);
2549
2550	restore_saved_sigmask_unless(err == -EINTR);
2551
2552	return err;
2553}
2554
2555COMPAT_SYSCALL_DEFINE6(epoll_pwait, int, epfd,
2556		       struct epoll_event __user *, events,
2557		       int, maxevents, int, timeout,
2558		       const compat_sigset_t __user *, sigmask,
2559		       compat_size_t, sigsetsize)
2560{
2561	struct timespec64 to;
2562
2563	return do_compat_epoll_pwait(epfd, events, maxevents,
2564				     ep_timeout_to_timespec(&to, timeout),
2565				     sigmask, sigsetsize);
2566}
2567
2568COMPAT_SYSCALL_DEFINE6(epoll_pwait2, int, epfd,
2569		       struct epoll_event __user *, events,
2570		       int, maxevents,
2571		       const struct __kernel_timespec __user *, timeout,
2572		       const compat_sigset_t __user *, sigmask,
2573		       compat_size_t, sigsetsize)
2574{
2575	struct timespec64 ts, *to = NULL;
2576
2577	if (timeout) {
2578		if (get_timespec64(&ts, timeout))
2579			return -EFAULT;
2580		to = &ts;
2581		if (poll_select_set_timeout(to, ts.tv_sec, ts.tv_nsec))
2582			return -EINVAL;
2583	}
2584
2585	return do_compat_epoll_pwait(epfd, events, maxevents, to,
2586				     sigmask, sigsetsize);
2587}
2588
2589#endif
2590
2591static int __init eventpoll_init(void)
2592{
2593	struct sysinfo si;
2594
2595	si_meminfo(&si);
2596	/*
2597	 * Allows top 4% of lomem to be allocated for epoll watches (per user).
2598	 */
2599	max_user_watches = (((si.totalram - si.totalhigh) / 25) << PAGE_SHIFT) /
2600		EP_ITEM_COST;
2601	BUG_ON(max_user_watches < 0);
2602
2603	/*
2604	 * We can have many thousands of epitems, so prevent this from
2605	 * using an extra cache line on 64-bit (and smaller) CPUs
2606	 */
2607	BUILD_BUG_ON(sizeof(void *) <= 8 && sizeof(struct epitem) > 128);
2608
2609	/* Allocates slab cache used to allocate "struct epitem" items */
2610	epi_cache = kmem_cache_create("eventpoll_epi", sizeof(struct epitem),
2611			0, SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT, NULL);
2612
2613	/* Allocates slab cache used to allocate "struct eppoll_entry" */
2614	pwq_cache = kmem_cache_create("eventpoll_pwq",
2615		sizeof(struct eppoll_entry), 0, SLAB_PANIC|SLAB_ACCOUNT, NULL);
2616	epoll_sysctls_init();
2617
2618	ephead_cache = kmem_cache_create("ep_head",
2619		sizeof(struct epitems_head), 0, SLAB_PANIC|SLAB_ACCOUNT, NULL);
2620
2621	return 0;
2622}
2623fs_initcall(eventpoll_init);