proc->thread stage 4: rework the VFS and DEVICE subsystems to take thread
[dragonfly.git] / sys / kern / kern_event.c
1 /*-
2  * Copyright (c) 1999,2000,2001 Jonathan Lemon <jlemon@FreeBSD.org>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  *
26  * $FreeBSD: src/sys/kern/kern_event.c,v 1.2.2.9 2003/05/08 07:47:16 kbyanc Exp $
27  * $DragonFly: src/sys/kern/kern_event.c,v 1.4 2003/06/25 03:55:57 dillon Exp $
28  */
29
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/kernel.h>
33 #include <sys/proc.h>
34 #include <sys/malloc.h> 
35 #include <sys/unistd.h>
36 #include <sys/file.h>
37 #include <sys/fcntl.h>
38 #include <sys/select.h>
39 #include <sys/queue.h>
40 #include <sys/event.h>
41 #include <sys/eventvar.h>
42 #include <sys/poll.h>
43 #include <sys/protosw.h>
44 #include <sys/socket.h>
45 #include <sys/socketvar.h>
46 #include <sys/stat.h>
47 #include <sys/sysctl.h>
48 #include <sys/sysproto.h>
49 #include <sys/uio.h>
50 #include <sys/file2.h>
51
52 #include <vm/vm_zone.h>
53
54 MALLOC_DEFINE(M_KQUEUE, "kqueue", "memory for kqueue system");
55
56 static int      kqueue_scan(struct file *fp, int maxevents,
57                     struct kevent *ulistp, const struct timespec *timeout,
58                     struct proc *p);
59 static int      kqueue_read(struct file *fp, struct uio *uio,
60                     struct ucred *cred, int flags, struct thread *td);
61 static int      kqueue_write(struct file *fp, struct uio *uio,
62                     struct ucred *cred, int flags, struct thread *td);
63 static int      kqueue_ioctl(struct file *fp, u_long com, caddr_t data,
64                     struct thread *td);
65 static int      kqueue_poll(struct file *fp, int events, struct ucred *cred,
66                     struct thread *td);
67 static int      kqueue_kqfilter(struct file *fp, struct knote *kn);
68 static int      kqueue_stat(struct file *fp, struct stat *st, struct thread *td);
69 static int      kqueue_close(struct file *fp, struct thread *td);
70 static void     kqueue_wakeup(struct kqueue *kq);
71
72 static struct fileops kqueueops = {
73         kqueue_read,
74         kqueue_write,
75         kqueue_ioctl,
76         kqueue_poll,
77         kqueue_kqfilter,
78         kqueue_stat,
79         kqueue_close
80 };
81
82 static void     knote_attach(struct knote *kn, struct filedesc *fdp);
83 static void     knote_drop(struct knote *kn, struct thread *td);
84 static void     knote_enqueue(struct knote *kn);
85 static void     knote_dequeue(struct knote *kn);
86 static void     knote_init(void);
87 static struct   knote *knote_alloc(void);
88 static void     knote_free(struct knote *kn);
89
90 static void     filt_kqdetach(struct knote *kn);
91 static int      filt_kqueue(struct knote *kn, long hint);
92 static int      filt_procattach(struct knote *kn);
93 static void     filt_procdetach(struct knote *kn);
94 static int      filt_proc(struct knote *kn, long hint);
95 static int      filt_fileattach(struct knote *kn);
96 static void     filt_timerexpire(void *knx);
97 static int      filt_timerattach(struct knote *kn);
98 static void     filt_timerdetach(struct knote *kn);
99 static int      filt_timer(struct knote *kn, long hint);
100
101 static struct filterops file_filtops =
102         { 1, filt_fileattach, NULL, NULL };
103 static struct filterops kqread_filtops =
104         { 1, NULL, filt_kqdetach, filt_kqueue };
105 static struct filterops proc_filtops =
106         { 0, filt_procattach, filt_procdetach, filt_proc };
107 static struct filterops timer_filtops =
108         { 0, filt_timerattach, filt_timerdetach, filt_timer };
109
110 static vm_zone_t        knote_zone;
111 static int              kq_ncallouts = 0;
112 static int              kq_calloutmax = (4 * 1024);
113 SYSCTL_INT(_kern, OID_AUTO, kq_calloutmax, CTLFLAG_RW,
114     &kq_calloutmax, 0, "Maximum number of callouts allocated for kqueue");
115
116 #define KNOTE_ACTIVATE(kn) do {                                         \
117         kn->kn_status |= KN_ACTIVE;                                     \
118         if ((kn->kn_status & (KN_QUEUED | KN_DISABLED)) == 0)           \
119                 knote_enqueue(kn);                                      \
120 } while(0)
121
122 #define KN_HASHSIZE             64              /* XXX should be tunable */
123 #define KN_HASH(val, mask)      (((val) ^ (val >> 8)) & (mask))
124
125 extern struct filterops aio_filtops;
126 extern struct filterops sig_filtops;
127
128 /*
129  * Table for for all system-defined filters.
130  */
131 static struct filterops *sysfilt_ops[] = {
132         &file_filtops,                  /* EVFILT_READ */
133         &file_filtops,                  /* EVFILT_WRITE */
134         &aio_filtops,                   /* EVFILT_AIO */
135         &file_filtops,                  /* EVFILT_VNODE */
136         &proc_filtops,                  /* EVFILT_PROC */
137         &sig_filtops,                   /* EVFILT_SIGNAL */
138         &timer_filtops,                 /* EVFILT_TIMER */
139 };
140
141 static int
142 filt_fileattach(struct knote *kn)
143 {
144         return (fo_kqfilter(kn->kn_fp, kn));
145 }
146
147 /*ARGSUSED*/
148 static int
149 kqueue_kqfilter(struct file *fp, struct knote *kn)
150 {
151         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
152
153         if (kn->kn_filter != EVFILT_READ)
154                 return (1);
155
156         kn->kn_fop = &kqread_filtops;
157         SLIST_INSERT_HEAD(&kq->kq_sel.si_note, kn, kn_selnext);
158         return (0);
159 }
160
161 static void
162 filt_kqdetach(struct knote *kn)
163 {
164         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
165
166         SLIST_REMOVE(&kq->kq_sel.si_note, kn, knote, kn_selnext);
167 }
168
169 /*ARGSUSED*/
170 static int
171 filt_kqueue(struct knote *kn, long hint)
172 {
173         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
174
175         kn->kn_data = kq->kq_count;
176         return (kn->kn_data > 0);
177 }
178
179 static int
180 filt_procattach(struct knote *kn)
181 {
182         struct proc *p;
183         int immediate;
184
185         immediate = 0;
186         p = pfind(kn->kn_id);
187         if (p == NULL && (kn->kn_sfflags & NOTE_EXIT)) {
188                 p = zpfind(kn->kn_id);
189                 immediate = 1;
190         }
191         if (p == NULL)
192                 return (ESRCH);
193         if (! PRISON_CHECK(curproc->p_ucred, p->p_ucred))
194                 return (EACCES);
195
196         kn->kn_ptr.p_proc = p;
197         kn->kn_flags |= EV_CLEAR;               /* automatically set */
198
199         /*
200          * internal flag indicating registration done by kernel
201          */
202         if (kn->kn_flags & EV_FLAG1) {
203                 kn->kn_data = kn->kn_sdata;             /* ppid */
204                 kn->kn_fflags = NOTE_CHILD;
205                 kn->kn_flags &= ~EV_FLAG1;
206         }
207
208         /* XXX lock the proc here while adding to the list? */
209         SLIST_INSERT_HEAD(&p->p_klist, kn, kn_selnext);
210
211         /*
212          * Immediately activate any exit notes if the target process is a
213          * zombie.  This is necessary to handle the case where the target
214          * process, e.g. a child, dies before the kevent is registered.
215          */
216         if (immediate && filt_proc(kn, NOTE_EXIT))
217                 KNOTE_ACTIVATE(kn);
218
219         return (0);
220 }
221
222 /*
223  * The knote may be attached to a different process, which may exit,
224  * leaving nothing for the knote to be attached to.  So when the process
225  * exits, the knote is marked as DETACHED and also flagged as ONESHOT so
226  * it will be deleted when read out.  However, as part of the knote deletion,
227  * this routine is called, so a check is needed to avoid actually performing
228  * a detach, because the original process does not exist any more.
229  */
230 static void
231 filt_procdetach(struct knote *kn)
232 {
233         struct proc *p = kn->kn_ptr.p_proc;
234
235         if (kn->kn_status & KN_DETACHED)
236                 return;
237
238         /* XXX locking?  this might modify another process. */
239         SLIST_REMOVE(&p->p_klist, kn, knote, kn_selnext);
240 }
241
242 static int
243 filt_proc(struct knote *kn, long hint)
244 {
245         u_int event;
246
247         /*
248          * mask off extra data
249          */
250         event = (u_int)hint & NOTE_PCTRLMASK;
251
252         /*
253          * if the user is interested in this event, record it.
254          */
255         if (kn->kn_sfflags & event)
256                 kn->kn_fflags |= event;
257
258         /*
259          * process is gone, so flag the event as finished.
260          */
261         if (event == NOTE_EXIT) {
262                 kn->kn_status |= KN_DETACHED;
263                 kn->kn_flags |= (EV_EOF | EV_ONESHOT); 
264                 return (1);
265         }
266
267         /*
268          * process forked, and user wants to track the new process,
269          * so attach a new knote to it, and immediately report an
270          * event with the parent's pid.
271          */
272         if ((event == NOTE_FORK) && (kn->kn_sfflags & NOTE_TRACK)) {
273                 struct kevent kev;
274                 int error;
275
276                 /*
277                  * register knote with new process.
278                  */
279                 kev.ident = hint & NOTE_PDATAMASK;      /* pid */
280                 kev.filter = kn->kn_filter;
281                 kev.flags = kn->kn_flags | EV_ADD | EV_ENABLE | EV_FLAG1;
282                 kev.fflags = kn->kn_sfflags;
283                 kev.data = kn->kn_id;                   /* parent */
284                 kev.udata = kn->kn_kevent.udata;        /* preserve udata */
285                 error = kqueue_register(kn->kn_kq, &kev, NULL);
286                 if (error)
287                         kn->kn_fflags |= NOTE_TRACKERR;
288         }
289
290         return (kn->kn_fflags != 0);
291 }
292
293 static void
294 filt_timerexpire(void *knx)
295 {
296         struct knote *kn = knx;
297         struct callout *calloutp;
298         struct timeval tv;
299         int tticks;
300
301         kn->kn_data++;
302         KNOTE_ACTIVATE(kn);
303
304         if ((kn->kn_flags & EV_ONESHOT) == 0) {
305                 tv.tv_sec = kn->kn_sdata / 1000;
306                 tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
307                 tticks = tvtohz(&tv);
308                 calloutp = (struct callout *)kn->kn_hook;
309                 callout_reset(calloutp, tticks, filt_timerexpire, kn);
310         }
311 }
312
313 /*
314  * data contains amount of time to sleep, in milliseconds
315  */ 
316 static int
317 filt_timerattach(struct knote *kn)
318 {
319         struct callout *calloutp;
320         struct timeval tv;
321         int tticks;
322
323         if (kq_ncallouts >= kq_calloutmax)
324                 return (ENOMEM);
325         kq_ncallouts++;
326
327         tv.tv_sec = kn->kn_sdata / 1000;
328         tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
329         tticks = tvtohz(&tv);
330
331         kn->kn_flags |= EV_CLEAR;               /* automatically set */
332         MALLOC(calloutp, struct callout *, sizeof(*calloutp),
333             M_KQUEUE, M_WAITOK);
334         callout_init(calloutp);
335         callout_reset(calloutp, tticks, filt_timerexpire, kn);
336         kn->kn_hook = (caddr_t)calloutp;
337
338         return (0);
339 }
340
341 static void
342 filt_timerdetach(struct knote *kn)
343 {
344         struct callout *calloutp;
345
346         calloutp = (struct callout *)kn->kn_hook;
347         callout_stop(calloutp);
348         FREE(calloutp, M_KQUEUE);
349         kq_ncallouts--;
350 }
351
352 static int
353 filt_timer(struct knote *kn, long hint)
354 {
355
356         return (kn->kn_data != 0);
357 }
358
359 int
360 kqueue(struct kqueue_args *uap)
361 {
362         struct proc *p = curproc;
363         struct filedesc *fdp = p->p_fd;
364         struct kqueue *kq;
365         struct file *fp;
366         int fd, error;
367
368         error = falloc(p, &fp, &fd);
369         if (error)
370                 return (error);
371         fp->f_flag = FREAD | FWRITE;
372         fp->f_type = DTYPE_KQUEUE;
373         fp->f_ops = &kqueueops;
374         kq = malloc(sizeof(struct kqueue), M_KQUEUE, M_WAITOK | M_ZERO);
375         TAILQ_INIT(&kq->kq_head);
376         fp->f_data = (caddr_t)kq;
377         p->p_retval[0] = fd;
378         if (fdp->fd_knlistsize < 0)
379                 fdp->fd_knlistsize = 0;         /* this process has a kq */
380         kq->kq_fdp = fdp;
381         return (error);
382 }
383
384 #ifndef _SYS_SYSPROTO_H_
385 struct kevent_args {
386         int     fd;
387         const struct kevent *changelist;
388         int     nchanges;
389         struct  kevent *eventlist;
390         int     nevents;
391         const struct timespec *timeout;
392 };
393 #endif
394 int
395 kevent(struct kevent_args *uap)
396 {
397         struct thread *td = curthread;
398         struct proc *p = td->td_proc;
399         struct filedesc *fdp;
400         struct kevent *kevp;
401         struct kqueue *kq;
402         struct file *fp = NULL;
403         struct timespec ts;
404         int i, n, nerrors, error;
405
406         KKASSERT(p);
407         fdp = p->p_fd;
408
409         if (((u_int)uap->fd) >= fdp->fd_nfiles ||
410             (fp = fdp->fd_ofiles[uap->fd]) == NULL ||
411             (fp->f_type != DTYPE_KQUEUE))
412                 return (EBADF);
413
414         fhold(fp);
415
416         if (uap->timeout != NULL) {
417                 error = copyin(uap->timeout, &ts, sizeof(ts));
418                 if (error)
419                         goto done;
420                 uap->timeout = &ts;
421         }
422
423         kq = (struct kqueue *)fp->f_data;
424         nerrors = 0;
425
426         while (uap->nchanges > 0) {
427                 n = uap->nchanges > KQ_NEVENTS ? KQ_NEVENTS : uap->nchanges;
428                 error = copyin(uap->changelist, kq->kq_kev,
429                     n * sizeof(struct kevent));
430                 if (error)
431                         goto done;
432                 for (i = 0; i < n; i++) {
433                         kevp = &kq->kq_kev[i];
434                         kevp->flags &= ~EV_SYSFLAGS;
435                         error = kqueue_register(kq, kevp, td);
436                         if (error) {
437                                 if (uap->nevents != 0) {
438                                         kevp->flags = EV_ERROR;
439                                         kevp->data = error;
440                                         (void) copyout((caddr_t)kevp,
441                                             (caddr_t)uap->eventlist,
442                                             sizeof(*kevp));
443                                         uap->eventlist++;
444                                         uap->nevents--;
445                                         nerrors++;
446                                 } else {
447                                         goto done;
448                                 }
449                         }
450                 }
451                 uap->nchanges -= n;
452                 uap->changelist += n;
453         }
454         if (nerrors) {
455                 p->p_retval[0] = nerrors;
456                 error = 0;
457                 goto done;
458         }
459
460         error = kqueue_scan(fp, uap->nevents, uap->eventlist, uap->timeout, p);
461 done:
462         if (fp != NULL)
463                 fdrop(fp, p->p_thread);
464         return (error);
465 }
466
467 int
468 kqueue_register(struct kqueue *kq, struct kevent *kev, struct thread *td)
469 {
470         struct filedesc *fdp = kq->kq_fdp;
471         struct filterops *fops;
472         struct file *fp = NULL;
473         struct knote *kn = NULL;
474         int s, error = 0;
475
476         if (kev->filter < 0) {
477                 if (kev->filter + EVFILT_SYSCOUNT < 0)
478                         return (EINVAL);
479                 fops = sysfilt_ops[~kev->filter];       /* to 0-base index */
480         } else {
481                 /*
482                  * XXX
483                  * filter attach routine is responsible for insuring that
484                  * the identifier can be attached to it.
485                  */
486                 printf("unknown filter: %d\n", kev->filter);
487                 return (EINVAL);
488         }
489
490         if (fops->f_isfd) {
491                 /* validate descriptor */
492                 if ((u_int)kev->ident >= fdp->fd_nfiles ||
493                     (fp = fdp->fd_ofiles[kev->ident]) == NULL)
494                         return (EBADF);
495                 fhold(fp);
496
497                 if (kev->ident < fdp->fd_knlistsize) {
498                         SLIST_FOREACH(kn, &fdp->fd_knlist[kev->ident], kn_link)
499                                 if (kq == kn->kn_kq &&
500                                     kev->filter == kn->kn_filter)
501                                         break;
502                 }
503         } else {
504                 if (fdp->fd_knhashmask != 0) {
505                         struct klist *list;
506                         
507                         list = &fdp->fd_knhash[
508                             KN_HASH((u_long)kev->ident, fdp->fd_knhashmask)];
509                         SLIST_FOREACH(kn, list, kn_link)
510                                 if (kev->ident == kn->kn_id &&
511                                     kq == kn->kn_kq &&
512                                     kev->filter == kn->kn_filter)
513                                         break;
514                 }
515         }
516
517         if (kn == NULL && ((kev->flags & EV_ADD) == 0)) {
518                 error = ENOENT;
519                 goto done;
520         }
521
522         /*
523          * kn now contains the matching knote, or NULL if no match
524          */
525         if (kev->flags & EV_ADD) {
526
527                 if (kn == NULL) {
528                         kn = knote_alloc();
529                         if (kn == NULL) {
530                                 error = ENOMEM;
531                                 goto done;
532                         }
533                         kn->kn_fp = fp;
534                         kn->kn_kq = kq;
535                         kn->kn_fop = fops;
536
537                         /*
538                          * apply reference count to knote structure, and
539                          * do not release it at the end of this routine.
540                          */
541                         fp = NULL;
542
543                         kn->kn_sfflags = kev->fflags;
544                         kn->kn_sdata = kev->data;
545                         kev->fflags = 0;
546                         kev->data = 0;
547                         kn->kn_kevent = *kev;
548
549                         knote_attach(kn, fdp);
550                         if ((error = fops->f_attach(kn)) != 0) {
551                                 knote_drop(kn, td);
552                                 goto done;
553                         }
554                 } else {
555                         /*
556                          * The user may change some filter values after the
557                          * initial EV_ADD, but doing so will not reset any 
558                          * filter which have already been triggered.
559                          */
560                         kn->kn_sfflags = kev->fflags;
561                         kn->kn_sdata = kev->data;
562                         kn->kn_kevent.udata = kev->udata;
563                 }
564
565                 s = splhigh();
566                 if (kn->kn_fop->f_event(kn, 0))
567                         KNOTE_ACTIVATE(kn);
568                 splx(s);
569
570         } else if (kev->flags & EV_DELETE) {
571                 kn->kn_fop->f_detach(kn);
572                 knote_drop(kn, td);
573                 goto done;
574         }
575
576         if ((kev->flags & EV_DISABLE) &&
577             ((kn->kn_status & KN_DISABLED) == 0)) {
578                 s = splhigh();
579                 kn->kn_status |= KN_DISABLED;
580                 splx(s);
581         }
582
583         if ((kev->flags & EV_ENABLE) && (kn->kn_status & KN_DISABLED)) {
584                 s = splhigh();
585                 kn->kn_status &= ~KN_DISABLED;
586                 if ((kn->kn_status & KN_ACTIVE) &&
587                     ((kn->kn_status & KN_QUEUED) == 0))
588                         knote_enqueue(kn);
589                 splx(s);
590         }
591
592 done:
593         if (fp != NULL)
594                 fdrop(fp, td);
595         return (error);
596 }
597
598 static int
599 kqueue_scan(struct file *fp, int maxevents, struct kevent *ulistp,
600         const struct timespec *tsp, struct proc *p)
601 {
602         struct thread *td = p->p_thread;
603         struct kqueue *kq = (struct kqueue *)fp->f_data;
604         struct kevent *kevp;
605         struct timeval atv, rtv, ttv;
606         struct knote *kn, marker;
607         int s, count, timeout, nkev = 0, error = 0;
608
609         count = maxevents;
610         if (count == 0)
611                 goto done;
612
613         if (tsp != NULL) {
614                 TIMESPEC_TO_TIMEVAL(&atv, tsp);
615                 if (itimerfix(&atv)) {
616                         error = EINVAL;
617                         goto done;
618                 }
619                 if (tsp->tv_sec == 0 && tsp->tv_nsec == 0)
620                         timeout = -1;
621                 else 
622                         timeout = atv.tv_sec > 24 * 60 * 60 ?
623                             24 * 60 * 60 * hz : tvtohz(&atv);
624                 getmicrouptime(&rtv);
625                 timevaladd(&atv, &rtv);
626         } else {
627                 atv.tv_sec = 0;
628                 atv.tv_usec = 0;
629                 timeout = 0;
630         }
631         goto start;
632
633 retry:
634         if (atv.tv_sec || atv.tv_usec) {
635                 getmicrouptime(&rtv);
636                 if (timevalcmp(&rtv, &atv, >=))
637                         goto done;
638                 ttv = atv;
639                 timevalsub(&ttv, &rtv);
640                 timeout = ttv.tv_sec > 24 * 60 * 60 ?
641                         24 * 60 * 60 * hz : tvtohz(&ttv);
642         }
643
644 start:
645         kevp = kq->kq_kev;
646         s = splhigh();
647         if (kq->kq_count == 0) {
648                 if (timeout < 0) { 
649                         error = EWOULDBLOCK;
650                 } else {
651                         kq->kq_state |= KQ_SLEEP;
652                         error = tsleep(kq, PSOCK | PCATCH, "kqread", timeout);
653                 }
654                 splx(s);
655                 if (error == 0)
656                         goto retry;
657                 /* don't restart after signals... */
658                 if (error == ERESTART)
659                         error = EINTR;
660                 else if (error == EWOULDBLOCK)
661                         error = 0;
662                 goto done;
663         }
664
665         TAILQ_INSERT_TAIL(&kq->kq_head, &marker, kn_tqe); 
666         while (count) {
667                 kn = TAILQ_FIRST(&kq->kq_head);
668                 TAILQ_REMOVE(&kq->kq_head, kn, kn_tqe); 
669                 if (kn == &marker) {
670                         splx(s);
671                         if (count == maxevents)
672                                 goto retry;
673                         goto done;
674                 }
675                 if (kn->kn_status & KN_DISABLED) {
676                         kn->kn_status &= ~KN_QUEUED;
677                         kq->kq_count--;
678                         continue;
679                 }
680                 if ((kn->kn_flags & EV_ONESHOT) == 0 &&
681                     kn->kn_fop->f_event(kn, 0) == 0) {
682                         kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE);
683                         kq->kq_count--;
684                         continue;
685                 }
686                 *kevp = kn->kn_kevent;
687                 kevp++;
688                 nkev++;
689                 if (kn->kn_flags & EV_ONESHOT) {
690                         kn->kn_status &= ~KN_QUEUED;
691                         kq->kq_count--;
692                         splx(s);
693                         kn->kn_fop->f_detach(kn);
694                         knote_drop(kn, td);
695                         s = splhigh();
696                 } else if (kn->kn_flags & EV_CLEAR) {
697                         kn->kn_data = 0;
698                         kn->kn_fflags = 0;
699                         kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE);
700                         kq->kq_count--;
701                 } else {
702                         TAILQ_INSERT_TAIL(&kq->kq_head, kn, kn_tqe); 
703                 }
704                 count--;
705                 if (nkev == KQ_NEVENTS) {
706                         splx(s);
707                         error = copyout((caddr_t)&kq->kq_kev, (caddr_t)ulistp,
708                             sizeof(struct kevent) * nkev);
709                         ulistp += nkev;
710                         nkev = 0;
711                         kevp = kq->kq_kev;
712                         s = splhigh();
713                         if (error)
714                                 break;
715                 }
716         }
717         TAILQ_REMOVE(&kq->kq_head, &marker, kn_tqe); 
718         splx(s);
719 done:
720         if (nkev != 0)
721                 error = copyout((caddr_t)&kq->kq_kev, (caddr_t)ulistp,
722                     sizeof(struct kevent) * nkev);
723         p->p_retval[0] = maxevents - count;
724         return (error);
725 }
726
727 /*
728  * XXX
729  * This could be expanded to call kqueue_scan, if desired.
730  */
731 /*ARGSUSED*/
732 static int
733 kqueue_read(struct file *fp, struct uio *uio, struct ucred *cred,
734         int flags, struct thread *td)
735 {
736         return (ENXIO);
737 }
738
739 /*ARGSUSED*/
740 static int
741 kqueue_write(struct file *fp, struct uio *uio, struct ucred *cred,
742          int flags, struct thread *td)
743 {
744         return (ENXIO);
745 }
746
747 /*ARGSUSED*/
748 static int
749 kqueue_ioctl(struct file *fp, u_long com, caddr_t data, struct thread *td)
750 {
751         return (ENOTTY);
752 }
753
754 /*ARGSUSED*/
755 static int
756 kqueue_poll(struct file *fp, int events, struct ucred *cred, struct thread *td)
757 {
758         struct kqueue *kq = (struct kqueue *)fp->f_data;
759         int revents = 0;
760         int s = splnet();
761
762         if (events & (POLLIN | POLLRDNORM)) {
763                 if (kq->kq_count) {
764                         revents |= events & (POLLIN | POLLRDNORM);
765                 } else {
766                         selrecord(td, &kq->kq_sel);
767                         kq->kq_state |= KQ_SEL;
768                 }
769         }
770         splx(s);
771         return (revents);
772 }
773
774 /*ARGSUSED*/
775 static int
776 kqueue_stat(struct file *fp, struct stat *st, struct thread *td)
777 {
778         struct kqueue *kq = (struct kqueue *)fp->f_data;
779
780         bzero((void *)st, sizeof(*st));
781         st->st_size = kq->kq_count;
782         st->st_blksize = sizeof(struct kevent);
783         st->st_mode = S_IFIFO;
784         return (0);
785 }
786
787 /*ARGSUSED*/
788 static int
789 kqueue_close(struct file *fp, struct thread *td)
790 {
791         struct proc *p = td->td_proc;
792         struct kqueue *kq = (struct kqueue *)fp->f_data;
793         struct filedesc *fdp;
794         struct knote **knp, *kn, *kn0;
795         int i;
796
797         KKASSERT(p);
798         fdp = p->p_fd;
799         for (i = 0; i < fdp->fd_knlistsize; i++) {
800                 knp = &SLIST_FIRST(&fdp->fd_knlist[i]);
801                 kn = *knp;
802                 while (kn != NULL) {
803                         kn0 = SLIST_NEXT(kn, kn_link);
804                         if (kq == kn->kn_kq) {
805                                 kn->kn_fop->f_detach(kn);
806                                 fdrop(kn->kn_fp, td);
807                                 knote_free(kn);
808                                 *knp = kn0;
809                         } else {
810                                 knp = &SLIST_NEXT(kn, kn_link);
811                         }
812                         kn = kn0;
813                 }
814         }
815         if (fdp->fd_knhashmask != 0) {
816                 for (i = 0; i < fdp->fd_knhashmask + 1; i++) {
817                         knp = &SLIST_FIRST(&fdp->fd_knhash[i]);
818                         kn = *knp;
819                         while (kn != NULL) {
820                                 kn0 = SLIST_NEXT(kn, kn_link);
821                                 if (kq == kn->kn_kq) {
822                                         kn->kn_fop->f_detach(kn);
823                 /* XXX non-fd release of kn->kn_ptr */
824                                         knote_free(kn);
825                                         *knp = kn0;
826                                 } else {
827                                         knp = &SLIST_NEXT(kn, kn_link);
828                                 }
829                                 kn = kn0;
830                         }
831                 }
832         }
833         free(kq, M_KQUEUE);
834         fp->f_data = NULL;
835
836         return (0);
837 }
838
839 static void
840 kqueue_wakeup(struct kqueue *kq)
841 {
842
843         if (kq->kq_state & KQ_SLEEP) {
844                 kq->kq_state &= ~KQ_SLEEP;
845                 wakeup(kq);
846         }
847         if (kq->kq_state & KQ_SEL) {
848                 kq->kq_state &= ~KQ_SEL;
849                 selwakeup(&kq->kq_sel);
850         }
851         KNOTE(&kq->kq_sel.si_note, 0);
852 }
853
854 /*
855  * walk down a list of knotes, activating them if their event has triggered.
856  */
857 void
858 knote(struct klist *list, long hint)
859 {
860         struct knote *kn;
861
862         SLIST_FOREACH(kn, list, kn_selnext)
863                 if (kn->kn_fop->f_event(kn, hint))
864                         KNOTE_ACTIVATE(kn);
865 }
866
867 /*
868  * remove all knotes from a specified klist
869  */
870 void
871 knote_remove(struct thread *td, struct klist *list)
872 {
873         struct knote *kn;
874
875         while ((kn = SLIST_FIRST(list)) != NULL) {
876                 kn->kn_fop->f_detach(kn);
877                 knote_drop(kn, td);
878         }
879 }
880
881 /*
882  * remove all knotes referencing a specified fd
883  */
884 void
885 knote_fdclose(struct proc *p, int fd)
886 {
887         struct filedesc *fdp = p->p_fd;
888         struct klist *list = &fdp->fd_knlist[fd];
889
890         knote_remove(p->p_thread, list);
891 }
892
893 static void
894 knote_attach(struct knote *kn, struct filedesc *fdp)
895 {
896         struct klist *list;
897         int size;
898
899         if (! kn->kn_fop->f_isfd) {
900                 if (fdp->fd_knhashmask == 0)
901                         fdp->fd_knhash = hashinit(KN_HASHSIZE, M_KQUEUE,
902                             &fdp->fd_knhashmask);
903                 list = &fdp->fd_knhash[KN_HASH(kn->kn_id, fdp->fd_knhashmask)];
904                 goto done;
905         }
906
907         if (fdp->fd_knlistsize <= kn->kn_id) {
908                 size = fdp->fd_knlistsize;
909                 while (size <= kn->kn_id)
910                         size += KQEXTENT;
911                 MALLOC(list, struct klist *,
912                     size * sizeof(struct klist *), M_KQUEUE, M_WAITOK);
913                 bcopy((caddr_t)fdp->fd_knlist, (caddr_t)list,
914                     fdp->fd_knlistsize * sizeof(struct klist *));
915                 bzero((caddr_t)list +
916                     fdp->fd_knlistsize * sizeof(struct klist *),
917                     (size - fdp->fd_knlistsize) * sizeof(struct klist *));
918                 if (fdp->fd_knlist != NULL)
919                         FREE(fdp->fd_knlist, M_KQUEUE);
920                 fdp->fd_knlistsize = size;
921                 fdp->fd_knlist = list;
922         }
923         list = &fdp->fd_knlist[kn->kn_id];
924 done:
925         SLIST_INSERT_HEAD(list, kn, kn_link);
926         kn->kn_status = 0;
927 }
928
929 /*
930  * should be called at spl == 0, since we don't want to hold spl
931  * while calling fdrop and free.
932  */
933 static void
934 knote_drop(struct knote *kn, struct thread *td)
935 {
936         struct filedesc *fdp;
937         struct klist *list;
938
939         KKASSERT(td->td_proc);
940         fdp = td->td_proc->p_fd;
941         if (kn->kn_fop->f_isfd)
942                 list = &fdp->fd_knlist[kn->kn_id];
943         else
944                 list = &fdp->fd_knhash[KN_HASH(kn->kn_id, fdp->fd_knhashmask)];
945
946         SLIST_REMOVE(list, kn, knote, kn_link);
947         if (kn->kn_status & KN_QUEUED)
948                 knote_dequeue(kn);
949         if (kn->kn_fop->f_isfd)
950                 fdrop(kn->kn_fp, td);
951         knote_free(kn);
952 }
953
954
955 static void
956 knote_enqueue(struct knote *kn)
957 {
958         struct kqueue *kq = kn->kn_kq;
959         int s = splhigh();
960
961         KASSERT((kn->kn_status & KN_QUEUED) == 0, ("knote already queued"));
962
963         TAILQ_INSERT_TAIL(&kq->kq_head, kn, kn_tqe); 
964         kn->kn_status |= KN_QUEUED;
965         kq->kq_count++;
966         splx(s);
967         kqueue_wakeup(kq);
968 }
969
970 static void
971 knote_dequeue(struct knote *kn)
972 {
973         struct kqueue *kq = kn->kn_kq;
974         int s = splhigh();
975
976         KASSERT(kn->kn_status & KN_QUEUED, ("knote not queued"));
977
978         TAILQ_REMOVE(&kq->kq_head, kn, kn_tqe); 
979         kn->kn_status &= ~KN_QUEUED;
980         kq->kq_count--;
981         splx(s);
982 }
983
984 static void
985 knote_init(void)
986 {
987         knote_zone = zinit("KNOTE", sizeof(struct knote), 0, 0, 1);
988 }
989 SYSINIT(knote, SI_SUB_PSEUDO, SI_ORDER_ANY, knote_init, NULL)
990
991 static struct knote *
992 knote_alloc(void)
993 {
994         return ((struct knote *)zalloc(knote_zone));
995 }
996
997 static void
998 knote_free(struct knote *kn)
999 {
1000         zfree(knote_zone, kn);
1001 }