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