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(s: ephead_cache, objp: 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(lock: &epi->ffd.file->f_lock);
306	if (!hlist_empty(h: &head->epitems))
307	to_free = NULL;
308	head->next = NULL;
309	spin_unlock(lock: &epi->ffd.file->f_lock);
310	}
311	free_ephead(head: 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(head: &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(head: &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 !!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, loop_end: nonblock ? NULL : ep_busy_loop_end,
450	loop_end_arg: 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(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(to: &epoll_params, from: uarg, n: 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(to: uarg, from: &epoll_params, n: 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(f: 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(lock: &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(wq_head: whead, wq_entry: &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(s: pwq_cache, objp: 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(list: &ep->rdllist, head: 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(new: &epi->rdllink, head: &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(list: txlist, head: &ep->rdllist);
760	__pm_relax(ws: ep->ws);
761
762	if (!list_empty(head: &ep->rdllist)) {
763	if (waitqueue_active(wq_head: &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(r: &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(r: &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(lock: &ep->mtx);
790	free_uid(ep->user);
791	wakeup_source_unregister(ws: ep->ws);
792	kfree(objp: 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(lock: &file->f_lock);
818	if (epi->dying && !force) {
819	spin_unlock(lock: &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	file->f_ep = NULL;
827	if (!is_file_epoll(f: file)) {
828	struct epitems_head *v;
829	v = container_of(head, struct epitems_head, epitems);
830	if (!smp_load_acquire(&v->next))
831	to_free = v;
832	}
833	}
834	hlist_del_rcu(n: &epi->fllink);
835	spin_unlock(lock: &file->f_lock);
836	free_ephead(head: to_free);
837
838	rb_erase_cached(node: &epi->rbn, root: &ep->rbr);
839
840	write_lock_irq(&ep->lock);
841	if (ep_is_linked(epi))
842	list_del_init(entry: &epi->rdllink);
843	write_unlock_irq(&ep->lock);
844
845	wakeup_source_unregister(ws: ep_wakeup_source(epi));
846	/*
847	* At this point it is safe to free the eventpoll item. Use the union
848	* field epi->rcu, since we are trying to minimize the size of
849	* 'struct epitem'. The 'rbn' field is no longer in use. Protected by
850	* ep->mtx. The rcu read side, reverse_path_check_proc(), does not make
851	* use of the rbn field.
852	*/
853	kfree_rcu(epi, rcu);
854
855	percpu_counter_dec(fbc: &ep->user->epoll_watches);
856	return ep_refcount_dec_and_test(ep);
857	}
858
859	/*
860	* ep_remove variant for callers owing an additional reference to the ep
861	*/
862	static void ep_remove_safe(struct eventpoll *ep, struct epitem *epi)
863	{
864	WARN_ON_ONCE(__ep_remove(ep, epi, false));
865	}
866
867	static void ep_clear_and_put(struct eventpoll *ep)
868	{
869	struct rb_node *rbp, *next;
870	struct epitem *epi;
871	bool dispose;
872
873	/* We need to release all tasks waiting for these file */
874	if (waitqueue_active(wq_head: &ep->poll_wait))
875	ep_poll_safewake(ep, NULL, pollflags: 0);
876
877	mutex_lock(&ep->mtx);
878
879	/*
880	* Walks through the whole tree by unregistering poll callbacks.
881	*/
882	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
883	epi = rb_entry(rbp, struct epitem, rbn);
884
885	ep_unregister_pollwait(ep, epi);
886	cond_resched();
887	}
888
889	/*
890	* Walks through the whole tree and try to free each "struct epitem".
891	* Note that ep_remove_safe() will not remove the epitem in case of a
892	* racing eventpoll_release_file(); the latter will do the removal.
893	* At this point we are sure no poll callbacks will be lingering around.
894	* Since we still own a reference to the eventpoll struct, the loop can't
895	* dispose it.
896	*/
897	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = next) {
898	next = rb_next(rbp);
899	epi = rb_entry(rbp, struct epitem, rbn);
900	ep_remove_safe(ep, epi);
901	cond_resched();
902	}
903
904	dispose = ep_refcount_dec_and_test(ep);
905	mutex_unlock(lock: &ep->mtx);
906
907	if (dispose)
908	ep_free(ep);
909	}
910
911	static long ep_eventpoll_ioctl(struct file *file, unsigned int cmd,
912	unsigned long arg)
913	{
914	int ret;
915
916	if (!is_file_epoll(f: file))
917	return -EINVAL;
918
919	switch (cmd) {
920	case EPIOCSPARAMS:
921	case EPIOCGPARAMS:
922	ret = ep_eventpoll_bp_ioctl(file, cmd, arg);
923	break;
924	default:
925	ret = -EINVAL;
926	break;
927	}
928
929	return ret;
930	}
931
932	static int ep_eventpoll_release(struct inode *inode, struct file *file)
933	{
934	struct eventpoll *ep = file->private_data;
935
936	if (ep)
937	ep_clear_and_put(ep);
938
939	return 0;
940	}
941
942	static __poll_t ep_item_poll(const struct epitem *epi, poll_table *pt, int depth);
943
944	static __poll_t __ep_eventpoll_poll(struct file *file, poll_table *wait, int depth)
945	{
946	struct eventpoll *ep = file->private_data;
947	LIST_HEAD(txlist);
948	struct epitem *epi, *tmp;
949	poll_table pt;
950	__poll_t res = 0;
951
952	init_poll_funcptr(pt: &pt, NULL);
953
954	/* Insert inside our poll wait queue */
955	poll_wait(filp: file, wait_address: &ep->poll_wait, p: wait);
956
957	/*
958	* Proceed to find out if wanted events are really available inside
959	* the ready list.
960	*/
961	mutex_lock_nested(lock: &ep->mtx, subclass: depth);
962	ep_start_scan(ep, txlist: &txlist);
963	list_for_each_entry_safe(epi, tmp, &txlist, rdllink) {
964	if (ep_item_poll(epi, pt: &pt, depth: depth + 1)) {
965	res = EPOLLIN | EPOLLRDNORM;
966	break;
967	} else {
968	/*
969	* Item has been dropped into the ready list by the poll
970	* callback, but it's not actually ready, as far as
971	* caller requested events goes. We can remove it here.
972	*/
973	__pm_relax(ws: ep_wakeup_source(epi));
974	list_del_init(entry: &epi->rdllink);
975	}
976	}
977	ep_done_scan(ep, txlist: &txlist);
978	mutex_unlock(lock: &ep->mtx);
979	return res;
980	}
981
982	/*
983	* Differs from ep_eventpoll_poll() in that internal callers already have
984	* the ep->mtx so we need to start from depth=1, such that mutex_lock_nested()
985	* is correctly annotated.
986	*/
987	static __poll_t ep_item_poll(const struct epitem *epi, poll_table *pt,
988	int depth)
989	{
990	struct file *file = epi->ffd.file;
991	__poll_t res;
992
993	pt->_key = epi->event.events;
994	if (!is_file_epoll(f: file))
995	res = vfs_poll(file, pt);
996	else
997	res = __ep_eventpoll_poll(file, wait: pt, depth);
998	return res & epi->event.events;
999	}
1000
1001	static __poll_t ep_eventpoll_poll(struct file *file, poll_table *wait)
1002	{
1003	return __ep_eventpoll_poll(file, wait, depth: 0);
1004	}
1005
1006	#ifdef CONFIG_PROC_FS
1007	static void ep_show_fdinfo(struct seq_file *m, struct file *f)
1008	{
1009	struct eventpoll *ep = f->private_data;
1010	struct rb_node *rbp;
1011
1012	mutex_lock(&ep->mtx);
1013	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
1014	struct epitem *epi = rb_entry(rbp, struct epitem, rbn);
1015	struct inode *inode = file_inode(f: epi->ffd.file);
1016
1017	seq_printf(m, fmt: "tfd: %8d events: %8x data: %16llx "
1018	" pos:%lli ino:%lx sdev:%x\n",
1019	epi->ffd.fd, epi->event.events,
1020	(long long)epi->event.data,
1021	(long long)epi->ffd.file->f_pos,
1022	inode->i_ino, inode->i_sb->s_dev);
1023	if (seq_has_overflowed(m))
1024	break;
1025	}
1026	mutex_unlock(lock: &ep->mtx);
1027	}
1028	#endif
1029
1030	/* File callbacks that implement the eventpoll file behaviour */
1031	static const struct file_operations eventpoll_fops = {
1032	#ifdef CONFIG_PROC_FS
1033	.show_fdinfo = ep_show_fdinfo,
1034	#endif
1035	.release = ep_eventpoll_release,
1036	.poll = ep_eventpoll_poll,
1037	.llseek = noop_llseek,
1038	.unlocked_ioctl = ep_eventpoll_ioctl,
1039	.compat_ioctl = compat_ptr_ioctl,
1040	};
1041
1042	/*
1043	* This is called from eventpoll_release() to unlink files from the eventpoll
1044	* interface. We need to have this facility to cleanup correctly files that are
1045	* closed without being removed from the eventpoll interface.
1046	*/
1047	void eventpoll_release_file(struct file *file)
1048	{
1049	struct eventpoll *ep;
1050	struct epitem *epi;
1051	bool dispose;
1052
1053	/*
1054	* Use the 'dying' flag to prevent a concurrent ep_clear_and_put() from
1055	* touching the epitems list before eventpoll_release_file() can access
1056	* the ep->mtx.
1057	*/
1058	again:
1059	spin_lock(lock: &file->f_lock);
1060	if (file->f_ep && file->f_ep->first) {
1061	epi = hlist_entry(file->f_ep->first, struct epitem, fllink);
1062	epi->dying = true;
1063	spin_unlock(lock: &file->f_lock);
1064
1065	/*
1066	* ep access is safe as we still own a reference to the ep
1067	* struct
1068	*/
1069	ep = epi->ep;
1070	mutex_lock(&ep->mtx);
1071	dispose = __ep_remove(ep, epi, force: true);
1072	mutex_unlock(lock: &ep->mtx);
1073
1074	if (dispose)
1075	ep_free(ep);
1076	goto again;
1077	}
1078	spin_unlock(lock: &file->f_lock);
1079	}
1080
1081	static int ep_alloc(struct eventpoll **pep)
1082	{
1083	struct eventpoll *ep;
1084
1085	ep = kzalloc(size: sizeof(*ep), GFP_KERNEL);
1086	if (unlikely(!ep))
1087	return -ENOMEM;
1088
1089	mutex_init(&ep->mtx);
1090	rwlock_init(&ep->lock);
1091	init_waitqueue_head(&ep->wq);
1092	init_waitqueue_head(&ep->poll_wait);
1093	INIT_LIST_HEAD(list: &ep->rdllist);
1094	ep->rbr = RB_ROOT_CACHED;
1095	ep->ovflist = EP_UNACTIVE_PTR;
1096	ep->user = get_current_user();
1097	refcount_set(r: &ep->refcount, n: 1);
1098
1099	*pep = ep;
1100
1101	return 0;
1102	}
1103
1104	/*
1105	* Search the file inside the eventpoll tree. The RB tree operations
1106	* are protected by the "mtx" mutex, and ep_find() must be called with
1107	* "mtx" held.
1108	*/
1109	static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
1110	{
1111	int kcmp;
1112	struct rb_node *rbp;
1113	struct epitem *epi, *epir = NULL;
1114	struct epoll_filefd ffd;
1115
1116	ep_set_ffd(ffd: &ffd, file, fd);
1117	for (rbp = ep->rbr.rb_root.rb_node; rbp; ) {
1118	epi = rb_entry(rbp, struct epitem, rbn);
1119	kcmp = ep_cmp_ffd(p1: &ffd, p2: &epi->ffd);
1120	if (kcmp > 0)
1121	rbp = rbp->rb_right;
1122	else if (kcmp < 0)
1123	rbp = rbp->rb_left;
1124	else {
1125	epir = epi;
1126	break;
1127	}
1128	}
1129
1130	return epir;
1131	}
1132
1133	#ifdef CONFIG_KCMP
1134	static struct epitem *ep_find_tfd(struct eventpoll *ep, int tfd, unsigned long toff)
1135	{
1136	struct rb_node *rbp;
1137	struct epitem *epi;
1138
1139	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
1140	epi = rb_entry(rbp, struct epitem, rbn);
1141	if (epi->ffd.fd == tfd) {
1142	if (toff == 0)
1143	return epi;
1144	else
1145	toff--;
1146	}
1147	cond_resched();
1148	}
1149
1150	return NULL;
1151	}
1152
1153	struct file *get_epoll_tfile_raw_ptr(struct file *file, int tfd,
1154	unsigned long toff)
1155	{
1156	struct file *file_raw;
1157	struct eventpoll *ep;
1158	struct epitem *epi;
1159
1160	if (!is_file_epoll(f: file))
1161	return ERR_PTR(error: -EINVAL);
1162
1163	ep = file->private_data;
1164
1165	mutex_lock(&ep->mtx);
1166	epi = ep_find_tfd(ep, tfd, toff);
1167	if (epi)
1168	file_raw = epi->ffd.file;
1169	else
1170	file_raw = ERR_PTR(error: -ENOENT);
1171	mutex_unlock(lock: &ep->mtx);
1172
1173	return file_raw;
1174	}
1175	#endif /* CONFIG_KCMP */
1176
1177	/*
1178	* Adds a new entry to the tail of the list in a lockless way, i.e.
1179	* multiple CPUs are allowed to call this function concurrently.
1180	*
1181	* Beware: it is necessary to prevent any other modifications of the
1182	* existing list until all changes are completed, in other words
1183	* concurrent list_add_tail_lockless() calls should be protected
1184	* with a read lock, where write lock acts as a barrier which
1185	* makes sure all list_add_tail_lockless() calls are fully
1186	* completed.
1187	*
1188	* Also an element can be locklessly added to the list only in one
1189	* direction i.e. either to the tail or to the head, otherwise
1190	* concurrent access will corrupt the list.
1191	*
1192	* Return: %false if element has been already added to the list, %true
1193	* otherwise.
1194	*/
1195	static inline bool list_add_tail_lockless(struct list_head *new,
1196	struct list_head *head)
1197	{
1198	struct list_head *prev;
1199
1200	/*
1201	* This is simple 'new->next = head' operation, but cmpxchg()
1202	* is used in order to detect that same element has been just
1203	* added to the list from another CPU: the winner observes
1204	* new->next == new.
1205	*/
1206	if (!try_cmpxchg(&new->next, &new, head))
1207	return false;
1208
1209	/*
1210	* Initially ->next of a new element must be updated with the head
1211	* (we are inserting to the tail) and only then pointers are atomically
1212	* exchanged. XCHG guarantees memory ordering, thus ->next should be
1213	* updated before pointers are actually swapped and pointers are
1214	* swapped before prev->next is updated.
1215	*/
1216
1217	prev = xchg(&head->prev, new);
1218
1219	/*
1220	* It is safe to modify prev->next and new->prev, because a new element
1221	* is added only to the tail and new->next is updated before XCHG.
1222	*/
1223
1224	prev->next = new;
1225	new->prev = prev;
1226
1227	return true;
1228	}
1229
1230	/*
1231	* Chains a new epi entry to the tail of the ep->ovflist in a lockless way,
1232	* i.e. multiple CPUs are allowed to call this function concurrently.
1233	*
1234	* Return: %false if epi element has been already chained, %true otherwise.
1235	*/
1236	static inline bool chain_epi_lockless(struct epitem *epi)
1237	{
1238	struct eventpoll *ep = epi->ep;
1239
1240	/* Fast preliminary check */
1241	if (epi->next != EP_UNACTIVE_PTR)
1242	return false;
1243
1244	/* Check that the same epi has not been just chained from another CPU */
1245	if (cmpxchg(&epi->next, EP_UNACTIVE_PTR, NULL) != EP_UNACTIVE_PTR)
1246	return false;
1247
1248	/* Atomically exchange tail */
1249	epi->next = xchg(&ep->ovflist, epi);
1250
1251	return true;
1252	}
1253
1254	/*
1255	* This is the callback that is passed to the wait queue wakeup
1256	* mechanism. It is called by the stored file descriptors when they
1257	* have events to report.
1258	*
1259	* This callback takes a read lock in order not to contend with concurrent
1260	* events from another file descriptor, thus all modifications to ->rdllist
1261	* or ->ovflist are lockless. Read lock is paired with the write lock from
1262	* ep_start/done_scan(), which stops all list modifications and guarantees
1263	* that lists state is seen correctly.
1264	*
1265	* Another thing worth to mention is that ep_poll_callback() can be called
1266	* concurrently for the same @epi from different CPUs if poll table was inited
1267	* with several wait queues entries. Plural wakeup from different CPUs of a
1268	* single wait queue is serialized by wq.lock, but the case when multiple wait
1269	* queues are used should be detected accordingly. This is detected using
1270	* cmpxchg() operation.
1271	*/
1272	static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key)
1273	{
1274	int pwake = 0;
1275	struct epitem *epi = ep_item_from_wait(p: wait);
1276	struct eventpoll *ep = epi->ep;
1277	__poll_t pollflags = key_to_poll(key);
1278	unsigned long flags;
1279	int ewake = 0;
1280
1281	read_lock_irqsave(&ep->lock, flags);
1282
1283	ep_set_busy_poll_napi_id(epi);
1284
1285	/*
1286	* If the event mask does not contain any poll(2) event, we consider the
1287	* descriptor to be disabled. This condition is likely the effect of the
1288	* EPOLLONESHOT bit that disables the descriptor when an event is received,
1289	* until the next EPOLL_CTL_MOD will be issued.
1290	*/
1291	if (!(epi->event.events & ~EP_PRIVATE_BITS))
1292	goto out_unlock;
1293
1294	/*
1295	* Check the events coming with the callback. At this stage, not
1296	* every device reports the events in the "key" parameter of the
1297	* callback. We need to be able to handle both cases here, hence the
1298	* test for "key" != NULL before the event match test.
1299	*/
1300	if (pollflags && !(pollflags & epi->event.events))
1301	goto out_unlock;
1302
1303	/*
1304	* If we are transferring events to userspace, we can hold no locks
1305	* (because we're accessing user memory, and because of linux f_op->poll()
1306	* semantics). All the events that happen during that period of time are
1307	* chained in ep->ovflist and requeued later on.
1308	*/
1309	if (READ_ONCE(ep->ovflist) != EP_UNACTIVE_PTR) {
1310	if (chain_epi_lockless(epi))
1311	ep_pm_stay_awake_rcu(epi);
1312	} else if (!ep_is_linked(epi)) {
1313	/* In the usual case, add event to ready list. */
1314	if (list_add_tail_lockless(new: &epi->rdllink, head: &ep->rdllist))
1315	ep_pm_stay_awake_rcu(epi);
1316	}
1317
1318	/*
1319	* Wake up ( if active ) both the eventpoll wait list and the ->poll()
1320	* wait list.
1321	*/
1322	if (waitqueue_active(wq_head: &ep->wq)) {
1323	if ((epi->event.events & EPOLLEXCLUSIVE) &&
1324	!(pollflags & POLLFREE)) {
1325	switch (pollflags & EPOLLINOUT_BITS) {
1326	case EPOLLIN:
1327	if (epi->event.events & EPOLLIN)
1328	ewake = 1;
1329	break;
1330	case EPOLLOUT:
1331	if (epi->event.events & EPOLLOUT)
1332	ewake = 1;
1333	break;
1334	case 0:
1335	ewake = 1;
1336	break;
1337	}
1338	}
1339	wake_up(&ep->wq);
1340	}
1341	if (waitqueue_active(wq_head: &ep->poll_wait))
1342	pwake++;
1343
1344	out_unlock:
1345	read_unlock_irqrestore(&ep->lock, flags);
1346
1347	/* We have to call this outside the lock */
1348	if (pwake)
1349	ep_poll_safewake(ep, epi, pollflags: pollflags & EPOLL_URING_WAKE);
1350
1351	if (!(epi->event.events & EPOLLEXCLUSIVE))
1352	ewake = 1;
1353
1354	if (pollflags & POLLFREE) {
1355	/*
1356	* If we race with ep_remove_wait_queue() it can miss
1357	* ->whead = NULL and do another remove_wait_queue() after
1358	* us, so we can't use __remove_wait_queue().
1359	*/
1360	list_del_init(entry: &wait->entry);
1361	/*
1362	* ->whead != NULL protects us from the race with
1363	* ep_clear_and_put() or ep_remove(), ep_remove_wait_queue()
1364	* takes whead->lock held by the caller. Once we nullify it,
1365	* nothing protects ep/epi or even wait.
1366	*/
1367	smp_store_release(&ep_pwq_from_wait(wait)->whead, NULL);
1368	}
1369
1370	return ewake;
1371	}
1372
1373	/*
1374	* This is the callback that is used to add our wait queue to the
1375	* target file wakeup lists.
1376	*/
1377	static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
1378	poll_table *pt)
1379	{
1380	struct ep_pqueue *epq = container_of(pt, struct ep_pqueue, pt);
1381	struct epitem *epi = epq->epi;
1382	struct eppoll_entry *pwq;
1383
1384	if (unlikely(!epi)) // an earlier allocation has failed
1385	return;
1386
1387	pwq = kmem_cache_alloc(cachep: pwq_cache, GFP_KERNEL);
1388	if (unlikely(!pwq)) {
1389	epq->epi = NULL;
1390	return;
1391	}
1392
1393	init_waitqueue_func_entry(wq_entry: &pwq->wait, func: ep_poll_callback);
1394	pwq->whead = whead;
1395	pwq->base = epi;
1396	if (epi->event.events & EPOLLEXCLUSIVE)
1397	add_wait_queue_exclusive(wq_head: whead, wq_entry: &pwq->wait);
1398	else
1399	add_wait_queue(wq_head: whead, wq_entry: &pwq->wait);
1400	pwq->next = epi->pwqlist;
1401	epi->pwqlist = pwq;
1402	}
1403
1404	static void ep_rbtree_insert(struct eventpoll *ep, struct epitem *epi)
1405	{
1406	int kcmp;
1407	struct rb_node **p = &ep->rbr.rb_root.rb_node, *parent = NULL;
1408	struct epitem *epic;
1409	bool leftmost = true;
1410
1411	while (*p) {
1412	parent = *p;
1413	epic = rb_entry(parent, struct epitem, rbn);
1414	kcmp = ep_cmp_ffd(p1: &epi->ffd, p2: &epic->ffd);
1415	if (kcmp > 0) {
1416	p = &parent->rb_right;
1417	leftmost = false;
1418	} else
1419	p = &parent->rb_left;
1420	}
1421	rb_link_node(node: &epi->rbn, parent, rb_link: p);
1422	rb_insert_color_cached(node: &epi->rbn, root: &ep->rbr, leftmost);
1423	}
1424
1425
1426
1427	#define PATH_ARR_SIZE 5
1428	/*
1429	* These are the number paths of length 1 to 5, that we are allowing to emanate
1430	* from a single file of interest. For example, we allow 1000 paths of length
1431	* 1, to emanate from each file of interest. This essentially represents the
1432	* potential wakeup paths, which need to be limited in order to avoid massive
1433	* uncontrolled wakeup storms. The common use case should be a single ep which
1434	* is connected to n file sources. In this case each file source has 1 path
1435	* of length 1. Thus, the numbers below should be more than sufficient. These
1436	* path limits are enforced during an EPOLL_CTL_ADD operation, since a modify
1437	* and delete can't add additional paths. Protected by the epnested_mutex.
1438	*/
1439	static const int path_limits[PATH_ARR_SIZE] = { 1000, 500, 100, 50, 10 };
1440	static int path_count[PATH_ARR_SIZE];
1441
1442	static int path_count_inc(int nests)
1443	{
1444	/* Allow an arbitrary number of depth 1 paths */
1445	if (nests == 0)
1446	return 0;
1447
1448	if (++path_count[nests] > path_limits[nests])
1449	return -1;
1450	return 0;
1451	}
1452
1453	static void path_count_init(void)
1454	{
1455	int i;
1456
1457	for (i = 0; i < PATH_ARR_SIZE; i++)
1458	path_count[i] = 0;
1459	}
1460
1461	static int reverse_path_check_proc(struct hlist_head *refs, int depth)
1462	{
1463	int error = 0;
1464	struct epitem *epi;
1465
1466	if (depth > EP_MAX_NESTS) /* too deep nesting */
1467	return -1;
1468
1469	/* CTL_DEL can remove links here, but that can't increase our count */
1470	hlist_for_each_entry_rcu(epi, refs, fllink) {
1471	struct hlist_head *refs = &epi->ep->refs;
1472	if (hlist_empty(h: refs))
1473	error = path_count_inc(nests: depth);
1474	else
1475	error = reverse_path_check_proc(refs, depth: depth + 1);
1476	if (error != 0)
1477	break;
1478	}
1479	return error;
1480	}
1481
1482	/**
1483	* reverse_path_check - The tfile_check_list is list of epitem_head, which have
1484	* links that are proposed to be newly added. We need to
1485	* make sure that those added links don't add too many
1486	* paths such that we will spend all our time waking up
1487	* eventpoll objects.
1488	*
1489	* Return: %zero if the proposed links don't create too many paths,
1490	* %-1 otherwise.
1491	*/
1492	static int reverse_path_check(void)
1493	{
1494	struct epitems_head *p;
1495
1496	for (p = tfile_check_list; p != EP_UNACTIVE_PTR; p = p->next) {
1497	int error;
1498	path_count_init();
1499	rcu_read_lock();
1500	error = reverse_path_check_proc(refs: &p->epitems, depth: 0);
1501	rcu_read_unlock();
1502	if (error)
1503	return error;
1504	}
1505	return 0;
1506	}
1507
1508	static int ep_create_wakeup_source(struct epitem *epi)
1509	{
1510	struct name_snapshot n;
1511	struct wakeup_source *ws;
1512
1513	if (!epi->ep->ws) {
1514	epi->ep->ws = wakeup_source_register(NULL, name: "eventpoll");
1515	if (!epi->ep->ws)
1516	return -ENOMEM;
1517	}
1518
1519	take_dentry_name_snapshot(&n, epi->ffd.file->f_path.dentry);
1520	ws = wakeup_source_register(NULL, name: n.name.name);
1521	release_dentry_name_snapshot(&n);
1522
1523	if (!ws)
1524	return -ENOMEM;
1525	rcu_assign_pointer(epi->ws, ws);
1526
1527	return 0;
1528	}
1529
1530	/* rare code path, only used when EPOLL_CTL_MOD removes a wakeup source */
1531	static noinline void ep_destroy_wakeup_source(struct epitem *epi)
1532	{
1533	struct wakeup_source *ws = ep_wakeup_source(epi);
1534
1535	RCU_INIT_POINTER(epi->ws, NULL);
1536
1537	/*
1538	* wait for ep_pm_stay_awake_rcu to finish, synchronize_rcu is
1539	* used internally by wakeup_source_remove, too (called by
1540	* wakeup_source_unregister), so we cannot use call_rcu
1541	*/
1542	synchronize_rcu();
1543	wakeup_source_unregister(ws);
1544	}
1545
1546	static int attach_epitem(struct file *file, struct epitem *epi)
1547	{
1548	struct epitems_head *to_free = NULL;
1549	struct hlist_head *head = NULL;
1550	struct eventpoll *ep = NULL;
1551
1552	if (is_file_epoll(f: file))
1553	ep = file->private_data;
1554
1555	if (ep) {
1556	head = &ep->refs;
1557	} else if (!READ_ONCE(file->f_ep)) {
1558	allocate:
1559	to_free = kmem_cache_zalloc(k: ephead_cache, GFP_KERNEL);
1560	if (!to_free)
1561	return -ENOMEM;
1562	head = &to_free->epitems;
1563	}
1564	spin_lock(lock: &file->f_lock);
1565	if (!file->f_ep) {
1566	if (unlikely(!head)) {
1567	spin_unlock(lock: &file->f_lock);
1568	goto allocate;
1569	}
1570	file->f_ep = head;
1571	to_free = NULL;
1572	}
1573	hlist_add_head_rcu(n: &epi->fllink, h: file->f_ep);
1574	spin_unlock(lock: &file->f_lock);
1575	free_ephead(head: to_free);
1576	return 0;
1577	}
1578
1579	/*
1580	* Must be called with "mtx" held.
1581	*/
1582	static int ep_insert(struct eventpoll *ep, const struct epoll_event *event,
1583	struct file *tfile, int fd, int full_check)
1584	{
1585	int error, pwake = 0;
1586	__poll_t revents;
1587	struct epitem *epi;
1588	struct ep_pqueue epq;
1589	struct eventpoll *tep = NULL;
1590
1591	if (is_file_epoll(f: tfile))
1592	tep = tfile->private_data;
1593
1594	lockdep_assert_irqs_enabled();
1595
1596	if (unlikely(percpu_counter_compare(&ep->user->epoll_watches,
1597	max_user_watches) >= 0))
1598	return -ENOSPC;
1599	percpu_counter_inc(fbc: &ep->user->epoll_watches);
1600
1601	if (!(epi = kmem_cache_zalloc(k: epi_cache, GFP_KERNEL))) {
1602	percpu_counter_dec(fbc: &ep->user->epoll_watches);
1603	return -ENOMEM;
1604	}
1605
1606	/* Item initialization follow here ... */
1607	INIT_LIST_HEAD(list: &epi->rdllink);
1608	epi->ep = ep;
1609	ep_set_ffd(ffd: &epi->ffd, file: tfile, fd);
1610	epi->event = *event;
1611	epi->next = EP_UNACTIVE_PTR;
1612
1613	if (tep)
1614	mutex_lock_nested(lock: &tep->mtx, subclass: 1);
1615	/* Add the current item to the list of active epoll hook for this file */
1616	if (unlikely(attach_epitem(tfile, epi) < 0)) {
1617	if (tep)
1618	mutex_unlock(lock: &tep->mtx);
1619	kmem_cache_free(s: epi_cache, objp: epi);
1620	percpu_counter_dec(fbc: &ep->user->epoll_watches);
1621	return -ENOMEM;
1622	}
1623
1624	if (full_check && !tep)
1625	list_file(file: tfile);
1626
1627	/*
1628	* Add the current item to the RB tree. All RB tree operations are
1629	* protected by "mtx", and ep_insert() is called with "mtx" held.
1630	*/
1631	ep_rbtree_insert(ep, epi);
1632	if (tep)
1633	mutex_unlock(lock: &tep->mtx);
1634
1635	/*
1636	* ep_remove_safe() calls in the later error paths can't lead to
1637	* ep_free() as the ep file itself still holds an ep reference.
1638	*/
1639	ep_get(ep);
1640
1641	/* now check if we've created too many backpaths */
1642	if (unlikely(full_check && reverse_path_check())) {
1643	ep_remove_safe(ep, epi);
1644	return -EINVAL;
1645	}
1646
1647	if (epi->event.events & EPOLLWAKEUP) {
1648	error = ep_create_wakeup_source(epi);
1649	if (error) {
1650	ep_remove_safe(ep, epi);
1651	return error;
1652	}
1653	}
1654
1655	/* Initialize the poll table using the queue callback */
1656	epq.epi = epi;
1657	init_poll_funcptr(pt: &epq.pt, qproc: ep_ptable_queue_proc);
1658
1659	/*
1660	* Attach the item to the poll hooks and get current event bits.
1661	* We can safely use the file* here because its usage count has
1662	* been increased by the caller of this function. Note that after
1663	* this operation completes, the poll callback can start hitting
1664	* the new item.
1665	*/
1666	revents = ep_item_poll(epi, pt: &epq.pt, depth: 1);
1667
1668	/*
1669	* We have to check if something went wrong during the poll wait queue
1670	* install process. Namely an allocation for a wait queue failed due
1671	* high memory pressure.
1672	*/
1673	if (unlikely(!epq.epi)) {
1674	ep_remove_safe(ep, epi);
1675	return -ENOMEM;
1676	}
1677
1678	/* We have to drop the new item inside our item list to keep track of it */
1679	write_lock_irq(&ep->lock);
1680
1681	/* record NAPI ID of new item if present */
1682	ep_set_busy_poll_napi_id(epi);
1683
1684	/* If the file is already "ready" we drop it inside the ready list */
1685	if (revents && !ep_is_linked(epi)) {
1686	list_add_tail(new: &epi->rdllink, head: &ep->rdllist);
1687	ep_pm_stay_awake(epi);
1688
1689	/* Notify waiting tasks that events are available */
1690	if (waitqueue_active(wq_head: &ep->wq))
1691	wake_up(&ep->wq);
1692	if (waitqueue_active(wq_head: &ep->poll_wait))
1693	pwake++;
1694	}
1695
1696	write_unlock_irq(&ep->lock);
1697
1698	/* We have to call this outside the lock */
1699	if (pwake)
1700	ep_poll_safewake(ep, NULL, pollflags: 0);
1701
1702	return 0;
1703	}
1704
1705	/*
1706	* Modify the interest event mask by dropping an event if the new mask
1707	* has a match in the current file status. Must be called with "mtx" held.
1708	*/
1709	static int ep_modify(struct eventpoll *ep, struct epitem *epi,
1710	const struct epoll_event *event)
1711	{
1712	int pwake = 0;
1713	poll_table pt;
1714
1715	lockdep_assert_irqs_enabled();
1716
1717	init_poll_funcptr(pt: &pt, NULL);
1718
1719	/*
1720	* Set the new event interest mask before calling f_op->poll();
1721	* otherwise we might miss an event that happens between the
1722	* f_op->poll() call and the new event set registering.
1723	*/
1724	epi->event.events = event->events; /* need barrier below */
1725	epi->event.data = event->data; /* protected by mtx */
1726	if (epi->event.events & EPOLLWAKEUP) {
1727	if (!ep_has_wakeup_source(epi))
1728	ep_create_wakeup_source(epi);
1729	} else if (ep_has_wakeup_source(epi)) {
1730	ep_destroy_wakeup_source(epi);
1731	}
1732
1733	/*
1734	* The following barrier has two effects:
1735	*
1736	* 1) Flush epi changes above to other CPUs. This ensures
1737	* we do not miss events from ep_poll_callback if an
1738	* event occurs immediately after we call f_op->poll().
1739	* We need this because we did not take ep->lock while
1740	* changing epi above (but ep_poll_callback does take
1741	* ep->lock).
1742	*
1743	* 2) We also need to ensure we do not miss _past_ events
1744	* when calling f_op->poll(). This barrier also
1745	* pairs with the barrier in wq_has_sleeper (see
1746	* comments for wq_has_sleeper).
1747	*
1748	* This barrier will now guarantee ep_poll_callback or f_op->poll
1749	* (or both) will notice the readiness of an item.
1750	*/
1751	smp_mb();
1752
1753	/*
1754	* Get current event bits. We can safely use the file* here because
1755	* its usage count has been increased by the caller of this function.
1756	* If the item is "hot" and it is not registered inside the ready
1757	* list, push it inside.
1758	*/
1759	if (ep_item_poll(epi, pt: &pt, depth: 1)) {
1760	write_lock_irq(&ep->lock);
1761	if (!ep_is_linked(epi)) {
1762	list_add_tail(new: &epi->rdllink, head: &ep->rdllist);
1763	ep_pm_stay_awake(epi);
1764
1765	/* Notify waiting tasks that events are available */
1766	if (waitqueue_active(wq_head: &ep->wq))
1767	wake_up(&ep->wq);
1768	if (waitqueue_active(wq_head: &ep->poll_wait))
1769	pwake++;
1770	}
1771	write_unlock_irq(&ep->lock);
1772	}
1773
1774	/* We have to call this outside the lock */
1775	if (pwake)
1776	ep_poll_safewake(ep, NULL, pollflags: 0);
1777
1778	return 0;
1779	}
1780
1781	static int ep_send_events(struct eventpoll *ep,
1782	struct epoll_event __user *events, int maxevents)
1783	{
1784	struct epitem *epi, *tmp;
1785	LIST_HEAD(txlist);
1786	poll_table pt;
1787	int res = 0;
1788
1789	/*
1790	* Always short-circuit for fatal signals to allow threads to make a
1791	* timely exit without the chance of finding more events available and
1792	* fetching repeatedly.
1793	*/
1794	if (fatal_signal_pending(current))
1795	return -EINTR;
1796
1797	init_poll_funcptr(pt: &pt, NULL);
1798
1799	mutex_lock(&ep->mtx);
1800	ep_start_scan(ep, txlist: &txlist);
1801
1802	/*
1803	* We can loop without lock because we are passed a task private list.
1804	* Items cannot vanish during the loop we are holding ep->mtx.
1805	*/
1806	list_for_each_entry_safe(epi, tmp, &txlist, rdllink) {
1807	struct wakeup_source *ws;
1808	__poll_t revents;
1809
1810	if (res >= maxevents)
1811	break;
1812
1813	/*
1814	* Activate ep->ws before deactivating epi->ws to prevent
1815	* triggering auto-suspend here (in case we reactive epi->ws
1816	* below).
1817	*
1818	* This could be rearranged to delay the deactivation of epi->ws
1819	* instead, but then epi->ws would temporarily be out of sync
1820	* with ep_is_linked().
1821	*/
1822	ws = ep_wakeup_source(epi);
1823	if (ws) {
1824	if (ws->active)
1825	__pm_stay_awake(ws: ep->ws);
1826	__pm_relax(ws);
1827	}
1828
1829	list_del_init(entry: &epi->rdllink);
1830
1831	/*
1832	* If the event mask intersect the caller-requested one,
1833	* deliver the event to userspace. Again, we are holding ep->mtx,
1834	* so no operations coming from userspace can change the item.
1835	*/
1836	revents = ep_item_poll(epi, pt: &pt, depth: 1);
1837	if (!revents)
1838	continue;
1839
1840	events = epoll_put_uevent(revents, data: epi->event.data, uevent: events);
1841	if (!events) {
1842	list_add(new: &epi->rdllink, head: &txlist);
1843	ep_pm_stay_awake(epi);
1844	if (!res)
1845	res = -EFAULT;
1846	break;
1847	}
1848	res++;
1849	if (epi->event.events & EPOLLONESHOT)
1850	epi->event.events &= EP_PRIVATE_BITS;
1851	else if (!(epi->event.events & EPOLLET)) {
1852	/*
1853	* If this file has been added with Level
1854	* Trigger mode, we need to insert back inside
1855	* the ready list, so that the next call to
1856	* epoll_wait() will check again the events
1857	* availability. At this point, no one can insert
1858	* into ep->rdllist besides us. The epoll_ctl()
1859	* callers are locked out by
1860	* ep_send_events() holding "mtx" and the
1861	* poll callback will queue them in ep->ovflist.
1862	*/
1863	list_add_tail(new: &epi->rdllink, head: &ep->rdllist);
1864	ep_pm_stay_awake(epi);
1865	}
1866	}
1867	ep_done_scan(ep, txlist: &txlist);
1868	mutex_unlock(lock: &ep->mtx);
1869
1870	return res;
1871	}
1872
1873	static struct timespec64 *ep_timeout_to_timespec(struct timespec64 *to, long ms)
1874	{
1875	struct timespec64 now;
1876
1877	if (ms < 0)
1878	return NULL;
1879
1880	if (!ms) {
1881	to->tv_sec = 0;
1882	to->tv_nsec = 0;
1883	return to;
1884	}
1885
1886	to->tv_sec = ms / MSEC_PER_SEC;
1887	to->tv_nsec = NSEC_PER_MSEC * (ms % MSEC_PER_SEC);
1888
1889	ktime_get_ts64(ts: &now);
1890	*to = timespec64_add_safe(lhs: now, rhs: *to);
1891	return to;
1892	}
1893
1894	/*
1895	* autoremove_wake_function, but remove even on failure to wake up, because we
1896	* know that default_wake_function/ttwu will only fail if the thread is already
1897	* woken, and in that case the ep_poll loop will remove the entry anyways, not
1898	* try to reuse it.
1899	*/
1900	static int ep_autoremove_wake_function(struct wait_queue_entry *wq_entry,
1901	unsigned int mode, int sync, void *key)
1902	{
1903	int ret = default_wake_function(wq_entry, mode, flags: sync, key);
1904
1905	/*
1906	* Pairs with list_empty_careful in ep_poll, and ensures future loop
1907	* iterations see the cause of this wakeup.
1908	*/
1909	list_del_init_careful(entry: &wq_entry->entry);
1910	return ret;
1911	}
1912
1913	/**
1914	* ep_poll - Retrieves ready events, and delivers them to the caller-supplied
1915	* event buffer.
1916	*
1917	* @ep: Pointer to the eventpoll context.
1918	* @events: Pointer to the userspace buffer where the ready events should be
1919	* stored.
1920	* @maxevents: Size (in terms of number of events) of the caller event buffer.
1921	* @timeout: Maximum timeout for the ready events fetch operation, in
1922	* timespec. If the timeout is zero, the function will not block,
1923	* while if the @timeout ptr is NULL, the function will block
1924	* until at least one event has been retrieved (or an error
1925	* occurred).
1926	*
1927	* Return: the number of ready events which have been fetched, or an
1928	* error code, in case of error.
1929	*/
1930	static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events,
1931	int maxevents, struct timespec64 *timeout)
1932	{
1933	int res, eavail, timed_out = 0;
1934	u64 slack = 0;
1935	wait_queue_entry_t wait;
1936	ktime_t expires, *to = NULL;
1937
1938	lockdep_assert_irqs_enabled();
1939
1940	if (timeout && (timeout->tv_sec | timeout->tv_nsec)) {
1941	slack = select_estimate_accuracy(tv: timeout);
1942	to = &expires;
1943	*to = timespec64_to_ktime(ts: *timeout);
1944	} else if (timeout) {
1945	/*
1946	* Avoid the unnecessary trip to the wait queue loop, if the
1947	* caller specified a non blocking operation.
1948	*/
1949	timed_out = 1;
1950	}
1951
1952	/*
1953	* This call is racy: We may or may not see events that are being added
1954	* to the ready list under the lock (e.g., in IRQ callbacks). For cases
1955	* with a non-zero timeout, this thread will check the ready list under
1956	* lock and will add to the wait queue. For cases with a zero
1957	* timeout, the user by definition should not care and will have to
1958	* recheck again.
1959	*/
1960	eavail = ep_events_available(ep);
1961
1962	while (1) {
1963	if (eavail) {
1964	/*
1965	* Try to transfer events to user space. In case we get
1966	* 0 events and there's still timeout left over, we go
1967	* trying again in search of more luck.
1968	*/
1969	res = ep_send_events(ep, events, maxevents);
1970	if (res)
1971	return res;
1972	}
1973
1974	if (timed_out)
1975	return 0;
1976
1977	eavail = ep_busy_loop(ep, nonblock: timed_out);
1978	if (eavail)
1979	continue;
1980
1981	if (signal_pending(current))
1982	return -EINTR;
1983
1984	/*
1985	* Internally init_wait() uses autoremove_wake_function(),
1986	* thus wait entry is removed from the wait queue on each
1987	* wakeup. Why it is important? In case of several waiters
1988	* each new wakeup will hit the next waiter, giving it the
1989	* chance to harvest new event. Otherwise wakeup can be
1990	* lost. This is also good performance-wise, because on
1991	* normal wakeup path no need to call __remove_wait_queue()
1992	* explicitly, thus ep->lock is not taken, which halts the
1993	* event delivery.
1994	*
1995	* In fact, we now use an even more aggressive function that
1996	* unconditionally removes, because we don't reuse the wait
1997	* entry between loop iterations. This lets us also avoid the
1998	* performance issue if a process is killed, causing all of its
1999	* threads to wake up without being removed normally.
2000	*/
2001	init_wait(&wait);
2002	wait.func = ep_autoremove_wake_function;
2003
2004	write_lock_irq(&ep->lock);
2005	/*
2006	* Barrierless variant, waitqueue_active() is called under
2007	* the same lock on wakeup ep_poll_callback() side, so it
2008	* is safe to avoid an explicit barrier.
2009	*/
2010	__set_current_state(TASK_INTERRUPTIBLE);
2011
2012	/*
2013	* Do the final check under the lock. ep_start/done_scan()
2014	* plays with two lists (->rdllist and ->ovflist) and there
2015	* is always a race when both lists are empty for short
2016	* period of time although events are pending, so lock is
2017	* important.
2018	*/
2019	eavail = ep_events_available(ep);
2020	if (!eavail)
2021	__add_wait_queue_exclusive(wq_head: &ep->wq, wq_entry: &wait);
2022
2023	write_unlock_irq(&ep->lock);
2024
2025	if (!eavail)
2026	timed_out = !schedule_hrtimeout_range(expires: to, delta: slack,
2027	mode: HRTIMER_MODE_ABS);
2028	__set_current_state(TASK_RUNNING);
2029
2030	/*
2031	* We were woken up, thus go and try to harvest some events.
2032	* If timed out and still on the wait queue, recheck eavail
2033	* carefully under lock, below.
2034	*/
2035	eavail = 1;
2036
2037	if (!list_empty_careful(head: &wait.entry)) {
2038	write_lock_irq(&ep->lock);
2039	/*
2040	* If the thread timed out and is not on the wait queue,
2041	* it means that the thread was woken up after its
2042	* timeout expired before it could reacquire the lock.
2043	* Thus, when wait.entry is empty, it needs to harvest
2044	* events.
2045	*/
2046	if (timed_out)
2047	eavail = list_empty(head: &wait.entry);
2048	__remove_wait_queue(wq_head: &ep->wq, wq_entry: &wait);
2049	write_unlock_irq(&ep->lock);
2050	}
2051	}
2052	}
2053
2054	/**
2055	* ep_loop_check_proc - verify that adding an epoll file inside another
2056	* epoll structure does not violate the constraints, in
2057	* terms of closed loops, or too deep chains (which can
2058	* result in excessive stack usage).
2059	*
2060	* @ep: the &struct eventpoll to be currently checked.
2061	* @depth: Current depth of the path being checked.
2062	*
2063	* Return: %zero if adding the epoll @file inside current epoll
2064	* structure @ep does not violate the constraints, or %-1 otherwise.
2065	*/
2066	static int ep_loop_check_proc(struct eventpoll *ep, int depth)
2067	{
2068	int error = 0;
2069	struct rb_node *rbp;
2070	struct epitem *epi;
2071
2072	mutex_lock_nested(lock: &ep->mtx, subclass: depth + 1);
2073	ep->gen = loop_check_gen;
2074	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
2075	epi = rb_entry(rbp, struct epitem, rbn);
2076	if (unlikely(is_file_epoll(epi->ffd.file))) {
2077	struct eventpoll *ep_tovisit;
2078	ep_tovisit = epi->ffd.file->private_data;
2079	if (ep_tovisit->gen == loop_check_gen)
2080	continue;
2081	if (ep_tovisit == inserting_into || depth > EP_MAX_NESTS)
2082	error = -1;
2083	else
2084	error = ep_loop_check_proc(ep: ep_tovisit, depth: depth + 1);
2085	if (error != 0)
2086	break;
2087	} else {
2088	/*
2089	* If we've reached a file that is not associated with
2090	* an ep, then we need to check if the newly added
2091	* links are going to add too many wakeup paths. We do
2092	* this by adding it to the tfile_check_list, if it's
2093	* not already there, and calling reverse_path_check()
2094	* during ep_insert().
2095	*/
2096	list_file(file: epi->ffd.file);
2097	}
2098	}
2099	mutex_unlock(lock: &ep->mtx);
2100
2101	return error;
2102	}
2103
2104	/**
2105	* ep_loop_check - Performs a check to verify that adding an epoll file (@to)
2106	* into another epoll file (represented by @ep) does not create
2107	* closed loops or too deep chains.
2108	*
2109	* @ep: Pointer to the epoll we are inserting into.
2110	* @to: Pointer to the epoll to be inserted.
2111	*
2112	* Return: %zero if adding the epoll @to inside the epoll @from
2113	* does not violate the constraints, or %-1 otherwise.
2114	*/
2115	static int ep_loop_check(struct eventpoll *ep, struct eventpoll *to)
2116	{
2117	inserting_into = ep;
2118	return ep_loop_check_proc(ep: to, depth: 0);
2119	}
2120
2121	static void clear_tfile_check_list(void)
2122	{
2123	rcu_read_lock();
2124	while (tfile_check_list != EP_UNACTIVE_PTR) {
2125	struct epitems_head *head = tfile_check_list;
2126	tfile_check_list = head->next;
2127	unlist_file(head);
2128	}
2129	rcu_read_unlock();
2130	}
2131
2132	/*
2133	* Open an eventpoll file descriptor.
2134	*/
2135	static int do_epoll_create(int flags)
2136	{
2137	int error, fd;
2138	struct eventpoll *ep = NULL;
2139	struct file *file;
2140
2141	/* Check the EPOLL_* constant for consistency. */
2142	BUILD_BUG_ON(EPOLL_CLOEXEC != O_CLOEXEC);
2143
2144	if (flags & ~EPOLL_CLOEXEC)
2145	return -EINVAL;
2146	/*
2147	* Create the internal data structure ("struct eventpoll").
2148	*/
2149	error = ep_alloc(pep: &ep);
2150	if (error < 0)
2151	return error;
2152	/*
2153	* Creates all the items needed to setup an eventpoll file. That is,
2154	* a file structure and a free file descriptor.
2155	*/
2156	fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC));
2157	if (fd < 0) {
2158	error = fd;
2159	goto out_free_ep;
2160	}
2161	file = anon_inode_getfile(name: "[eventpoll]", fops: &eventpoll_fops, priv: ep,
2162	O_RDWR | (flags & O_CLOEXEC));
2163	if (IS_ERR(ptr: file)) {
2164	error = PTR_ERR(ptr: file);
2165	goto out_free_fd;
2166	}
2167	#ifdef CONFIG_NET_RX_BUSY_POLL
2168	ep->busy_poll_usecs = 0;
2169	ep->busy_poll_budget = 0;
2170	ep->prefer_busy_poll = false;
2171	#endif
2172	ep->file = file;
2173	fd_install(fd, file);
2174	return fd;
2175
2176	out_free_fd:
2177	put_unused_fd(fd);
2178	out_free_ep:
2179	ep_clear_and_put(ep);
2180	return error;
2181	}
2182
2183	SYSCALL_DEFINE1(epoll_create1, int, flags)
2184	{
2185	return do_epoll_create(flags);
2186	}
2187
2188	SYSCALL_DEFINE1(epoll_create, int, size)
2189	{
2190	if (size <= 0)
2191	return -EINVAL;
2192
2193	return do_epoll_create(flags: 0);
2194	}
2195
2196	#ifdef CONFIG_PM_SLEEP
2197	static inline void ep_take_care_of_epollwakeup(struct epoll_event *epev)
2198	{
2199	if ((epev->events & EPOLLWAKEUP) && !capable(CAP_BLOCK_SUSPEND))
2200	epev->events &= ~EPOLLWAKEUP;
2201	}
2202	#else
2203	static inline void ep_take_care_of_epollwakeup(struct epoll_event *epev)
2204	{
2205	epev->events &= ~EPOLLWAKEUP;
2206	}
2207	#endif
2208
2209	static inline int epoll_mutex_lock(struct mutex *mutex, int depth,
2210	bool nonblock)
2211	{
2212	if (!nonblock) {
2213	mutex_lock_nested(lock: mutex, subclass: depth);
2214	return 0;
2215	}
2216	if (mutex_trylock(lock: mutex))
2217	return 0;
2218	return -EAGAIN;
2219	}
2220
2221	int do_epoll_ctl(int epfd, int op, int fd, struct epoll_event *epds,
2222	bool nonblock)
2223	{
2224	int error;
2225	int full_check = 0;
2226	struct fd f, tf;
2227	struct eventpoll *ep;
2228	struct epitem *epi;
2229	struct eventpoll *tep = NULL;
2230
2231	error = -EBADF;
2232	f = fdget(fd: epfd);
2233	if (!f.file)
2234	goto error_return;
2235
2236	/* Get the "struct file *" for the target file */
2237	tf = fdget(fd);
2238	if (!tf.file)
2239	goto error_fput;
2240
2241	/* The target file descriptor must support poll */
2242	error = -EPERM;
2243	if (!file_can_poll(file: tf.file))
2244	goto error_tgt_fput;
2245
2246	/* Check if EPOLLWAKEUP is allowed */
2247	if (ep_op_has_event(op))
2248	ep_take_care_of_epollwakeup(epev: epds);
2249
2250	/*
2251	* We have to check that the file structure underneath the file descriptor
2252	* the user passed to us _is_ an eventpoll file. And also we do not permit
2253	* adding an epoll file descriptor inside itself.
2254	*/
2255	error = -EINVAL;
2256	if (f.file == tf.file || !is_file_epoll(f: f.file))
2257	goto error_tgt_fput;
2258
2259	/*
2260	* epoll adds to the wakeup queue at EPOLL_CTL_ADD time only,
2261	* so EPOLLEXCLUSIVE is not allowed for a EPOLL_CTL_MOD operation.
2262	* Also, we do not currently supported nested exclusive wakeups.
2263	*/
2264	if (ep_op_has_event(op) && (epds->events & EPOLLEXCLUSIVE)) {
2265	if (op == EPOLL_CTL_MOD)
2266	goto error_tgt_fput;
2267	if (op == EPOLL_CTL_ADD && (is_file_epoll(f: tf.file) ||
2268	(epds->events & ~EPOLLEXCLUSIVE_OK_BITS)))
2269	goto error_tgt_fput;
2270	}
2271
2272	/*
2273	* At this point it is safe to assume that the "private_data" contains
2274	* our own data structure.
2275	*/
2276	ep = f.file->private_data;
2277
2278	/*
2279	* When we insert an epoll file descriptor inside another epoll file
2280	* descriptor, there is the chance of creating closed loops, which are
2281	* better be handled here, than in more critical paths. While we are
2282	* checking for loops we also determine the list of files reachable
2283	* and hang them on the tfile_check_list, so we can check that we
2284	* haven't created too many possible wakeup paths.
2285	*
2286	* We do not need to take the global 'epumutex' on EPOLL_CTL_ADD when
2287	* the epoll file descriptor is attaching directly to a wakeup source,
2288	* unless the epoll file descriptor is nested. The purpose of taking the
2289	* 'epnested_mutex' on add is to prevent complex toplogies such as loops and
2290	* deep wakeup paths from forming in parallel through multiple
2291	* EPOLL_CTL_ADD operations.
2292	*/
2293	error = epoll_mutex_lock(mutex: &ep->mtx, depth: 0, nonblock);
2294	if (error)
2295	goto error_tgt_fput;
2296	if (op == EPOLL_CTL_ADD) {
2297	if (READ_ONCE(f.file->f_ep) || ep->gen == loop_check_gen ||
2298	is_file_epoll(f: tf.file)) {
2299	mutex_unlock(lock: &ep->mtx);
2300	error = epoll_mutex_lock(mutex: &epnested_mutex, depth: 0, nonblock);
2301	if (error)
2302	goto error_tgt_fput;
2303	loop_check_gen++;
2304	full_check = 1;
2305	if (is_file_epoll(f: tf.file)) {
2306	tep = tf.file->private_data;
2307	error = -ELOOP;
2308	if (ep_loop_check(ep, to: tep) != 0)
2309	goto error_tgt_fput;
2310	}
2311	error = epoll_mutex_lock(mutex: &ep->mtx, depth: 0, nonblock);
2312	if (error)
2313	goto error_tgt_fput;
2314	}
2315	}
2316
2317	/*
2318	* Try to lookup the file inside our RB tree. Since we grabbed "mtx"
2319	* above, we can be sure to be able to use the item looked up by
2320	* ep_find() till we release the mutex.
2321	*/
2322	epi = ep_find(ep, file: tf.file, fd);
2323
2324	error = -EINVAL;
2325	switch (op) {
2326	case EPOLL_CTL_ADD:
2327	if (!epi) {
2328	epds->events |= EPOLLERR | EPOLLHUP;
2329	error = ep_insert(ep, event: epds, tfile: tf.file, fd, full_check);
2330	} else
2331	error = -EEXIST;
2332	break;
2333	case EPOLL_CTL_DEL:
2334	if (epi) {
2335	/*
2336	* The eventpoll itself is still alive: the refcount
2337	* can't go to zero here.
2338	*/
2339	ep_remove_safe(ep, epi);
2340	error = 0;
2341	} else {
2342	error = -ENOENT;
2343	}
2344	break;
2345	case EPOLL_CTL_MOD:
2346	if (epi) {
2347	if (!(epi->event.events & EPOLLEXCLUSIVE)) {
2348	epds->events |= EPOLLERR | EPOLLHUP;
2349	error = ep_modify(ep, epi, event: epds);
2350	}
2351	} else
2352	error = -ENOENT;
2353	break;
2354	}
2355	mutex_unlock(lock: &ep->mtx);
2356
2357	error_tgt_fput:
2358	if (full_check) {
2359	clear_tfile_check_list();
2360	loop_check_gen++;
2361	mutex_unlock(lock: &epnested_mutex);
2362	}
2363
2364	fdput(fd: tf);
2365	error_fput:
2366	fdput(fd: f);
2367	error_return:
2368
2369	return error;
2370	}
2371
2372	/*
2373	* The following function implements the controller interface for
2374	* the eventpoll file that enables the insertion/removal/change of
2375	* file descriptors inside the interest set.
2376	*/
2377	SYSCALL_DEFINE4(epoll_ctl, int, epfd, int, op, int, fd,
2378	struct epoll_event __user *, event)
2379	{
2380	struct epoll_event epds;
2381
2382	if (ep_op_has_event(op) &&
2383	copy_from_user(to: &epds, from: event, n: sizeof(struct epoll_event)))
2384	return -EFAULT;
2385
2386	return do_epoll_ctl(epfd, op, fd, epds: &epds, nonblock: false);
2387	}
2388
2389	/*
2390	* Implement the event wait interface for the eventpoll file. It is the kernel
2391	* part of the user space epoll_wait(2).
2392	*/
2393	static int do_epoll_wait(int epfd, struct epoll_event __user *events,
2394	int maxevents, struct timespec64 *to)
2395	{
2396	int error;
2397	struct fd f;
2398	struct eventpoll *ep;
2399
2400	/* The maximum number of event must be greater than zero */
2401	if (maxevents <= 0 || maxevents > EP_MAX_EVENTS)
2402	return -EINVAL;
2403
2404	/* Verify that the area passed by the user is writeable */
2405	if (!access_ok(events, maxevents * sizeof(struct epoll_event)))
2406	return -EFAULT;
2407
2408	/* Get the "struct file *" for the eventpoll file */
2409	f = fdget(fd: epfd);
2410	if (!f.file)
2411	return -EBADF;
2412
2413	/*
2414	* We have to check that the file structure underneath the fd
2415	* the user passed to us _is_ an eventpoll file.
2416	*/
2417	error = -EINVAL;
2418	if (!is_file_epoll(f: f.file))
2419	goto error_fput;
2420
2421	/*
2422	* At this point it is safe to assume that the "private_data" contains
2423	* our own data structure.
2424	*/
2425	ep = f.file->private_data;
2426
2427	/* Time to fish for events ... */
2428	error = ep_poll(ep, events, maxevents, timeout: to);
2429
2430	error_fput:
2431	fdput(fd: f);
2432	return error;
2433	}
2434
2435	SYSCALL_DEFINE4(epoll_wait, int, epfd, struct epoll_event __user *, events,
2436	int, maxevents, int, timeout)
2437	{
2438	struct timespec64 to;
2439
2440	return do_epoll_wait(epfd, events, maxevents,
2441	to: ep_timeout_to_timespec(to: &to, ms: timeout));
2442	}
2443
2444	/*
2445	* Implement the event wait interface for the eventpoll file. It is the kernel
2446	* part of the user space epoll_pwait(2).
2447	*/
2448	static int do_epoll_pwait(int epfd, struct epoll_event __user *events,
2449	int maxevents, struct timespec64 *to,
2450	const sigset_t __user *sigmask, size_t sigsetsize)
2451	{
2452	int error;
2453
2454	/*
2455	* If the caller wants a certain signal mask to be set during the wait,
2456	* we apply it here.
2457	*/
2458	error = set_user_sigmask(umask: sigmask, sigsetsize);
2459	if (error)
2460	return error;
2461
2462	error = do_epoll_wait(epfd, events, maxevents, to);
2463
2464	restore_saved_sigmask_unless(interrupted: error == -EINTR);
2465
2466	return error;
2467	}
2468
2469	SYSCALL_DEFINE6(epoll_pwait, int, epfd, struct epoll_event __user *, events,
2470	int, maxevents, int, timeout, const sigset_t __user *, sigmask,
2471	size_t, sigsetsize)
2472	{
2473	struct timespec64 to;
2474
2475	return do_epoll_pwait(epfd, events, maxevents,
2476	to: ep_timeout_to_timespec(to: &to, ms: timeout),
2477	sigmask, sigsetsize);
2478	}
2479
2480	SYSCALL_DEFINE6(epoll_pwait2, int, epfd, struct epoll_event __user *, events,
2481	int, maxevents, const struct __kernel_timespec __user *, timeout,
2482	const sigset_t __user *, sigmask, size_t, sigsetsize)
2483	{
2484	struct timespec64 ts, *to = NULL;
2485
2486	if (timeout) {
2487	if (get_timespec64(ts: &ts, uts: timeout))
2488	return -EFAULT;
2489	to = &ts;
2490	if (poll_select_set_timeout(to, sec: ts.tv_sec, nsec: ts.tv_nsec))
2491	return -EINVAL;
2492	}
2493
2494	return do_epoll_pwait(epfd, events, maxevents, to,
2495	sigmask, sigsetsize);
2496	}
2497
2498	#ifdef CONFIG_COMPAT
2499	static int do_compat_epoll_pwait(int epfd, struct epoll_event __user *events,
2500	int maxevents, struct timespec64 *timeout,
2501	const compat_sigset_t __user *sigmask,
2502	compat_size_t sigsetsize)
2503	{
2504	long err;
2505
2506	/*
2507	* If the caller wants a certain signal mask to be set during the wait,
2508	* we apply it here.
2509	*/
2510	err = set_compat_user_sigmask(umask: sigmask, sigsetsize);
2511	if (err)
2512	return err;
2513
2514	err = do_epoll_wait(epfd, events, maxevents, to: timeout);
2515
2516	restore_saved_sigmask_unless(interrupted: err == -EINTR);
2517
2518	return err;
2519	}
2520
2521	COMPAT_SYSCALL_DEFINE6(epoll_pwait, int, epfd,
2522	struct epoll_event __user *, events,
2523	int, maxevents, int, timeout,
2524	const compat_sigset_t __user *, sigmask,
2525	compat_size_t, sigsetsize)
2526	{
2527	struct timespec64 to;
2528
2529	return do_compat_epoll_pwait(epfd, events, maxevents,
2530	timeout: ep_timeout_to_timespec(to: &to, ms: timeout),
2531	sigmask, sigsetsize);
2532	}
2533
2534	COMPAT_SYSCALL_DEFINE6(epoll_pwait2, int, epfd,
2535	struct epoll_event __user *, events,
2536	int, maxevents,
2537	const struct __kernel_timespec __user *, timeout,
2538	const compat_sigset_t __user *, sigmask,
2539	compat_size_t, sigsetsize)
2540	{
2541	struct timespec64 ts, *to = NULL;
2542
2543	if (timeout) {
2544	if (get_timespec64(ts: &ts, uts: timeout))
2545	return -EFAULT;
2546	to = &ts;
2547	if (poll_select_set_timeout(to, sec: ts.tv_sec, nsec: ts.tv_nsec))
2548	return -EINVAL;
2549	}
2550
2551	return do_compat_epoll_pwait(epfd, events, maxevents, timeout: to,
2552	sigmask, sigsetsize);
2553	}
2554
2555	#endif
2556
2557	static int __init eventpoll_init(void)
2558	{
2559	struct sysinfo si;
2560
2561	si_meminfo(val: &si);
2562	/*
2563	* Allows top 4% of lomem to be allocated for epoll watches (per user).
2564	*/
2565	max_user_watches = (((si.totalram - si.totalhigh) / 25) << PAGE_SHIFT) /
2566	EP_ITEM_COST;
2567	BUG_ON(max_user_watches < 0);
2568
2569	/*
2570	* We can have many thousands of epitems, so prevent this from
2571	* using an extra cache line on 64-bit (and smaller) CPUs
2572	*/
2573	BUILD_BUG_ON(sizeof(void *) <= 8 && sizeof(struct epitem) > 128);
2574
2575	/* Allocates slab cache used to allocate "struct epitem" items */
2576	epi_cache = kmem_cache_create(name: "eventpoll_epi", size: sizeof(struct epitem),
2577	align: 0, SLAB_HWCACHE_ALIGN|SLAB_PANIC|SLAB_ACCOUNT, NULL);
2578
2579	/* Allocates slab cache used to allocate "struct eppoll_entry" */
2580	pwq_cache = kmem_cache_create(name: "eventpoll_pwq",
2581	size: sizeof(struct eppoll_entry), align: 0, SLAB_PANIC|SLAB_ACCOUNT, NULL);
2582	epoll_sysctls_init();
2583
2584	ephead_cache = kmem_cache_create(name: "ep_head",
2585	size: sizeof(struct epitems_head), align: 0, SLAB_PANIC|SLAB_ACCOUNT, NULL);
2586
2587	return 0;
2588	}
2589	fs_initcall(eventpoll_init);
2590