xref: /freebsd/sys/kern/kern_event.c (revision 64a0982bee3db2236df43357e70ce8dddbc21d48)
1 /*-
2  * Copyright (c) 1999,2000,2001 Jonathan Lemon <jlemon@FreeBSD.org>
3  * Copyright 2004 John-Mark Gurney <jmg@FreeBSD.org>
4  * Copyright (c) 2009 Apple, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26  * SUCH DAMAGE.
27  */
28 
29 #include <sys/cdefs.h>
30 __FBSDID("$FreeBSD$");
31 
32 #include "opt_ktrace.h"
33 #include "opt_kqueue.h"
34 
35 #include <sys/param.h>
36 #include <sys/systm.h>
37 #include <sys/capsicum.h>
38 #include <sys/kernel.h>
39 #include <sys/lock.h>
40 #include <sys/mutex.h>
41 #include <sys/rwlock.h>
42 #include <sys/proc.h>
43 #include <sys/malloc.h>
44 #include <sys/unistd.h>
45 #include <sys/file.h>
46 #include <sys/filedesc.h>
47 #include <sys/filio.h>
48 #include <sys/fcntl.h>
49 #include <sys/kthread.h>
50 #include <sys/selinfo.h>
51 #include <sys/queue.h>
52 #include <sys/event.h>
53 #include <sys/eventvar.h>
54 #include <sys/poll.h>
55 #include <sys/protosw.h>
56 #include <sys/resourcevar.h>
57 #include <sys/sigio.h>
58 #include <sys/signalvar.h>
59 #include <sys/socket.h>
60 #include <sys/socketvar.h>
61 #include <sys/stat.h>
62 #include <sys/sysctl.h>
63 #include <sys/sysproto.h>
64 #include <sys/syscallsubr.h>
65 #include <sys/taskqueue.h>
66 #include <sys/uio.h>
67 #include <sys/user.h>
68 #ifdef KTRACE
69 #include <sys/ktrace.h>
70 #endif
71 #include <machine/atomic.h>
72 
73 #include <vm/uma.h>
74 
75 static MALLOC_DEFINE(M_KQUEUE, "kqueue", "memory for kqueue system");
76 
77 /*
78  * This lock is used if multiple kq locks are required.  This possibly
79  * should be made into a per proc lock.
80  */
81 static struct mtx	kq_global;
82 MTX_SYSINIT(kq_global, &kq_global, "kqueue order", MTX_DEF);
83 #define KQ_GLOBAL_LOCK(lck, haslck)	do {	\
84 	if (!haslck)				\
85 		mtx_lock(lck);			\
86 	haslck = 1;				\
87 } while (0)
88 #define KQ_GLOBAL_UNLOCK(lck, haslck)	do {	\
89 	if (haslck)				\
90 		mtx_unlock(lck);			\
91 	haslck = 0;				\
92 } while (0)
93 
94 TASKQUEUE_DEFINE_THREAD(kqueue_ctx);
95 
96 static int	kevent_copyout(void *arg, struct kevent *kevp, int count);
97 static int	kevent_copyin(void *arg, struct kevent *kevp, int count);
98 static int	kqueue_register(struct kqueue *kq, struct kevent *kev,
99 		    struct thread *td, int waitok);
100 static int	kqueue_acquire(struct file *fp, struct kqueue **kqp);
101 static void	kqueue_release(struct kqueue *kq, int locked);
102 static void	kqueue_destroy(struct kqueue *kq);
103 static void	kqueue_drain(struct kqueue *kq, struct thread *td);
104 static int	kqueue_expand(struct kqueue *kq, struct filterops *fops,
105 		    uintptr_t ident, int waitok);
106 static void	kqueue_task(void *arg, int pending);
107 static int	kqueue_scan(struct kqueue *kq, int maxevents,
108 		    struct kevent_copyops *k_ops,
109 		    const struct timespec *timeout,
110 		    struct kevent *keva, struct thread *td);
111 static void 	kqueue_wakeup(struct kqueue *kq);
112 static struct filterops *kqueue_fo_find(int filt);
113 static void	kqueue_fo_release(int filt);
114 
115 static fo_ioctl_t	kqueue_ioctl;
116 static fo_poll_t	kqueue_poll;
117 static fo_kqfilter_t	kqueue_kqfilter;
118 static fo_stat_t	kqueue_stat;
119 static fo_close_t	kqueue_close;
120 static fo_fill_kinfo_t	kqueue_fill_kinfo;
121 
122 static struct fileops kqueueops = {
123 	.fo_read = invfo_rdwr,
124 	.fo_write = invfo_rdwr,
125 	.fo_truncate = invfo_truncate,
126 	.fo_ioctl = kqueue_ioctl,
127 	.fo_poll = kqueue_poll,
128 	.fo_kqfilter = kqueue_kqfilter,
129 	.fo_stat = kqueue_stat,
130 	.fo_close = kqueue_close,
131 	.fo_chmod = invfo_chmod,
132 	.fo_chown = invfo_chown,
133 	.fo_sendfile = invfo_sendfile,
134 	.fo_fill_kinfo = kqueue_fill_kinfo,
135 };
136 
137 static int 	knote_attach(struct knote *kn, struct kqueue *kq);
138 static void 	knote_drop(struct knote *kn, struct thread *td);
139 static void 	knote_drop_detached(struct knote *kn, struct thread *td);
140 static void 	knote_enqueue(struct knote *kn);
141 static void 	knote_dequeue(struct knote *kn);
142 static void 	knote_init(void);
143 static struct 	knote *knote_alloc(int waitok);
144 static void 	knote_free(struct knote *kn);
145 
146 static void	filt_kqdetach(struct knote *kn);
147 static int	filt_kqueue(struct knote *kn, long hint);
148 static int	filt_procattach(struct knote *kn);
149 static void	filt_procdetach(struct knote *kn);
150 static int	filt_proc(struct knote *kn, long hint);
151 static int	filt_fileattach(struct knote *kn);
152 static void	filt_timerexpire(void *knx);
153 static int	filt_timerattach(struct knote *kn);
154 static void	filt_timerdetach(struct knote *kn);
155 static int	filt_timer(struct knote *kn, long hint);
156 static int	filt_userattach(struct knote *kn);
157 static void	filt_userdetach(struct knote *kn);
158 static int	filt_user(struct knote *kn, long hint);
159 static void	filt_usertouch(struct knote *kn, struct kevent *kev,
160 		    u_long type);
161 
162 static struct filterops file_filtops = {
163 	.f_isfd = 1,
164 	.f_attach = filt_fileattach,
165 };
166 static struct filterops kqread_filtops = {
167 	.f_isfd = 1,
168 	.f_detach = filt_kqdetach,
169 	.f_event = filt_kqueue,
170 };
171 /* XXX - move to kern_proc.c?  */
172 static struct filterops proc_filtops = {
173 	.f_isfd = 0,
174 	.f_attach = filt_procattach,
175 	.f_detach = filt_procdetach,
176 	.f_event = filt_proc,
177 };
178 static struct filterops timer_filtops = {
179 	.f_isfd = 0,
180 	.f_attach = filt_timerattach,
181 	.f_detach = filt_timerdetach,
182 	.f_event = filt_timer,
183 };
184 static struct filterops user_filtops = {
185 	.f_attach = filt_userattach,
186 	.f_detach = filt_userdetach,
187 	.f_event = filt_user,
188 	.f_touch = filt_usertouch,
189 };
190 
191 static uma_zone_t	knote_zone;
192 static unsigned int	kq_ncallouts = 0;
193 static unsigned int 	kq_calloutmax = 4 * 1024;
194 SYSCTL_UINT(_kern, OID_AUTO, kq_calloutmax, CTLFLAG_RW,
195     &kq_calloutmax, 0, "Maximum number of callouts allocated for kqueue");
196 
197 /* XXX - ensure not influx ? */
198 #define KNOTE_ACTIVATE(kn, islock) do { 				\
199 	if ((islock))							\
200 		mtx_assert(&(kn)->kn_kq->kq_lock, MA_OWNED);		\
201 	else								\
202 		KQ_LOCK((kn)->kn_kq);					\
203 	(kn)->kn_status |= KN_ACTIVE;					\
204 	if (((kn)->kn_status & (KN_QUEUED | KN_DISABLED)) == 0)		\
205 		knote_enqueue((kn));					\
206 	if (!(islock))							\
207 		KQ_UNLOCK((kn)->kn_kq);					\
208 } while(0)
209 #define KQ_LOCK(kq) do {						\
210 	mtx_lock(&(kq)->kq_lock);					\
211 } while (0)
212 #define KQ_FLUX_WAKEUP(kq) do {						\
213 	if (((kq)->kq_state & KQ_FLUXWAIT) == KQ_FLUXWAIT) {		\
214 		(kq)->kq_state &= ~KQ_FLUXWAIT;				\
215 		wakeup((kq));						\
216 	}								\
217 } while (0)
218 #define KQ_UNLOCK_FLUX(kq) do {						\
219 	KQ_FLUX_WAKEUP(kq);						\
220 	mtx_unlock(&(kq)->kq_lock);					\
221 } while (0)
222 #define KQ_UNLOCK(kq) do {						\
223 	mtx_unlock(&(kq)->kq_lock);					\
224 } while (0)
225 #define KQ_OWNED(kq) do {						\
226 	mtx_assert(&(kq)->kq_lock, MA_OWNED);				\
227 } while (0)
228 #define KQ_NOTOWNED(kq) do {						\
229 	mtx_assert(&(kq)->kq_lock, MA_NOTOWNED);			\
230 } while (0)
231 
232 static struct knlist *
233 kn_list_lock(struct knote *kn)
234 {
235 	struct knlist *knl;
236 
237 	knl = kn->kn_knlist;
238 	if (knl != NULL)
239 		knl->kl_lock(knl->kl_lockarg);
240 	return (knl);
241 }
242 
243 static void
244 kn_list_unlock(struct knlist *knl)
245 {
246 	bool do_free;
247 
248 	if (knl == NULL)
249 		return;
250 	do_free = knl->kl_autodestroy && knlist_empty(knl);
251 	knl->kl_unlock(knl->kl_lockarg);
252 	if (do_free) {
253 		knlist_destroy(knl);
254 		free(knl, M_KQUEUE);
255 	}
256 }
257 
258 static bool
259 kn_in_flux(struct knote *kn)
260 {
261 
262 	return (kn->kn_influx > 0);
263 }
264 
265 static void
266 kn_enter_flux(struct knote *kn)
267 {
268 
269 	KQ_OWNED(kn->kn_kq);
270 	MPASS(kn->kn_influx < INT_MAX);
271 	kn->kn_influx++;
272 }
273 
274 static bool
275 kn_leave_flux(struct knote *kn)
276 {
277 
278 	KQ_OWNED(kn->kn_kq);
279 	MPASS(kn->kn_influx > 0);
280 	kn->kn_influx--;
281 	return (kn->kn_influx == 0);
282 }
283 
284 #define	KNL_ASSERT_LOCK(knl, islocked) do {				\
285 	if (islocked)							\
286 		KNL_ASSERT_LOCKED(knl);				\
287 	else								\
288 		KNL_ASSERT_UNLOCKED(knl);				\
289 } while (0)
290 #ifdef INVARIANTS
291 #define	KNL_ASSERT_LOCKED(knl) do {					\
292 	knl->kl_assert_locked((knl)->kl_lockarg);			\
293 } while (0)
294 #define	KNL_ASSERT_UNLOCKED(knl) do {					\
295 	knl->kl_assert_unlocked((knl)->kl_lockarg);			\
296 } while (0)
297 #else /* !INVARIANTS */
298 #define	KNL_ASSERT_LOCKED(knl) do {} while(0)
299 #define	KNL_ASSERT_UNLOCKED(knl) do {} while (0)
300 #endif /* INVARIANTS */
301 
302 #ifndef	KN_HASHSIZE
303 #define	KN_HASHSIZE		64		/* XXX should be tunable */
304 #endif
305 
306 #define KN_HASH(val, mask)	(((val) ^ (val >> 8)) & (mask))
307 
308 static int
309 filt_nullattach(struct knote *kn)
310 {
311 
312 	return (ENXIO);
313 };
314 
315 struct filterops null_filtops = {
316 	.f_isfd = 0,
317 	.f_attach = filt_nullattach,
318 };
319 
320 /* XXX - make SYSINIT to add these, and move into respective modules. */
321 extern struct filterops sig_filtops;
322 extern struct filterops fs_filtops;
323 
324 /*
325  * Table for for all system-defined filters.
326  */
327 static struct mtx	filterops_lock;
328 MTX_SYSINIT(kqueue_filterops, &filterops_lock, "protect sysfilt_ops",
329 	MTX_DEF);
330 static struct {
331 	struct filterops *for_fop;
332 	int for_nolock;
333 	int for_refcnt;
334 } sysfilt_ops[EVFILT_SYSCOUNT] = {
335 	{ &file_filtops, 1 },			/* EVFILT_READ */
336 	{ &file_filtops, 1 },			/* EVFILT_WRITE */
337 	{ &null_filtops },			/* EVFILT_AIO */
338 	{ &file_filtops, 1 },			/* EVFILT_VNODE */
339 	{ &proc_filtops, 1 },			/* EVFILT_PROC */
340 	{ &sig_filtops, 1 },			/* EVFILT_SIGNAL */
341 	{ &timer_filtops, 1 },			/* EVFILT_TIMER */
342 	{ &file_filtops, 1 },			/* EVFILT_PROCDESC */
343 	{ &fs_filtops, 1 },			/* EVFILT_FS */
344 	{ &null_filtops },			/* EVFILT_LIO */
345 	{ &user_filtops, 1 },			/* EVFILT_USER */
346 	{ &null_filtops },			/* EVFILT_SENDFILE */
347 	{ &file_filtops, 1 },                   /* EVFILT_EMPTY */
348 };
349 
350 /*
351  * Simple redirection for all cdevsw style objects to call their fo_kqfilter
352  * method.
353  */
354 static int
355 filt_fileattach(struct knote *kn)
356 {
357 
358 	return (fo_kqfilter(kn->kn_fp, kn));
359 }
360 
361 /*ARGSUSED*/
362 static int
363 kqueue_kqfilter(struct file *fp, struct knote *kn)
364 {
365 	struct kqueue *kq = kn->kn_fp->f_data;
366 
367 	if (kn->kn_filter != EVFILT_READ)
368 		return (EINVAL);
369 
370 	kn->kn_status |= KN_KQUEUE;
371 	kn->kn_fop = &kqread_filtops;
372 	knlist_add(&kq->kq_sel.si_note, kn, 0);
373 
374 	return (0);
375 }
376 
377 static void
378 filt_kqdetach(struct knote *kn)
379 {
380 	struct kqueue *kq = kn->kn_fp->f_data;
381 
382 	knlist_remove(&kq->kq_sel.si_note, kn, 0);
383 }
384 
385 /*ARGSUSED*/
386 static int
387 filt_kqueue(struct knote *kn, long hint)
388 {
389 	struct kqueue *kq = kn->kn_fp->f_data;
390 
391 	kn->kn_data = kq->kq_count;
392 	return (kn->kn_data > 0);
393 }
394 
395 /* XXX - move to kern_proc.c?  */
396 static int
397 filt_procattach(struct knote *kn)
398 {
399 	struct proc *p;
400 	int error;
401 	bool exiting, immediate;
402 
403 	exiting = immediate = false;
404 	p = pfind(kn->kn_id);
405 	if (p == NULL && (kn->kn_sfflags & NOTE_EXIT)) {
406 		p = zpfind(kn->kn_id);
407 		exiting = true;
408 	} else if (p != NULL && (p->p_flag & P_WEXIT)) {
409 		exiting = true;
410 	}
411 
412 	if (p == NULL)
413 		return (ESRCH);
414 	if ((error = p_cansee(curthread, p))) {
415 		PROC_UNLOCK(p);
416 		return (error);
417 	}
418 
419 	kn->kn_ptr.p_proc = p;
420 	kn->kn_flags |= EV_CLEAR;		/* automatically set */
421 
422 	/*
423 	 * Internal flag indicating registration done by kernel for the
424 	 * purposes of getting a NOTE_CHILD notification.
425 	 */
426 	if (kn->kn_flags & EV_FLAG2) {
427 		kn->kn_flags &= ~EV_FLAG2;
428 		kn->kn_data = kn->kn_sdata;		/* ppid */
429 		kn->kn_fflags = NOTE_CHILD;
430 		kn->kn_sfflags &= ~(NOTE_EXIT | NOTE_EXEC | NOTE_FORK);
431 		immediate = true; /* Force immediate activation of child note. */
432 	}
433 	/*
434 	 * Internal flag indicating registration done by kernel (for other than
435 	 * NOTE_CHILD).
436 	 */
437 	if (kn->kn_flags & EV_FLAG1) {
438 		kn->kn_flags &= ~EV_FLAG1;
439 	}
440 
441 	knlist_add(p->p_klist, kn, 1);
442 
443 	/*
444 	 * Immediately activate any child notes or, in the case of a zombie
445 	 * target process, exit notes.  The latter is necessary to handle the
446 	 * case where the target process, e.g. a child, dies before the kevent
447 	 * is registered.
448 	 */
449 	if (immediate || (exiting && filt_proc(kn, NOTE_EXIT)))
450 		KNOTE_ACTIVATE(kn, 0);
451 
452 	PROC_UNLOCK(p);
453 
454 	return (0);
455 }
456 
457 /*
458  * The knote may be attached to a different process, which may exit,
459  * leaving nothing for the knote to be attached to.  So when the process
460  * exits, the knote is marked as DETACHED and also flagged as ONESHOT so
461  * it will be deleted when read out.  However, as part of the knote deletion,
462  * this routine is called, so a check is needed to avoid actually performing
463  * a detach, because the original process does not exist any more.
464  */
465 /* XXX - move to kern_proc.c?  */
466 static void
467 filt_procdetach(struct knote *kn)
468 {
469 
470 	knlist_remove(kn->kn_knlist, kn, 0);
471 	kn->kn_ptr.p_proc = NULL;
472 }
473 
474 /* XXX - move to kern_proc.c?  */
475 static int
476 filt_proc(struct knote *kn, long hint)
477 {
478 	struct proc *p;
479 	u_int event;
480 
481 	p = kn->kn_ptr.p_proc;
482 	if (p == NULL) /* already activated, from attach filter */
483 		return (0);
484 
485 	/* Mask off extra data. */
486 	event = (u_int)hint & NOTE_PCTRLMASK;
487 
488 	/* If the user is interested in this event, record it. */
489 	if (kn->kn_sfflags & event)
490 		kn->kn_fflags |= event;
491 
492 	/* Process is gone, so flag the event as finished. */
493 	if (event == NOTE_EXIT) {
494 		kn->kn_flags |= EV_EOF | EV_ONESHOT;
495 		kn->kn_ptr.p_proc = NULL;
496 		if (kn->kn_fflags & NOTE_EXIT)
497 			kn->kn_data = KW_EXITCODE(p->p_xexit, p->p_xsig);
498 		if (kn->kn_fflags == 0)
499 			kn->kn_flags |= EV_DROP;
500 		return (1);
501 	}
502 
503 	return (kn->kn_fflags != 0);
504 }
505 
506 /*
507  * Called when the process forked. It mostly does the same as the
508  * knote(), activating all knotes registered to be activated when the
509  * process forked. Additionally, for each knote attached to the
510  * parent, check whether user wants to track the new process. If so
511  * attach a new knote to it, and immediately report an event with the
512  * child's pid.
513  */
514 void
515 knote_fork(struct knlist *list, int pid)
516 {
517 	struct kqueue *kq;
518 	struct knote *kn;
519 	struct kevent kev;
520 	int error;
521 
522 	if (list == NULL)
523 		return;
524 	list->kl_lock(list->kl_lockarg);
525 
526 	SLIST_FOREACH(kn, &list->kl_list, kn_selnext) {
527 		kq = kn->kn_kq;
528 		KQ_LOCK(kq);
529 		if (kn_in_flux(kn) && (kn->kn_status & KN_SCAN) == 0) {
530 			KQ_UNLOCK(kq);
531 			continue;
532 		}
533 
534 		/*
535 		 * The same as knote(), activate the event.
536 		 */
537 		if ((kn->kn_sfflags & NOTE_TRACK) == 0) {
538 			kn->kn_status |= KN_HASKQLOCK;
539 			if (kn->kn_fop->f_event(kn, NOTE_FORK))
540 				KNOTE_ACTIVATE(kn, 1);
541 			kn->kn_status &= ~KN_HASKQLOCK;
542 			KQ_UNLOCK(kq);
543 			continue;
544 		}
545 
546 		/*
547 		 * The NOTE_TRACK case. In addition to the activation
548 		 * of the event, we need to register new events to
549 		 * track the child. Drop the locks in preparation for
550 		 * the call to kqueue_register().
551 		 */
552 		kn_enter_flux(kn);
553 		KQ_UNLOCK(kq);
554 		list->kl_unlock(list->kl_lockarg);
555 
556 		/*
557 		 * Activate existing knote and register tracking knotes with
558 		 * new process.
559 		 *
560 		 * First register a knote to get just the child notice. This
561 		 * must be a separate note from a potential NOTE_EXIT
562 		 * notification since both NOTE_CHILD and NOTE_EXIT are defined
563 		 * to use the data field (in conflicting ways).
564 		 */
565 		kev.ident = pid;
566 		kev.filter = kn->kn_filter;
567 		kev.flags = kn->kn_flags | EV_ADD | EV_ENABLE | EV_ONESHOT |
568 		    EV_FLAG2;
569 		kev.fflags = kn->kn_sfflags;
570 		kev.data = kn->kn_id;		/* parent */
571 		kev.udata = kn->kn_kevent.udata;/* preserve udata */
572 		error = kqueue_register(kq, &kev, NULL, 0);
573 		if (error)
574 			kn->kn_fflags |= NOTE_TRACKERR;
575 
576 		/*
577 		 * Then register another knote to track other potential events
578 		 * from the new process.
579 		 */
580 		kev.ident = pid;
581 		kev.filter = kn->kn_filter;
582 		kev.flags = kn->kn_flags | EV_ADD | EV_ENABLE | EV_FLAG1;
583 		kev.fflags = kn->kn_sfflags;
584 		kev.data = kn->kn_id;		/* parent */
585 		kev.udata = kn->kn_kevent.udata;/* preserve udata */
586 		error = kqueue_register(kq, &kev, NULL, 0);
587 		if (error)
588 			kn->kn_fflags |= NOTE_TRACKERR;
589 		if (kn->kn_fop->f_event(kn, NOTE_FORK))
590 			KNOTE_ACTIVATE(kn, 0);
591 		KQ_LOCK(kq);
592 		kn_leave_flux(kn);
593 		KQ_UNLOCK_FLUX(kq);
594 		list->kl_lock(list->kl_lockarg);
595 	}
596 	list->kl_unlock(list->kl_lockarg);
597 }
598 
599 /*
600  * XXX: EVFILT_TIMER should perhaps live in kern_time.c beside the
601  * interval timer support code.
602  */
603 
604 #define NOTE_TIMER_PRECMASK	(NOTE_SECONDS|NOTE_MSECONDS|NOTE_USECONDS| \
605 				NOTE_NSECONDS)
606 
607 static sbintime_t
608 timer2sbintime(intptr_t data, int flags)
609 {
610 
611         /*
612          * Macros for converting to the fractional second portion of an
613          * sbintime_t using 64bit multiplication to improve precision.
614          */
615 #define NS_TO_SBT(ns) (((ns) * (((uint64_t)1 << 63) / 500000000)) >> 32)
616 #define US_TO_SBT(us) (((us) * (((uint64_t)1 << 63) / 500000)) >> 32)
617 #define MS_TO_SBT(ms) (((ms) * (((uint64_t)1 << 63) / 500)) >> 32)
618 	switch (flags & NOTE_TIMER_PRECMASK) {
619 	case NOTE_SECONDS:
620 #ifdef __LP64__
621 		if (data > (SBT_MAX / SBT_1S))
622 			return (SBT_MAX);
623 #endif
624 		return ((sbintime_t)data << 32);
625 	case NOTE_MSECONDS: /* FALLTHROUGH */
626 	case 0:
627 		if (data >= 1000) {
628 			int64_t secs = data / 1000;
629 #ifdef __LP64__
630 			if (secs > (SBT_MAX / SBT_1S))
631 				return (SBT_MAX);
632 #endif
633 			return (secs << 32 | MS_TO_SBT(data % 1000));
634 		}
635 		return MS_TO_SBT(data);
636 	case NOTE_USECONDS:
637 		if (data >= 1000000) {
638 			int64_t secs = data / 1000000;
639 #ifdef __LP64__
640 			if (secs > (SBT_MAX / SBT_1S))
641 				return (SBT_MAX);
642 #endif
643 			return (secs << 32 | US_TO_SBT(data % 1000000));
644 		}
645 		return US_TO_SBT(data);
646 	case NOTE_NSECONDS:
647 		if (data >= 1000000000) {
648 			int64_t secs = data / 1000000000;
649 #ifdef __LP64__
650 			if (secs > (SBT_MAX / SBT_1S))
651 				return (SBT_MAX);
652 #endif
653 			return (secs << 32 | US_TO_SBT(data % 1000000000));
654 		}
655 		return (NS_TO_SBT(data));
656 	default:
657 		break;
658 	}
659 	return (-1);
660 }
661 
662 struct kq_timer_cb_data {
663 	struct callout c;
664 	sbintime_t next;	/* next timer event fires at */
665 	sbintime_t to;		/* precalculated timer period */
666 };
667 
668 static void
669 filt_timerexpire(void *knx)
670 {
671 	struct knote *kn;
672 	struct kq_timer_cb_data *kc;
673 
674 	kn = knx;
675 	kn->kn_data++;
676 	KNOTE_ACTIVATE(kn, 0);	/* XXX - handle locking */
677 
678 	if ((kn->kn_flags & EV_ONESHOT) != 0)
679 		return;
680 
681 	kc = kn->kn_ptr.p_v;
682 	kc->next += kc->to;
683 	callout_reset_sbt_on(&kc->c, kc->next, 0, filt_timerexpire, kn,
684 	    PCPU_GET(cpuid), C_ABSOLUTE);
685 }
686 
687 /*
688  * data contains amount of time to sleep
689  */
690 static int
691 filt_timerattach(struct knote *kn)
692 {
693 	struct kq_timer_cb_data *kc;
694 	sbintime_t to;
695 	unsigned int ncallouts;
696 
697 	if (kn->kn_sdata < 0)
698 		return (EINVAL);
699 	if (kn->kn_sdata == 0 && (kn->kn_flags & EV_ONESHOT) == 0)
700 		kn->kn_sdata = 1;
701 	/* Only precision unit are supported in flags so far */
702 	if ((kn->kn_sfflags & ~NOTE_TIMER_PRECMASK) != 0)
703 		return (EINVAL);
704 
705 	to = timer2sbintime(kn->kn_sdata, kn->kn_sfflags);
706 	if (to < 0)
707 		return (EINVAL);
708 
709 	do {
710 		ncallouts = kq_ncallouts;
711 		if (ncallouts >= kq_calloutmax)
712 			return (ENOMEM);
713 	} while (!atomic_cmpset_int(&kq_ncallouts, ncallouts, ncallouts + 1));
714 
715 	kn->kn_flags |= EV_CLEAR;		/* automatically set */
716 	kn->kn_status &= ~KN_DETACHED;		/* knlist_add clears it */
717 	kn->kn_ptr.p_v = kc = malloc(sizeof(*kc), M_KQUEUE, M_WAITOK);
718 	callout_init(&kc->c, 1);
719 	kc->next = to + sbinuptime();
720 	kc->to = to;
721 	callout_reset_sbt_on(&kc->c, kc->next, 0, filt_timerexpire, kn,
722 	    PCPU_GET(cpuid), C_ABSOLUTE);
723 
724 	return (0);
725 }
726 
727 static void
728 filt_timerdetach(struct knote *kn)
729 {
730 	struct kq_timer_cb_data *kc;
731 	unsigned int old;
732 
733 	kc = kn->kn_ptr.p_v;
734 	callout_drain(&kc->c);
735 	free(kc, M_KQUEUE);
736 	old = atomic_fetchadd_int(&kq_ncallouts, -1);
737 	KASSERT(old > 0, ("Number of callouts cannot become negative"));
738 	kn->kn_status |= KN_DETACHED;	/* knlist_remove sets it */
739 }
740 
741 static int
742 filt_timer(struct knote *kn, long hint)
743 {
744 
745 	return (kn->kn_data != 0);
746 }
747 
748 static int
749 filt_userattach(struct knote *kn)
750 {
751 
752 	/*
753 	 * EVFILT_USER knotes are not attached to anything in the kernel.
754 	 */
755 	kn->kn_hook = NULL;
756 	if (kn->kn_fflags & NOTE_TRIGGER)
757 		kn->kn_hookid = 1;
758 	else
759 		kn->kn_hookid = 0;
760 	return (0);
761 }
762 
763 static void
764 filt_userdetach(__unused struct knote *kn)
765 {
766 
767 	/*
768 	 * EVFILT_USER knotes are not attached to anything in the kernel.
769 	 */
770 }
771 
772 static int
773 filt_user(struct knote *kn, __unused long hint)
774 {
775 
776 	return (kn->kn_hookid);
777 }
778 
779 static void
780 filt_usertouch(struct knote *kn, struct kevent *kev, u_long type)
781 {
782 	u_int ffctrl;
783 
784 	switch (type) {
785 	case EVENT_REGISTER:
786 		if (kev->fflags & NOTE_TRIGGER)
787 			kn->kn_hookid = 1;
788 
789 		ffctrl = kev->fflags & NOTE_FFCTRLMASK;
790 		kev->fflags &= NOTE_FFLAGSMASK;
791 		switch (ffctrl) {
792 		case NOTE_FFNOP:
793 			break;
794 
795 		case NOTE_FFAND:
796 			kn->kn_sfflags &= kev->fflags;
797 			break;
798 
799 		case NOTE_FFOR:
800 			kn->kn_sfflags |= kev->fflags;
801 			break;
802 
803 		case NOTE_FFCOPY:
804 			kn->kn_sfflags = kev->fflags;
805 			break;
806 
807 		default:
808 			/* XXX Return error? */
809 			break;
810 		}
811 		kn->kn_sdata = kev->data;
812 		if (kev->flags & EV_CLEAR) {
813 			kn->kn_hookid = 0;
814 			kn->kn_data = 0;
815 			kn->kn_fflags = 0;
816 		}
817 		break;
818 
819         case EVENT_PROCESS:
820 		*kev = kn->kn_kevent;
821 		kev->fflags = kn->kn_sfflags;
822 		kev->data = kn->kn_sdata;
823 		if (kn->kn_flags & EV_CLEAR) {
824 			kn->kn_hookid = 0;
825 			kn->kn_data = 0;
826 			kn->kn_fflags = 0;
827 		}
828 		break;
829 
830 	default:
831 		panic("filt_usertouch() - invalid type (%ld)", type);
832 		break;
833 	}
834 }
835 
836 int
837 sys_kqueue(struct thread *td, struct kqueue_args *uap)
838 {
839 
840 	return (kern_kqueue(td, 0, NULL));
841 }
842 
843 static void
844 kqueue_init(struct kqueue *kq)
845 {
846 
847 	mtx_init(&kq->kq_lock, "kqueue", NULL, MTX_DEF | MTX_DUPOK);
848 	TAILQ_INIT(&kq->kq_head);
849 	knlist_init_mtx(&kq->kq_sel.si_note, &kq->kq_lock);
850 	TASK_INIT(&kq->kq_task, 0, kqueue_task, kq);
851 }
852 
853 int
854 kern_kqueue(struct thread *td, int flags, struct filecaps *fcaps)
855 {
856 	struct filedesc *fdp;
857 	struct kqueue *kq;
858 	struct file *fp;
859 	struct ucred *cred;
860 	int fd, error;
861 
862 	fdp = td->td_proc->p_fd;
863 	cred = td->td_ucred;
864 	if (!chgkqcnt(cred->cr_ruidinfo, 1, lim_cur(td, RLIMIT_KQUEUES)))
865 		return (ENOMEM);
866 
867 	error = falloc_caps(td, &fp, &fd, flags, fcaps);
868 	if (error != 0) {
869 		chgkqcnt(cred->cr_ruidinfo, -1, 0);
870 		return (error);
871 	}
872 
873 	/* An extra reference on `fp' has been held for us by falloc(). */
874 	kq = malloc(sizeof *kq, M_KQUEUE, M_WAITOK | M_ZERO);
875 	kqueue_init(kq);
876 	kq->kq_fdp = fdp;
877 	kq->kq_cred = crhold(cred);
878 
879 	FILEDESC_XLOCK(fdp);
880 	TAILQ_INSERT_HEAD(&fdp->fd_kqlist, kq, kq_list);
881 	FILEDESC_XUNLOCK(fdp);
882 
883 	finit(fp, FREAD | FWRITE, DTYPE_KQUEUE, kq, &kqueueops);
884 	fdrop(fp, td);
885 
886 	td->td_retval[0] = fd;
887 	return (0);
888 }
889 
890 #ifndef _SYS_SYSPROTO_H_
891 struct kevent_args {
892 	int	fd;
893 	const struct kevent *changelist;
894 	int	nchanges;
895 	struct	kevent *eventlist;
896 	int	nevents;
897 	const struct timespec *timeout;
898 };
899 #endif
900 int
901 sys_kevent(struct thread *td, struct kevent_args *uap)
902 {
903 	struct timespec ts, *tsp;
904 	struct kevent_copyops k_ops = { uap,
905 					kevent_copyout,
906 					kevent_copyin};
907 	int error;
908 #ifdef KTRACE
909 	struct uio ktruio;
910 	struct iovec ktriov;
911 	struct uio *ktruioin = NULL;
912 	struct uio *ktruioout = NULL;
913 #endif
914 
915 	if (uap->timeout != NULL) {
916 		error = copyin(uap->timeout, &ts, sizeof(ts));
917 		if (error)
918 			return (error);
919 		tsp = &ts;
920 	} else
921 		tsp = NULL;
922 
923 #ifdef KTRACE
924 	if (KTRPOINT(td, KTR_GENIO)) {
925 		ktriov.iov_base = uap->changelist;
926 		ktriov.iov_len = uap->nchanges * sizeof(struct kevent);
927 		ktruio = (struct uio){ .uio_iov = &ktriov, .uio_iovcnt = 1,
928 		    .uio_segflg = UIO_USERSPACE, .uio_rw = UIO_READ,
929 		    .uio_td = td };
930 		ktruioin = cloneuio(&ktruio);
931 		ktriov.iov_base = uap->eventlist;
932 		ktriov.iov_len = uap->nevents * sizeof(struct kevent);
933 		ktruioout = cloneuio(&ktruio);
934 	}
935 #endif
936 
937 	error = kern_kevent(td, uap->fd, uap->nchanges, uap->nevents,
938 	    &k_ops, tsp);
939 
940 #ifdef KTRACE
941 	if (ktruioin != NULL) {
942 		ktruioin->uio_resid = uap->nchanges * sizeof(struct kevent);
943 		ktrgenio(uap->fd, UIO_WRITE, ktruioin, 0);
944 		ktruioout->uio_resid = td->td_retval[0] * sizeof(struct kevent);
945 		ktrgenio(uap->fd, UIO_READ, ktruioout, error);
946 	}
947 #endif
948 
949 	return (error);
950 }
951 
952 /*
953  * Copy 'count' items into the destination list pointed to by uap->eventlist.
954  */
955 static int
956 kevent_copyout(void *arg, struct kevent *kevp, int count)
957 {
958 	struct kevent_args *uap;
959 	int error;
960 
961 	KASSERT(count <= KQ_NEVENTS, ("count (%d) > KQ_NEVENTS", count));
962 	uap = (struct kevent_args *)arg;
963 
964 	error = copyout(kevp, uap->eventlist, count * sizeof *kevp);
965 	if (error == 0)
966 		uap->eventlist += count;
967 	return (error);
968 }
969 
970 /*
971  * Copy 'count' items from the list pointed to by uap->changelist.
972  */
973 static int
974 kevent_copyin(void *arg, struct kevent *kevp, int count)
975 {
976 	struct kevent_args *uap;
977 	int error;
978 
979 	KASSERT(count <= KQ_NEVENTS, ("count (%d) > KQ_NEVENTS", count));
980 	uap = (struct kevent_args *)arg;
981 
982 	error = copyin(uap->changelist, kevp, count * sizeof *kevp);
983 	if (error == 0)
984 		uap->changelist += count;
985 	return (error);
986 }
987 
988 int
989 kern_kevent(struct thread *td, int fd, int nchanges, int nevents,
990     struct kevent_copyops *k_ops, const struct timespec *timeout)
991 {
992 	cap_rights_t rights;
993 	struct file *fp;
994 	int error;
995 
996 	cap_rights_init(&rights);
997 	if (nchanges > 0)
998 		cap_rights_set(&rights, CAP_KQUEUE_CHANGE);
999 	if (nevents > 0)
1000 		cap_rights_set(&rights, CAP_KQUEUE_EVENT);
1001 	error = fget(td, fd, &rights, &fp);
1002 	if (error != 0)
1003 		return (error);
1004 
1005 	error = kern_kevent_fp(td, fp, nchanges, nevents, k_ops, timeout);
1006 	fdrop(fp, td);
1007 
1008 	return (error);
1009 }
1010 
1011 static int
1012 kqueue_kevent(struct kqueue *kq, struct thread *td, int nchanges, int nevents,
1013     struct kevent_copyops *k_ops, const struct timespec *timeout)
1014 {
1015 	struct kevent keva[KQ_NEVENTS];
1016 	struct kevent *kevp, *changes;
1017 	int i, n, nerrors, error;
1018 
1019 	nerrors = 0;
1020 	while (nchanges > 0) {
1021 		n = nchanges > KQ_NEVENTS ? KQ_NEVENTS : nchanges;
1022 		error = k_ops->k_copyin(k_ops->arg, keva, n);
1023 		if (error)
1024 			return (error);
1025 		changes = keva;
1026 		for (i = 0; i < n; i++) {
1027 			kevp = &changes[i];
1028 			if (!kevp->filter)
1029 				continue;
1030 			kevp->flags &= ~EV_SYSFLAGS;
1031 			error = kqueue_register(kq, kevp, td, 1);
1032 			if (error || (kevp->flags & EV_RECEIPT)) {
1033 				if (nevents == 0)
1034 					return (error);
1035 				kevp->flags = EV_ERROR;
1036 				kevp->data = error;
1037 				(void)k_ops->k_copyout(k_ops->arg, kevp, 1);
1038 				nevents--;
1039 				nerrors++;
1040 			}
1041 		}
1042 		nchanges -= n;
1043 	}
1044 	if (nerrors) {
1045 		td->td_retval[0] = nerrors;
1046 		return (0);
1047 	}
1048 
1049 	return (kqueue_scan(kq, nevents, k_ops, timeout, keva, td));
1050 }
1051 
1052 int
1053 kern_kevent_fp(struct thread *td, struct file *fp, int nchanges, int nevents,
1054     struct kevent_copyops *k_ops, const struct timespec *timeout)
1055 {
1056 	struct kqueue *kq;
1057 	int error;
1058 
1059 	error = kqueue_acquire(fp, &kq);
1060 	if (error != 0)
1061 		return (error);
1062 	error = kqueue_kevent(kq, td, nchanges, nevents, k_ops, timeout);
1063 	kqueue_release(kq, 0);
1064 	return (error);
1065 }
1066 
1067 /*
1068  * Performs a kevent() call on a temporarily created kqueue. This can be
1069  * used to perform one-shot polling, similar to poll() and select().
1070  */
1071 int
1072 kern_kevent_anonymous(struct thread *td, int nevents,
1073     struct kevent_copyops *k_ops)
1074 {
1075 	struct kqueue kq = {};
1076 	int error;
1077 
1078 	kqueue_init(&kq);
1079 	kq.kq_refcnt = 1;
1080 	error = kqueue_kevent(&kq, td, nevents, nevents, k_ops, NULL);
1081 	kqueue_drain(&kq, td);
1082 	kqueue_destroy(&kq);
1083 	return (error);
1084 }
1085 
1086 int
1087 kqueue_add_filteropts(int filt, struct filterops *filtops)
1088 {
1089 	int error;
1090 
1091 	error = 0;
1092 	if (filt > 0 || filt + EVFILT_SYSCOUNT < 0) {
1093 		printf(
1094 "trying to add a filterop that is out of range: %d is beyond %d\n",
1095 		    ~filt, EVFILT_SYSCOUNT);
1096 		return EINVAL;
1097 	}
1098 	mtx_lock(&filterops_lock);
1099 	if (sysfilt_ops[~filt].for_fop != &null_filtops &&
1100 	    sysfilt_ops[~filt].for_fop != NULL)
1101 		error = EEXIST;
1102 	else {
1103 		sysfilt_ops[~filt].for_fop = filtops;
1104 		sysfilt_ops[~filt].for_refcnt = 0;
1105 	}
1106 	mtx_unlock(&filterops_lock);
1107 
1108 	return (error);
1109 }
1110 
1111 int
1112 kqueue_del_filteropts(int filt)
1113 {
1114 	int error;
1115 
1116 	error = 0;
1117 	if (filt > 0 || filt + EVFILT_SYSCOUNT < 0)
1118 		return EINVAL;
1119 
1120 	mtx_lock(&filterops_lock);
1121 	if (sysfilt_ops[~filt].for_fop == &null_filtops ||
1122 	    sysfilt_ops[~filt].for_fop == NULL)
1123 		error = EINVAL;
1124 	else if (sysfilt_ops[~filt].for_refcnt != 0)
1125 		error = EBUSY;
1126 	else {
1127 		sysfilt_ops[~filt].for_fop = &null_filtops;
1128 		sysfilt_ops[~filt].for_refcnt = 0;
1129 	}
1130 	mtx_unlock(&filterops_lock);
1131 
1132 	return error;
1133 }
1134 
1135 static struct filterops *
1136 kqueue_fo_find(int filt)
1137 {
1138 
1139 	if (filt > 0 || filt + EVFILT_SYSCOUNT < 0)
1140 		return NULL;
1141 
1142 	if (sysfilt_ops[~filt].for_nolock)
1143 		return sysfilt_ops[~filt].for_fop;
1144 
1145 	mtx_lock(&filterops_lock);
1146 	sysfilt_ops[~filt].for_refcnt++;
1147 	if (sysfilt_ops[~filt].for_fop == NULL)
1148 		sysfilt_ops[~filt].for_fop = &null_filtops;
1149 	mtx_unlock(&filterops_lock);
1150 
1151 	return sysfilt_ops[~filt].for_fop;
1152 }
1153 
1154 static void
1155 kqueue_fo_release(int filt)
1156 {
1157 
1158 	if (filt > 0 || filt + EVFILT_SYSCOUNT < 0)
1159 		return;
1160 
1161 	if (sysfilt_ops[~filt].for_nolock)
1162 		return;
1163 
1164 	mtx_lock(&filterops_lock);
1165 	KASSERT(sysfilt_ops[~filt].for_refcnt > 0,
1166 	    ("filter object refcount not valid on release"));
1167 	sysfilt_ops[~filt].for_refcnt--;
1168 	mtx_unlock(&filterops_lock);
1169 }
1170 
1171 /*
1172  * A ref to kq (obtained via kqueue_acquire) must be held.  waitok will
1173  * influence if memory allocation should wait.  Make sure it is 0 if you
1174  * hold any mutexes.
1175  */
1176 static int
1177 kqueue_register(struct kqueue *kq, struct kevent *kev, struct thread *td, int waitok)
1178 {
1179 	struct filterops *fops;
1180 	struct file *fp;
1181 	struct knote *kn, *tkn;
1182 	struct knlist *knl;
1183 	cap_rights_t rights;
1184 	int error, filt, event;
1185 	int haskqglobal, filedesc_unlock;
1186 
1187 	if ((kev->flags & (EV_ENABLE | EV_DISABLE)) == (EV_ENABLE | EV_DISABLE))
1188 		return (EINVAL);
1189 
1190 	fp = NULL;
1191 	kn = NULL;
1192 	knl = NULL;
1193 	error = 0;
1194 	haskqglobal = 0;
1195 	filedesc_unlock = 0;
1196 
1197 	filt = kev->filter;
1198 	fops = kqueue_fo_find(filt);
1199 	if (fops == NULL)
1200 		return EINVAL;
1201 
1202 	if (kev->flags & EV_ADD) {
1203 		/*
1204 		 * Prevent waiting with locks.  Non-sleepable
1205 		 * allocation failures are handled in the loop, only
1206 		 * if the spare knote appears to be actually required.
1207 		 */
1208 		tkn = knote_alloc(waitok);
1209 	} else {
1210 		tkn = NULL;
1211 	}
1212 
1213 findkn:
1214 	if (fops->f_isfd) {
1215 		KASSERT(td != NULL, ("td is NULL"));
1216 		if (kev->ident > INT_MAX)
1217 			error = EBADF;
1218 		else
1219 			error = fget(td, kev->ident,
1220 			    cap_rights_init(&rights, CAP_EVENT), &fp);
1221 		if (error)
1222 			goto done;
1223 
1224 		if ((kev->flags & EV_ADD) == EV_ADD && kqueue_expand(kq, fops,
1225 		    kev->ident, 0) != 0) {
1226 			/* try again */
1227 			fdrop(fp, td);
1228 			fp = NULL;
1229 			error = kqueue_expand(kq, fops, kev->ident, waitok);
1230 			if (error)
1231 				goto done;
1232 			goto findkn;
1233 		}
1234 
1235 		if (fp->f_type == DTYPE_KQUEUE) {
1236 			/*
1237 			 * If we add some intelligence about what we are doing,
1238 			 * we should be able to support events on ourselves.
1239 			 * We need to know when we are doing this to prevent
1240 			 * getting both the knlist lock and the kq lock since
1241 			 * they are the same thing.
1242 			 */
1243 			if (fp->f_data == kq) {
1244 				error = EINVAL;
1245 				goto done;
1246 			}
1247 
1248 			/*
1249 			 * Pre-lock the filedesc before the global
1250 			 * lock mutex, see the comment in
1251 			 * kqueue_close().
1252 			 */
1253 			FILEDESC_XLOCK(td->td_proc->p_fd);
1254 			filedesc_unlock = 1;
1255 			KQ_GLOBAL_LOCK(&kq_global, haskqglobal);
1256 		}
1257 
1258 		KQ_LOCK(kq);
1259 		if (kev->ident < kq->kq_knlistsize) {
1260 			SLIST_FOREACH(kn, &kq->kq_knlist[kev->ident], kn_link)
1261 				if (kev->filter == kn->kn_filter)
1262 					break;
1263 		}
1264 	} else {
1265 		if ((kev->flags & EV_ADD) == EV_ADD)
1266 			kqueue_expand(kq, fops, kev->ident, waitok);
1267 
1268 		KQ_LOCK(kq);
1269 
1270 		/*
1271 		 * If possible, find an existing knote to use for this kevent.
1272 		 */
1273 		if (kev->filter == EVFILT_PROC &&
1274 		    (kev->flags & (EV_FLAG1 | EV_FLAG2)) != 0) {
1275 			/* This is an internal creation of a process tracking
1276 			 * note. Don't attempt to coalesce this with an
1277 			 * existing note.
1278 			 */
1279 			;
1280 		} else if (kq->kq_knhashmask != 0) {
1281 			struct klist *list;
1282 
1283 			list = &kq->kq_knhash[
1284 			    KN_HASH((u_long)kev->ident, kq->kq_knhashmask)];
1285 			SLIST_FOREACH(kn, list, kn_link)
1286 				if (kev->ident == kn->kn_id &&
1287 				    kev->filter == kn->kn_filter)
1288 					break;
1289 		}
1290 	}
1291 
1292 	/* knote is in the process of changing, wait for it to stabilize. */
1293 	if (kn != NULL && kn_in_flux(kn)) {
1294 		KQ_GLOBAL_UNLOCK(&kq_global, haskqglobal);
1295 		if (filedesc_unlock) {
1296 			FILEDESC_XUNLOCK(td->td_proc->p_fd);
1297 			filedesc_unlock = 0;
1298 		}
1299 		kq->kq_state |= KQ_FLUXWAIT;
1300 		msleep(kq, &kq->kq_lock, PSOCK | PDROP, "kqflxwt", 0);
1301 		if (fp != NULL) {
1302 			fdrop(fp, td);
1303 			fp = NULL;
1304 		}
1305 		goto findkn;
1306 	}
1307 
1308 	/*
1309 	 * kn now contains the matching knote, or NULL if no match
1310 	 */
1311 	if (kn == NULL) {
1312 		if (kev->flags & EV_ADD) {
1313 			kn = tkn;
1314 			tkn = NULL;
1315 			if (kn == NULL) {
1316 				KQ_UNLOCK(kq);
1317 				error = ENOMEM;
1318 				goto done;
1319 			}
1320 			kn->kn_fp = fp;
1321 			kn->kn_kq = kq;
1322 			kn->kn_fop = fops;
1323 			/*
1324 			 * apply reference counts to knote structure, and
1325 			 * do not release it at the end of this routine.
1326 			 */
1327 			fops = NULL;
1328 			fp = NULL;
1329 
1330 			kn->kn_sfflags = kev->fflags;
1331 			kn->kn_sdata = kev->data;
1332 			kev->fflags = 0;
1333 			kev->data = 0;
1334 			kn->kn_kevent = *kev;
1335 			kn->kn_kevent.flags &= ~(EV_ADD | EV_DELETE |
1336 			    EV_ENABLE | EV_DISABLE | EV_FORCEONESHOT);
1337 			kn->kn_status = KN_DETACHED;
1338 			kn_enter_flux(kn);
1339 
1340 			error = knote_attach(kn, kq);
1341 			KQ_UNLOCK(kq);
1342 			if (error != 0) {
1343 				tkn = kn;
1344 				goto done;
1345 			}
1346 
1347 			if ((error = kn->kn_fop->f_attach(kn)) != 0) {
1348 				knote_drop_detached(kn, td);
1349 				goto done;
1350 			}
1351 			knl = kn_list_lock(kn);
1352 			goto done_ev_add;
1353 		} else {
1354 			/* No matching knote and the EV_ADD flag is not set. */
1355 			KQ_UNLOCK(kq);
1356 			error = ENOENT;
1357 			goto done;
1358 		}
1359 	}
1360 
1361 	if (kev->flags & EV_DELETE) {
1362 		kn_enter_flux(kn);
1363 		KQ_UNLOCK(kq);
1364 		knote_drop(kn, td);
1365 		goto done;
1366 	}
1367 
1368 	if (kev->flags & EV_FORCEONESHOT) {
1369 		kn->kn_flags |= EV_ONESHOT;
1370 		KNOTE_ACTIVATE(kn, 1);
1371 	}
1372 
1373 	/*
1374 	 * The user may change some filter values after the initial EV_ADD,
1375 	 * but doing so will not reset any filter which has already been
1376 	 * triggered.
1377 	 */
1378 	kn->kn_status |= KN_SCAN;
1379 	kn_enter_flux(kn);
1380 	KQ_UNLOCK(kq);
1381 	knl = kn_list_lock(kn);
1382 	kn->kn_kevent.udata = kev->udata;
1383 	if (!fops->f_isfd && fops->f_touch != NULL) {
1384 		fops->f_touch(kn, kev, EVENT_REGISTER);
1385 	} else {
1386 		kn->kn_sfflags = kev->fflags;
1387 		kn->kn_sdata = kev->data;
1388 	}
1389 
1390 	/*
1391 	 * We can get here with kn->kn_knlist == NULL.  This can happen when
1392 	 * the initial attach event decides that the event is "completed"
1393 	 * already.  i.e. filt_procattach is called on a zombie process.  It
1394 	 * will call filt_proc which will remove it from the list, and NULL
1395 	 * kn_knlist.
1396 	 */
1397 done_ev_add:
1398 	if ((kev->flags & EV_ENABLE) != 0)
1399 		kn->kn_status &= ~KN_DISABLED;
1400 	else if ((kev->flags & EV_DISABLE) != 0)
1401 		kn->kn_status |= KN_DISABLED;
1402 
1403 	if ((kn->kn_status & KN_DISABLED) == 0)
1404 		event = kn->kn_fop->f_event(kn, 0);
1405 	else
1406 		event = 0;
1407 
1408 	KQ_LOCK(kq);
1409 	if (event)
1410 		kn->kn_status |= KN_ACTIVE;
1411 	if ((kn->kn_status & (KN_ACTIVE | KN_DISABLED | KN_QUEUED)) ==
1412 	    KN_ACTIVE)
1413 		knote_enqueue(kn);
1414 	kn->kn_status &= ~KN_SCAN;
1415 	kn_leave_flux(kn);
1416 	kn_list_unlock(knl);
1417 	KQ_UNLOCK_FLUX(kq);
1418 
1419 done:
1420 	KQ_GLOBAL_UNLOCK(&kq_global, haskqglobal);
1421 	if (filedesc_unlock)
1422 		FILEDESC_XUNLOCK(td->td_proc->p_fd);
1423 	if (fp != NULL)
1424 		fdrop(fp, td);
1425 	knote_free(tkn);
1426 	if (fops != NULL)
1427 		kqueue_fo_release(filt);
1428 	return (error);
1429 }
1430 
1431 static int
1432 kqueue_acquire(struct file *fp, struct kqueue **kqp)
1433 {
1434 	int error;
1435 	struct kqueue *kq;
1436 
1437 	error = 0;
1438 
1439 	kq = fp->f_data;
1440 	if (fp->f_type != DTYPE_KQUEUE || kq == NULL)
1441 		return (EBADF);
1442 	*kqp = kq;
1443 	KQ_LOCK(kq);
1444 	if ((kq->kq_state & KQ_CLOSING) == KQ_CLOSING) {
1445 		KQ_UNLOCK(kq);
1446 		return (EBADF);
1447 	}
1448 	kq->kq_refcnt++;
1449 	KQ_UNLOCK(kq);
1450 
1451 	return error;
1452 }
1453 
1454 static void
1455 kqueue_release(struct kqueue *kq, int locked)
1456 {
1457 	if (locked)
1458 		KQ_OWNED(kq);
1459 	else
1460 		KQ_LOCK(kq);
1461 	kq->kq_refcnt--;
1462 	if (kq->kq_refcnt == 1)
1463 		wakeup(&kq->kq_refcnt);
1464 	if (!locked)
1465 		KQ_UNLOCK(kq);
1466 }
1467 
1468 static void
1469 kqueue_schedtask(struct kqueue *kq)
1470 {
1471 
1472 	KQ_OWNED(kq);
1473 	KASSERT(((kq->kq_state & KQ_TASKDRAIN) != KQ_TASKDRAIN),
1474 	    ("scheduling kqueue task while draining"));
1475 
1476 	if ((kq->kq_state & KQ_TASKSCHED) != KQ_TASKSCHED) {
1477 		taskqueue_enqueue(taskqueue_kqueue_ctx, &kq->kq_task);
1478 		kq->kq_state |= KQ_TASKSCHED;
1479 	}
1480 }
1481 
1482 /*
1483  * Expand the kq to make sure we have storage for fops/ident pair.
1484  *
1485  * Return 0 on success (or no work necessary), return errno on failure.
1486  *
1487  * Not calling hashinit w/ waitok (proper malloc flag) should be safe.
1488  * If kqueue_register is called from a non-fd context, there usually/should
1489  * be no locks held.
1490  */
1491 static int
1492 kqueue_expand(struct kqueue *kq, struct filterops *fops, uintptr_t ident,
1493 	int waitok)
1494 {
1495 	struct klist *list, *tmp_knhash, *to_free;
1496 	u_long tmp_knhashmask;
1497 	int size;
1498 	int fd;
1499 	int mflag = waitok ? M_WAITOK : M_NOWAIT;
1500 
1501 	KQ_NOTOWNED(kq);
1502 
1503 	to_free = NULL;
1504 	if (fops->f_isfd) {
1505 		fd = ident;
1506 		if (kq->kq_knlistsize <= fd) {
1507 			size = kq->kq_knlistsize;
1508 			while (size <= fd)
1509 				size += KQEXTENT;
1510 			list = malloc(size * sizeof(*list), M_KQUEUE, mflag);
1511 			if (list == NULL)
1512 				return ENOMEM;
1513 			KQ_LOCK(kq);
1514 			if (kq->kq_knlistsize > fd) {
1515 				to_free = list;
1516 				list = NULL;
1517 			} else {
1518 				if (kq->kq_knlist != NULL) {
1519 					bcopy(kq->kq_knlist, list,
1520 					    kq->kq_knlistsize * sizeof(*list));
1521 					to_free = kq->kq_knlist;
1522 					kq->kq_knlist = NULL;
1523 				}
1524 				bzero((caddr_t)list +
1525 				    kq->kq_knlistsize * sizeof(*list),
1526 				    (size - kq->kq_knlistsize) * sizeof(*list));
1527 				kq->kq_knlistsize = size;
1528 				kq->kq_knlist = list;
1529 			}
1530 			KQ_UNLOCK(kq);
1531 		}
1532 	} else {
1533 		if (kq->kq_knhashmask == 0) {
1534 			tmp_knhash = hashinit(KN_HASHSIZE, M_KQUEUE,
1535 			    &tmp_knhashmask);
1536 			if (tmp_knhash == NULL)
1537 				return ENOMEM;
1538 			KQ_LOCK(kq);
1539 			if (kq->kq_knhashmask == 0) {
1540 				kq->kq_knhash = tmp_knhash;
1541 				kq->kq_knhashmask = tmp_knhashmask;
1542 			} else {
1543 				to_free = tmp_knhash;
1544 			}
1545 			KQ_UNLOCK(kq);
1546 		}
1547 	}
1548 	free(to_free, M_KQUEUE);
1549 
1550 	KQ_NOTOWNED(kq);
1551 	return 0;
1552 }
1553 
1554 static void
1555 kqueue_task(void *arg, int pending)
1556 {
1557 	struct kqueue *kq;
1558 	int haskqglobal;
1559 
1560 	haskqglobal = 0;
1561 	kq = arg;
1562 
1563 	KQ_GLOBAL_LOCK(&kq_global, haskqglobal);
1564 	KQ_LOCK(kq);
1565 
1566 	KNOTE_LOCKED(&kq->kq_sel.si_note, 0);
1567 
1568 	kq->kq_state &= ~KQ_TASKSCHED;
1569 	if ((kq->kq_state & KQ_TASKDRAIN) == KQ_TASKDRAIN) {
1570 		wakeup(&kq->kq_state);
1571 	}
1572 	KQ_UNLOCK(kq);
1573 	KQ_GLOBAL_UNLOCK(&kq_global, haskqglobal);
1574 }
1575 
1576 /*
1577  * Scan, update kn_data (if not ONESHOT), and copyout triggered events.
1578  * We treat KN_MARKER knotes as if they are in flux.
1579  */
1580 static int
1581 kqueue_scan(struct kqueue *kq, int maxevents, struct kevent_copyops *k_ops,
1582     const struct timespec *tsp, struct kevent *keva, struct thread *td)
1583 {
1584 	struct kevent *kevp;
1585 	struct knote *kn, *marker;
1586 	struct knlist *knl;
1587 	sbintime_t asbt, rsbt;
1588 	int count, error, haskqglobal, influx, nkev, touch;
1589 
1590 	count = maxevents;
1591 	nkev = 0;
1592 	error = 0;
1593 	haskqglobal = 0;
1594 
1595 	if (maxevents == 0)
1596 		goto done_nl;
1597 
1598 	rsbt = 0;
1599 	if (tsp != NULL) {
1600 		if (tsp->tv_sec < 0 || tsp->tv_nsec < 0 ||
1601 		    tsp->tv_nsec >= 1000000000) {
1602 			error = EINVAL;
1603 			goto done_nl;
1604 		}
1605 		if (timespecisset(tsp)) {
1606 			if (tsp->tv_sec <= INT32_MAX) {
1607 				rsbt = tstosbt(*tsp);
1608 				if (TIMESEL(&asbt, rsbt))
1609 					asbt += tc_tick_sbt;
1610 				if (asbt <= SBT_MAX - rsbt)
1611 					asbt += rsbt;
1612 				else
1613 					asbt = 0;
1614 				rsbt >>= tc_precexp;
1615 			} else
1616 				asbt = 0;
1617 		} else
1618 			asbt = -1;
1619 	} else
1620 		asbt = 0;
1621 	marker = knote_alloc(1);
1622 	marker->kn_status = KN_MARKER;
1623 	KQ_LOCK(kq);
1624 
1625 retry:
1626 	kevp = keva;
1627 	if (kq->kq_count == 0) {
1628 		if (asbt == -1) {
1629 			error = EWOULDBLOCK;
1630 		} else {
1631 			kq->kq_state |= KQ_SLEEP;
1632 			error = msleep_sbt(kq, &kq->kq_lock, PSOCK | PCATCH,
1633 			    "kqread", asbt, rsbt, C_ABSOLUTE);
1634 		}
1635 		if (error == 0)
1636 			goto retry;
1637 		/* don't restart after signals... */
1638 		if (error == ERESTART)
1639 			error = EINTR;
1640 		else if (error == EWOULDBLOCK)
1641 			error = 0;
1642 		goto done;
1643 	}
1644 
1645 	TAILQ_INSERT_TAIL(&kq->kq_head, marker, kn_tqe);
1646 	influx = 0;
1647 	while (count) {
1648 		KQ_OWNED(kq);
1649 		kn = TAILQ_FIRST(&kq->kq_head);
1650 
1651 		if ((kn->kn_status == KN_MARKER && kn != marker) ||
1652 		    kn_in_flux(kn)) {
1653 			if (influx) {
1654 				influx = 0;
1655 				KQ_FLUX_WAKEUP(kq);
1656 			}
1657 			kq->kq_state |= KQ_FLUXWAIT;
1658 			error = msleep(kq, &kq->kq_lock, PSOCK,
1659 			    "kqflxwt", 0);
1660 			continue;
1661 		}
1662 
1663 		TAILQ_REMOVE(&kq->kq_head, kn, kn_tqe);
1664 		if ((kn->kn_status & KN_DISABLED) == KN_DISABLED) {
1665 			kn->kn_status &= ~KN_QUEUED;
1666 			kq->kq_count--;
1667 			continue;
1668 		}
1669 		if (kn == marker) {
1670 			KQ_FLUX_WAKEUP(kq);
1671 			if (count == maxevents)
1672 				goto retry;
1673 			goto done;
1674 		}
1675 		KASSERT(!kn_in_flux(kn),
1676 		    ("knote %p is unexpectedly in flux", kn));
1677 
1678 		if ((kn->kn_flags & EV_DROP) == EV_DROP) {
1679 			kn->kn_status &= ~KN_QUEUED;
1680 			kn_enter_flux(kn);
1681 			kq->kq_count--;
1682 			KQ_UNLOCK(kq);
1683 			/*
1684 			 * We don't need to lock the list since we've
1685 			 * marked it as in flux.
1686 			 */
1687 			knote_drop(kn, td);
1688 			KQ_LOCK(kq);
1689 			continue;
1690 		} else if ((kn->kn_flags & EV_ONESHOT) == EV_ONESHOT) {
1691 			kn->kn_status &= ~KN_QUEUED;
1692 			kn_enter_flux(kn);
1693 			kq->kq_count--;
1694 			KQ_UNLOCK(kq);
1695 			/*
1696 			 * We don't need to lock the list since we've
1697 			 * marked the knote as being in flux.
1698 			 */
1699 			*kevp = kn->kn_kevent;
1700 			knote_drop(kn, td);
1701 			KQ_LOCK(kq);
1702 			kn = NULL;
1703 		} else {
1704 			kn->kn_status |= KN_SCAN;
1705 			kn_enter_flux(kn);
1706 			KQ_UNLOCK(kq);
1707 			if ((kn->kn_status & KN_KQUEUE) == KN_KQUEUE)
1708 				KQ_GLOBAL_LOCK(&kq_global, haskqglobal);
1709 			knl = kn_list_lock(kn);
1710 			if (kn->kn_fop->f_event(kn, 0) == 0) {
1711 				KQ_LOCK(kq);
1712 				KQ_GLOBAL_UNLOCK(&kq_global, haskqglobal);
1713 				kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE |
1714 				    KN_SCAN);
1715 				kn_leave_flux(kn);
1716 				kq->kq_count--;
1717 				kn_list_unlock(knl);
1718 				influx = 1;
1719 				continue;
1720 			}
1721 			touch = (!kn->kn_fop->f_isfd &&
1722 			    kn->kn_fop->f_touch != NULL);
1723 			if (touch)
1724 				kn->kn_fop->f_touch(kn, kevp, EVENT_PROCESS);
1725 			else
1726 				*kevp = kn->kn_kevent;
1727 			KQ_LOCK(kq);
1728 			KQ_GLOBAL_UNLOCK(&kq_global, haskqglobal);
1729 			if (kn->kn_flags & (EV_CLEAR | EV_DISPATCH)) {
1730 				/*
1731 				 * Manually clear knotes who weren't
1732 				 * 'touch'ed.
1733 				 */
1734 				if (touch == 0 && kn->kn_flags & EV_CLEAR) {
1735 					kn->kn_data = 0;
1736 					kn->kn_fflags = 0;
1737 				}
1738 				if (kn->kn_flags & EV_DISPATCH)
1739 					kn->kn_status |= KN_DISABLED;
1740 				kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE);
1741 				kq->kq_count--;
1742 			} else
1743 				TAILQ_INSERT_TAIL(&kq->kq_head, kn, kn_tqe);
1744 
1745 			kn->kn_status &= ~KN_SCAN;
1746 			kn_leave_flux(kn);
1747 			kn_list_unlock(knl);
1748 			influx = 1;
1749 		}
1750 
1751 		/* we are returning a copy to the user */
1752 		kevp++;
1753 		nkev++;
1754 		count--;
1755 
1756 		if (nkev == KQ_NEVENTS) {
1757 			influx = 0;
1758 			KQ_UNLOCK_FLUX(kq);
1759 			error = k_ops->k_copyout(k_ops->arg, keva, nkev);
1760 			nkev = 0;
1761 			kevp = keva;
1762 			KQ_LOCK(kq);
1763 			if (error)
1764 				break;
1765 		}
1766 	}
1767 	TAILQ_REMOVE(&kq->kq_head, marker, kn_tqe);
1768 done:
1769 	KQ_OWNED(kq);
1770 	KQ_UNLOCK_FLUX(kq);
1771 	knote_free(marker);
1772 done_nl:
1773 	KQ_NOTOWNED(kq);
1774 	if (nkev != 0)
1775 		error = k_ops->k_copyout(k_ops->arg, keva, nkev);
1776 	td->td_retval[0] = maxevents - count;
1777 	return (error);
1778 }
1779 
1780 /*ARGSUSED*/
1781 static int
1782 kqueue_ioctl(struct file *fp, u_long cmd, void *data,
1783 	struct ucred *active_cred, struct thread *td)
1784 {
1785 	/*
1786 	 * Enabling sigio causes two major problems:
1787 	 * 1) infinite recursion:
1788 	 * Synopsys: kevent is being used to track signals and have FIOASYNC
1789 	 * set.  On receipt of a signal this will cause a kqueue to recurse
1790 	 * into itself over and over.  Sending the sigio causes the kqueue
1791 	 * to become ready, which in turn posts sigio again, forever.
1792 	 * Solution: this can be solved by setting a flag in the kqueue that
1793 	 * we have a SIGIO in progress.
1794 	 * 2) locking problems:
1795 	 * Synopsys: Kqueue is a leaf subsystem, but adding signalling puts
1796 	 * us above the proc and pgrp locks.
1797 	 * Solution: Post a signal using an async mechanism, being sure to
1798 	 * record a generation count in the delivery so that we do not deliver
1799 	 * a signal to the wrong process.
1800 	 *
1801 	 * Note, these two mechanisms are somewhat mutually exclusive!
1802 	 */
1803 #if 0
1804 	struct kqueue *kq;
1805 
1806 	kq = fp->f_data;
1807 	switch (cmd) {
1808 	case FIOASYNC:
1809 		if (*(int *)data) {
1810 			kq->kq_state |= KQ_ASYNC;
1811 		} else {
1812 			kq->kq_state &= ~KQ_ASYNC;
1813 		}
1814 		return (0);
1815 
1816 	case FIOSETOWN:
1817 		return (fsetown(*(int *)data, &kq->kq_sigio));
1818 
1819 	case FIOGETOWN:
1820 		*(int *)data = fgetown(&kq->kq_sigio);
1821 		return (0);
1822 	}
1823 #endif
1824 
1825 	return (ENOTTY);
1826 }
1827 
1828 /*ARGSUSED*/
1829 static int
1830 kqueue_poll(struct file *fp, int events, struct ucred *active_cred,
1831 	struct thread *td)
1832 {
1833 	struct kqueue *kq;
1834 	int revents = 0;
1835 	int error;
1836 
1837 	if ((error = kqueue_acquire(fp, &kq)))
1838 		return POLLERR;
1839 
1840 	KQ_LOCK(kq);
1841 	if (events & (POLLIN | POLLRDNORM)) {
1842 		if (kq->kq_count) {
1843 			revents |= events & (POLLIN | POLLRDNORM);
1844 		} else {
1845 			selrecord(td, &kq->kq_sel);
1846 			if (SEL_WAITING(&kq->kq_sel))
1847 				kq->kq_state |= KQ_SEL;
1848 		}
1849 	}
1850 	kqueue_release(kq, 1);
1851 	KQ_UNLOCK(kq);
1852 	return (revents);
1853 }
1854 
1855 /*ARGSUSED*/
1856 static int
1857 kqueue_stat(struct file *fp, struct stat *st, struct ucred *active_cred,
1858 	struct thread *td)
1859 {
1860 
1861 	bzero((void *)st, sizeof *st);
1862 	/*
1863 	 * We no longer return kq_count because the unlocked value is useless.
1864 	 * If you spent all this time getting the count, why not spend your
1865 	 * syscall better by calling kevent?
1866 	 *
1867 	 * XXX - This is needed for libc_r.
1868 	 */
1869 	st->st_mode = S_IFIFO;
1870 	return (0);
1871 }
1872 
1873 static void
1874 kqueue_drain(struct kqueue *kq, struct thread *td)
1875 {
1876 	struct knote *kn;
1877 	int i;
1878 
1879 	KQ_LOCK(kq);
1880 
1881 	KASSERT((kq->kq_state & KQ_CLOSING) != KQ_CLOSING,
1882 	    ("kqueue already closing"));
1883 	kq->kq_state |= KQ_CLOSING;
1884 	if (kq->kq_refcnt > 1)
1885 		msleep(&kq->kq_refcnt, &kq->kq_lock, PSOCK, "kqclose", 0);
1886 
1887 	KASSERT(kq->kq_refcnt == 1, ("other refs are out there!"));
1888 
1889 	KASSERT(knlist_empty(&kq->kq_sel.si_note),
1890 	    ("kqueue's knlist not empty"));
1891 
1892 	for (i = 0; i < kq->kq_knlistsize; i++) {
1893 		while ((kn = SLIST_FIRST(&kq->kq_knlist[i])) != NULL) {
1894 			if (kn_in_flux(kn)) {
1895 				kq->kq_state |= KQ_FLUXWAIT;
1896 				msleep(kq, &kq->kq_lock, PSOCK, "kqclo1", 0);
1897 				continue;
1898 			}
1899 			kn_enter_flux(kn);
1900 			KQ_UNLOCK(kq);
1901 			knote_drop(kn, td);
1902 			KQ_LOCK(kq);
1903 		}
1904 	}
1905 	if (kq->kq_knhashmask != 0) {
1906 		for (i = 0; i <= kq->kq_knhashmask; i++) {
1907 			while ((kn = SLIST_FIRST(&kq->kq_knhash[i])) != NULL) {
1908 				if (kn_in_flux(kn)) {
1909 					kq->kq_state |= KQ_FLUXWAIT;
1910 					msleep(kq, &kq->kq_lock, PSOCK,
1911 					       "kqclo2", 0);
1912 					continue;
1913 				}
1914 				kn_enter_flux(kn);
1915 				KQ_UNLOCK(kq);
1916 				knote_drop(kn, td);
1917 				KQ_LOCK(kq);
1918 			}
1919 		}
1920 	}
1921 
1922 	if ((kq->kq_state & KQ_TASKSCHED) == KQ_TASKSCHED) {
1923 		kq->kq_state |= KQ_TASKDRAIN;
1924 		msleep(&kq->kq_state, &kq->kq_lock, PSOCK, "kqtqdr", 0);
1925 	}
1926 
1927 	if ((kq->kq_state & KQ_SEL) == KQ_SEL) {
1928 		selwakeuppri(&kq->kq_sel, PSOCK);
1929 		if (!SEL_WAITING(&kq->kq_sel))
1930 			kq->kq_state &= ~KQ_SEL;
1931 	}
1932 
1933 	KQ_UNLOCK(kq);
1934 }
1935 
1936 static void
1937 kqueue_destroy(struct kqueue *kq)
1938 {
1939 
1940 	KASSERT(kq->kq_fdp == NULL,
1941 	    ("kqueue still attached to a file descriptor"));
1942 	seldrain(&kq->kq_sel);
1943 	knlist_destroy(&kq->kq_sel.si_note);
1944 	mtx_destroy(&kq->kq_lock);
1945 
1946 	if (kq->kq_knhash != NULL)
1947 		free(kq->kq_knhash, M_KQUEUE);
1948 	if (kq->kq_knlist != NULL)
1949 		free(kq->kq_knlist, M_KQUEUE);
1950 
1951 	funsetown(&kq->kq_sigio);
1952 }
1953 
1954 /*ARGSUSED*/
1955 static int
1956 kqueue_close(struct file *fp, struct thread *td)
1957 {
1958 	struct kqueue *kq = fp->f_data;
1959 	struct filedesc *fdp;
1960 	int error;
1961 	int filedesc_unlock;
1962 
1963 	if ((error = kqueue_acquire(fp, &kq)))
1964 		return error;
1965 	kqueue_drain(kq, td);
1966 
1967 	/*
1968 	 * We could be called due to the knote_drop() doing fdrop(),
1969 	 * called from kqueue_register().  In this case the global
1970 	 * lock is owned, and filedesc sx is locked before, to not
1971 	 * take the sleepable lock after non-sleepable.
1972 	 */
1973 	fdp = kq->kq_fdp;
1974 	kq->kq_fdp = NULL;
1975 	if (!sx_xlocked(FILEDESC_LOCK(fdp))) {
1976 		FILEDESC_XLOCK(fdp);
1977 		filedesc_unlock = 1;
1978 	} else
1979 		filedesc_unlock = 0;
1980 	TAILQ_REMOVE(&fdp->fd_kqlist, kq, kq_list);
1981 	if (filedesc_unlock)
1982 		FILEDESC_XUNLOCK(fdp);
1983 
1984 	kqueue_destroy(kq);
1985 	chgkqcnt(kq->kq_cred->cr_ruidinfo, -1, 0);
1986 	crfree(kq->kq_cred);
1987 	free(kq, M_KQUEUE);
1988 	fp->f_data = NULL;
1989 
1990 	return (0);
1991 }
1992 
1993 static int
1994 kqueue_fill_kinfo(struct file *fp, struct kinfo_file *kif, struct filedesc *fdp)
1995 {
1996 
1997 	kif->kf_type = KF_TYPE_KQUEUE;
1998 	return (0);
1999 }
2000 
2001 static void
2002 kqueue_wakeup(struct kqueue *kq)
2003 {
2004 	KQ_OWNED(kq);
2005 
2006 	if ((kq->kq_state & KQ_SLEEP) == KQ_SLEEP) {
2007 		kq->kq_state &= ~KQ_SLEEP;
2008 		wakeup(kq);
2009 	}
2010 	if ((kq->kq_state & KQ_SEL) == KQ_SEL) {
2011 		selwakeuppri(&kq->kq_sel, PSOCK);
2012 		if (!SEL_WAITING(&kq->kq_sel))
2013 			kq->kq_state &= ~KQ_SEL;
2014 	}
2015 	if (!knlist_empty(&kq->kq_sel.si_note))
2016 		kqueue_schedtask(kq);
2017 	if ((kq->kq_state & KQ_ASYNC) == KQ_ASYNC) {
2018 		pgsigio(&kq->kq_sigio, SIGIO, 0);
2019 	}
2020 }
2021 
2022 /*
2023  * Walk down a list of knotes, activating them if their event has triggered.
2024  *
2025  * There is a possibility to optimize in the case of one kq watching another.
2026  * Instead of scheduling a task to wake it up, you could pass enough state
2027  * down the chain to make up the parent kqueue.  Make this code functional
2028  * first.
2029  */
2030 void
2031 knote(struct knlist *list, long hint, int lockflags)
2032 {
2033 	struct kqueue *kq;
2034 	struct knote *kn, *tkn;
2035 	int error;
2036 
2037 	if (list == NULL)
2038 		return;
2039 
2040 	KNL_ASSERT_LOCK(list, lockflags & KNF_LISTLOCKED);
2041 
2042 	if ((lockflags & KNF_LISTLOCKED) == 0)
2043 		list->kl_lock(list->kl_lockarg);
2044 
2045 	/*
2046 	 * If we unlock the list lock (and enter influx), we can
2047 	 * eliminate the kqueue scheduling, but this will introduce
2048 	 * four lock/unlock's for each knote to test.  Also, marker
2049 	 * would be needed to keep iteration position, since filters
2050 	 * or other threads could remove events.
2051 	 */
2052 	SLIST_FOREACH_SAFE(kn, &list->kl_list, kn_selnext, tkn) {
2053 		kq = kn->kn_kq;
2054 		KQ_LOCK(kq);
2055 		if (kn_in_flux(kn) && (kn->kn_status & KN_SCAN) == 0) {
2056 			/*
2057 			 * Do not process the influx notes, except for
2058 			 * the influx coming from the kq unlock in the
2059 			 * kqueue_scan().  In the later case, we do
2060 			 * not interfere with the scan, since the code
2061 			 * fragment in kqueue_scan() locks the knlist,
2062 			 * and cannot proceed until we finished.
2063 			 */
2064 			KQ_UNLOCK(kq);
2065 		} else if ((lockflags & KNF_NOKQLOCK) != 0) {
2066 			kn_enter_flux(kn);
2067 			KQ_UNLOCK(kq);
2068 			error = kn->kn_fop->f_event(kn, hint);
2069 			KQ_LOCK(kq);
2070 			kn_leave_flux(kn);
2071 			if (error)
2072 				KNOTE_ACTIVATE(kn, 1);
2073 			KQ_UNLOCK_FLUX(kq);
2074 		} else {
2075 			kn->kn_status |= KN_HASKQLOCK;
2076 			if (kn->kn_fop->f_event(kn, hint))
2077 				KNOTE_ACTIVATE(kn, 1);
2078 			kn->kn_status &= ~KN_HASKQLOCK;
2079 			KQ_UNLOCK(kq);
2080 		}
2081 	}
2082 	if ((lockflags & KNF_LISTLOCKED) == 0)
2083 		list->kl_unlock(list->kl_lockarg);
2084 }
2085 
2086 /*
2087  * add a knote to a knlist
2088  */
2089 void
2090 knlist_add(struct knlist *knl, struct knote *kn, int islocked)
2091 {
2092 
2093 	KNL_ASSERT_LOCK(knl, islocked);
2094 	KQ_NOTOWNED(kn->kn_kq);
2095 	KASSERT(kn_in_flux(kn), ("knote %p not in flux", kn));
2096 	KASSERT((kn->kn_status & KN_DETACHED) != 0,
2097 	    ("knote %p was not detached", kn));
2098 	if (!islocked)
2099 		knl->kl_lock(knl->kl_lockarg);
2100 	SLIST_INSERT_HEAD(&knl->kl_list, kn, kn_selnext);
2101 	if (!islocked)
2102 		knl->kl_unlock(knl->kl_lockarg);
2103 	KQ_LOCK(kn->kn_kq);
2104 	kn->kn_knlist = knl;
2105 	kn->kn_status &= ~KN_DETACHED;
2106 	KQ_UNLOCK(kn->kn_kq);
2107 }
2108 
2109 static void
2110 knlist_remove_kq(struct knlist *knl, struct knote *kn, int knlislocked,
2111     int kqislocked)
2112 {
2113 
2114 	KASSERT(!kqislocked || knlislocked, ("kq locked w/o knl locked"));
2115 	KNL_ASSERT_LOCK(knl, knlislocked);
2116 	mtx_assert(&kn->kn_kq->kq_lock, kqislocked ? MA_OWNED : MA_NOTOWNED);
2117 	KASSERT(kqislocked || kn_in_flux(kn), ("knote %p not in flux", kn));
2118 	KASSERT((kn->kn_status & KN_DETACHED) == 0,
2119 	    ("knote %p was already detached", kn));
2120 	if (!knlislocked)
2121 		knl->kl_lock(knl->kl_lockarg);
2122 	SLIST_REMOVE(&knl->kl_list, kn, knote, kn_selnext);
2123 	kn->kn_knlist = NULL;
2124 	if (!knlislocked)
2125 		kn_list_unlock(knl);
2126 	if (!kqislocked)
2127 		KQ_LOCK(kn->kn_kq);
2128 	kn->kn_status |= KN_DETACHED;
2129 	if (!kqislocked)
2130 		KQ_UNLOCK(kn->kn_kq);
2131 }
2132 
2133 /*
2134  * remove knote from the specified knlist
2135  */
2136 void
2137 knlist_remove(struct knlist *knl, struct knote *kn, int islocked)
2138 {
2139 
2140 	knlist_remove_kq(knl, kn, islocked, 0);
2141 }
2142 
2143 int
2144 knlist_empty(struct knlist *knl)
2145 {
2146 
2147 	KNL_ASSERT_LOCKED(knl);
2148 	return (SLIST_EMPTY(&knl->kl_list));
2149 }
2150 
2151 static struct mtx knlist_lock;
2152 MTX_SYSINIT(knlist_lock, &knlist_lock, "knlist lock for lockless objects",
2153     MTX_DEF);
2154 static void knlist_mtx_lock(void *arg);
2155 static void knlist_mtx_unlock(void *arg);
2156 
2157 static void
2158 knlist_mtx_lock(void *arg)
2159 {
2160 
2161 	mtx_lock((struct mtx *)arg);
2162 }
2163 
2164 static void
2165 knlist_mtx_unlock(void *arg)
2166 {
2167 
2168 	mtx_unlock((struct mtx *)arg);
2169 }
2170 
2171 static void
2172 knlist_mtx_assert_locked(void *arg)
2173 {
2174 
2175 	mtx_assert((struct mtx *)arg, MA_OWNED);
2176 }
2177 
2178 static void
2179 knlist_mtx_assert_unlocked(void *arg)
2180 {
2181 
2182 	mtx_assert((struct mtx *)arg, MA_NOTOWNED);
2183 }
2184 
2185 static void
2186 knlist_rw_rlock(void *arg)
2187 {
2188 
2189 	rw_rlock((struct rwlock *)arg);
2190 }
2191 
2192 static void
2193 knlist_rw_runlock(void *arg)
2194 {
2195 
2196 	rw_runlock((struct rwlock *)arg);
2197 }
2198 
2199 static void
2200 knlist_rw_assert_locked(void *arg)
2201 {
2202 
2203 	rw_assert((struct rwlock *)arg, RA_LOCKED);
2204 }
2205 
2206 static void
2207 knlist_rw_assert_unlocked(void *arg)
2208 {
2209 
2210 	rw_assert((struct rwlock *)arg, RA_UNLOCKED);
2211 }
2212 
2213 void
2214 knlist_init(struct knlist *knl, void *lock, void (*kl_lock)(void *),
2215     void (*kl_unlock)(void *),
2216     void (*kl_assert_locked)(void *), void (*kl_assert_unlocked)(void *))
2217 {
2218 
2219 	if (lock == NULL)
2220 		knl->kl_lockarg = &knlist_lock;
2221 	else
2222 		knl->kl_lockarg = lock;
2223 
2224 	if (kl_lock == NULL)
2225 		knl->kl_lock = knlist_mtx_lock;
2226 	else
2227 		knl->kl_lock = kl_lock;
2228 	if (kl_unlock == NULL)
2229 		knl->kl_unlock = knlist_mtx_unlock;
2230 	else
2231 		knl->kl_unlock = kl_unlock;
2232 	if (kl_assert_locked == NULL)
2233 		knl->kl_assert_locked = knlist_mtx_assert_locked;
2234 	else
2235 		knl->kl_assert_locked = kl_assert_locked;
2236 	if (kl_assert_unlocked == NULL)
2237 		knl->kl_assert_unlocked = knlist_mtx_assert_unlocked;
2238 	else
2239 		knl->kl_assert_unlocked = kl_assert_unlocked;
2240 
2241 	knl->kl_autodestroy = 0;
2242 	SLIST_INIT(&knl->kl_list);
2243 }
2244 
2245 void
2246 knlist_init_mtx(struct knlist *knl, struct mtx *lock)
2247 {
2248 
2249 	knlist_init(knl, lock, NULL, NULL, NULL, NULL);
2250 }
2251 
2252 struct knlist *
2253 knlist_alloc(struct mtx *lock)
2254 {
2255 	struct knlist *knl;
2256 
2257 	knl = malloc(sizeof(struct knlist), M_KQUEUE, M_WAITOK);
2258 	knlist_init_mtx(knl, lock);
2259 	return (knl);
2260 }
2261 
2262 void
2263 knlist_init_rw_reader(struct knlist *knl, struct rwlock *lock)
2264 {
2265 
2266 	knlist_init(knl, lock, knlist_rw_rlock, knlist_rw_runlock,
2267 	    knlist_rw_assert_locked, knlist_rw_assert_unlocked);
2268 }
2269 
2270 void
2271 knlist_destroy(struct knlist *knl)
2272 {
2273 
2274 	KASSERT(KNLIST_EMPTY(knl),
2275 	    ("destroying knlist %p with knotes on it", knl));
2276 }
2277 
2278 void
2279 knlist_detach(struct knlist *knl)
2280 {
2281 
2282 	KNL_ASSERT_LOCKED(knl);
2283 	knl->kl_autodestroy = 1;
2284 	if (knlist_empty(knl)) {
2285 		knlist_destroy(knl);
2286 		free(knl, M_KQUEUE);
2287 	}
2288 }
2289 
2290 /*
2291  * Even if we are locked, we may need to drop the lock to allow any influx
2292  * knotes time to "settle".
2293  */
2294 void
2295 knlist_cleardel(struct knlist *knl, struct thread *td, int islocked, int killkn)
2296 {
2297 	struct knote *kn, *kn2;
2298 	struct kqueue *kq;
2299 
2300 	KASSERT(!knl->kl_autodestroy, ("cleardel for autodestroy %p", knl));
2301 	if (islocked)
2302 		KNL_ASSERT_LOCKED(knl);
2303 	else {
2304 		KNL_ASSERT_UNLOCKED(knl);
2305 again:		/* need to reacquire lock since we have dropped it */
2306 		knl->kl_lock(knl->kl_lockarg);
2307 	}
2308 
2309 	SLIST_FOREACH_SAFE(kn, &knl->kl_list, kn_selnext, kn2) {
2310 		kq = kn->kn_kq;
2311 		KQ_LOCK(kq);
2312 		if (kn_in_flux(kn)) {
2313 			KQ_UNLOCK(kq);
2314 			continue;
2315 		}
2316 		knlist_remove_kq(knl, kn, 1, 1);
2317 		if (killkn) {
2318 			kn_enter_flux(kn);
2319 			KQ_UNLOCK(kq);
2320 			knote_drop_detached(kn, td);
2321 		} else {
2322 			/* Make sure cleared knotes disappear soon */
2323 			kn->kn_flags |= EV_EOF | EV_ONESHOT;
2324 			KQ_UNLOCK(kq);
2325 		}
2326 		kq = NULL;
2327 	}
2328 
2329 	if (!SLIST_EMPTY(&knl->kl_list)) {
2330 		/* there are still in flux knotes remaining */
2331 		kn = SLIST_FIRST(&knl->kl_list);
2332 		kq = kn->kn_kq;
2333 		KQ_LOCK(kq);
2334 		KASSERT(kn_in_flux(kn), ("knote removed w/o list lock"));
2335 		knl->kl_unlock(knl->kl_lockarg);
2336 		kq->kq_state |= KQ_FLUXWAIT;
2337 		msleep(kq, &kq->kq_lock, PSOCK | PDROP, "kqkclr", 0);
2338 		kq = NULL;
2339 		goto again;
2340 	}
2341 
2342 	if (islocked)
2343 		KNL_ASSERT_LOCKED(knl);
2344 	else {
2345 		knl->kl_unlock(knl->kl_lockarg);
2346 		KNL_ASSERT_UNLOCKED(knl);
2347 	}
2348 }
2349 
2350 /*
2351  * Remove all knotes referencing a specified fd must be called with FILEDESC
2352  * lock.  This prevents a race where a new fd comes along and occupies the
2353  * entry and we attach a knote to the fd.
2354  */
2355 void
2356 knote_fdclose(struct thread *td, int fd)
2357 {
2358 	struct filedesc *fdp = td->td_proc->p_fd;
2359 	struct kqueue *kq;
2360 	struct knote *kn;
2361 	int influx;
2362 
2363 	FILEDESC_XLOCK_ASSERT(fdp);
2364 
2365 	/*
2366 	 * We shouldn't have to worry about new kevents appearing on fd
2367 	 * since filedesc is locked.
2368 	 */
2369 	TAILQ_FOREACH(kq, &fdp->fd_kqlist, kq_list) {
2370 		KQ_LOCK(kq);
2371 
2372 again:
2373 		influx = 0;
2374 		while (kq->kq_knlistsize > fd &&
2375 		    (kn = SLIST_FIRST(&kq->kq_knlist[fd])) != NULL) {
2376 			if (kn_in_flux(kn)) {
2377 				/* someone else might be waiting on our knote */
2378 				if (influx)
2379 					wakeup(kq);
2380 				kq->kq_state |= KQ_FLUXWAIT;
2381 				msleep(kq, &kq->kq_lock, PSOCK, "kqflxwt", 0);
2382 				goto again;
2383 			}
2384 			kn_enter_flux(kn);
2385 			KQ_UNLOCK(kq);
2386 			influx = 1;
2387 			knote_drop(kn, td);
2388 			KQ_LOCK(kq);
2389 		}
2390 		KQ_UNLOCK_FLUX(kq);
2391 	}
2392 }
2393 
2394 static int
2395 knote_attach(struct knote *kn, struct kqueue *kq)
2396 {
2397 	struct klist *list;
2398 
2399 	KASSERT(kn_in_flux(kn), ("knote %p not marked influx", kn));
2400 	KQ_OWNED(kq);
2401 
2402 	if (kn->kn_fop->f_isfd) {
2403 		if (kn->kn_id >= kq->kq_knlistsize)
2404 			return (ENOMEM);
2405 		list = &kq->kq_knlist[kn->kn_id];
2406 	} else {
2407 		if (kq->kq_knhash == NULL)
2408 			return (ENOMEM);
2409 		list = &kq->kq_knhash[KN_HASH(kn->kn_id, kq->kq_knhashmask)];
2410 	}
2411 	SLIST_INSERT_HEAD(list, kn, kn_link);
2412 	return (0);
2413 }
2414 
2415 static void
2416 knote_drop(struct knote *kn, struct thread *td)
2417 {
2418 
2419 	if ((kn->kn_status & KN_DETACHED) == 0)
2420 		kn->kn_fop->f_detach(kn);
2421 	knote_drop_detached(kn, td);
2422 }
2423 
2424 static void
2425 knote_drop_detached(struct knote *kn, struct thread *td)
2426 {
2427 	struct kqueue *kq;
2428 	struct klist *list;
2429 
2430 	kq = kn->kn_kq;
2431 
2432 	KASSERT((kn->kn_status & KN_DETACHED) != 0,
2433 	    ("knote %p still attached", kn));
2434 	KQ_NOTOWNED(kq);
2435 
2436 	KQ_LOCK(kq);
2437 	KASSERT(kn->kn_influx == 1,
2438 	    ("knote_drop called on %p with influx %d", kn, kn->kn_influx));
2439 
2440 	if (kn->kn_fop->f_isfd)
2441 		list = &kq->kq_knlist[kn->kn_id];
2442 	else
2443 		list = &kq->kq_knhash[KN_HASH(kn->kn_id, kq->kq_knhashmask)];
2444 
2445 	if (!SLIST_EMPTY(list))
2446 		SLIST_REMOVE(list, kn, knote, kn_link);
2447 	if (kn->kn_status & KN_QUEUED)
2448 		knote_dequeue(kn);
2449 	KQ_UNLOCK_FLUX(kq);
2450 
2451 	if (kn->kn_fop->f_isfd) {
2452 		fdrop(kn->kn_fp, td);
2453 		kn->kn_fp = NULL;
2454 	}
2455 	kqueue_fo_release(kn->kn_kevent.filter);
2456 	kn->kn_fop = NULL;
2457 	knote_free(kn);
2458 }
2459 
2460 static void
2461 knote_enqueue(struct knote *kn)
2462 {
2463 	struct kqueue *kq = kn->kn_kq;
2464 
2465 	KQ_OWNED(kn->kn_kq);
2466 	KASSERT((kn->kn_status & KN_QUEUED) == 0, ("knote already queued"));
2467 
2468 	TAILQ_INSERT_TAIL(&kq->kq_head, kn, kn_tqe);
2469 	kn->kn_status |= KN_QUEUED;
2470 	kq->kq_count++;
2471 	kqueue_wakeup(kq);
2472 }
2473 
2474 static void
2475 knote_dequeue(struct knote *kn)
2476 {
2477 	struct kqueue *kq = kn->kn_kq;
2478 
2479 	KQ_OWNED(kn->kn_kq);
2480 	KASSERT(kn->kn_status & KN_QUEUED, ("knote not queued"));
2481 
2482 	TAILQ_REMOVE(&kq->kq_head, kn, kn_tqe);
2483 	kn->kn_status &= ~KN_QUEUED;
2484 	kq->kq_count--;
2485 }
2486 
2487 static void
2488 knote_init(void)
2489 {
2490 
2491 	knote_zone = uma_zcreate("KNOTE", sizeof(struct knote), NULL, NULL,
2492 	    NULL, NULL, UMA_ALIGN_PTR, 0);
2493 }
2494 SYSINIT(knote, SI_SUB_PSEUDO, SI_ORDER_ANY, knote_init, NULL);
2495 
2496 static struct knote *
2497 knote_alloc(int waitok)
2498 {
2499 
2500 	return (uma_zalloc(knote_zone, (waitok ? M_WAITOK : M_NOWAIT) |
2501 	    M_ZERO));
2502 }
2503 
2504 static void
2505 knote_free(struct knote *kn)
2506 {
2507 
2508 	uma_zfree(knote_zone, kn);
2509 }
2510 
2511 /*
2512  * Register the kev w/ the kq specified by fd.
2513  */
2514 int
2515 kqfd_register(int fd, struct kevent *kev, struct thread *td, int waitok)
2516 {
2517 	struct kqueue *kq;
2518 	struct file *fp;
2519 	cap_rights_t rights;
2520 	int error;
2521 
2522 	error = fget(td, fd, cap_rights_init(&rights, CAP_KQUEUE_CHANGE), &fp);
2523 	if (error != 0)
2524 		return (error);
2525 	if ((error = kqueue_acquire(fp, &kq)) != 0)
2526 		goto noacquire;
2527 
2528 	error = kqueue_register(kq, kev, td, waitok);
2529 	kqueue_release(kq, 0);
2530 
2531 noacquire:
2532 	fdrop(fp, td);
2533 	return (error);
2534 }
2535