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.10 2004/04/04 07:03:14 cperciva Exp $
  27  * $DragonFly: src/sys/kern/kern_event.c,v 1.31 2006/12/23 00:35:04 swildner 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/lock.h>
  38 #include <sys/fcntl.h>
  39 #include <sys/select.h>
  40 #include <sys/queue.h>
  41 #include <sys/event.h>
  42 #include <sys/eventvar.h>
  43 #include <sys/poll.h>
  44 #include <sys/protosw.h>
  45 #include <sys/socket.h>
  46 #include <sys/socketvar.h>
  47 #include <sys/stat.h>
  48 #include <sys/sysctl.h>
  49 #include <sys/sysproto.h>
  50 #include <sys/uio.h>
  51 #include <sys/thread2.h>
  52 #include <sys/file2.h>
  53
  54 #include <vm/vm_zone.h>
  55
  56 MALLOC_DEFINE(M_KQUEUE, "kqueue", "memory for kqueue system");
  57
  58 static int      kqueue_scan(struct file *fp, int maxevents,
  59                     struct kevent *ulistp, const struct timespec *timeout,
  60                     struct thread *td, int *res);
  61 static int      kqueue_read(struct file *fp, struct uio *uio,
  62                     struct ucred *cred, int flags);
  63 static int      kqueue_write(struct file *fp, struct uio *uio,
  64                     struct ucred *cred, int flags);
  65 static int      kqueue_ioctl(struct file *fp, u_long com, caddr_t data,
  66                     struct ucred *cred);
  67 static int      kqueue_poll(struct file *fp, int events, struct ucred *cred);
  68 static int      kqueue_kqfilter(struct file *fp, struct knote *kn);
  69 static int      kqueue_stat(struct file *fp, struct stat *st,
  70                     struct ucred *cred);
  71 static int      kqueue_close(struct file *fp);
  72 static void     kqueue_wakeup(struct kqueue *kq);
  73
  74 /*
  75  * MPSAFE
  76  */
  77 static struct fileops kqueueops = {
  78         .fo_read = kqueue_read,
  79         .fo_write = kqueue_write,
  80         .fo_ioctl = kqueue_ioctl,
  81         .fo_poll = kqueue_poll,
  82         .fo_kqfilter = kqueue_kqfilter,
  83         .fo_stat = kqueue_stat,
  84         .fo_close = kqueue_close,
  85         .fo_shutdown = nofo_shutdown
  86 };
  87
  88 static void     knote_attach(struct knote *kn, struct filedesc *fdp);
  89 static void     knote_drop(struct knote *kn, struct thread *td);
  90 static void     knote_enqueue(struct knote *kn);
  91 static void     knote_dequeue(struct knote *kn);
  92 static void     knote_init(void);
  93 static struct   knote *knote_alloc(void);
  94 static void     knote_free(struct knote *kn);
  95
  96 static void     filt_kqdetach(struct knote *kn);
  97 static int      filt_kqueue(struct knote *kn, long hint);
  98 static int      filt_procattach(struct knote *kn);
  99 static void     filt_procdetach(struct knote *kn);
 100 static int      filt_proc(struct knote *kn, long hint);
 101 static int      filt_fileattach(struct knote *kn);
 102 static void     filt_timerexpire(void *knx);
 103 static int      filt_timerattach(struct knote *kn);
 104 static void     filt_timerdetach(struct knote *kn);
 105 static int      filt_timer(struct knote *kn, long hint);
 106
 107 static struct filterops file_filtops =
 108         { 1, filt_fileattach, NULL, NULL };
 109 static struct filterops kqread_filtops =
 110         { 1, NULL, filt_kqdetach, filt_kqueue };
 111 static struct filterops proc_filtops =
 112         { 0, filt_procattach, filt_procdetach, filt_proc };
 113 static struct filterops timer_filtops =
 114         { 0, filt_timerattach, filt_timerdetach, filt_timer };
 115
 116 static vm_zone_t        knote_zone;
 117 static int              kq_ncallouts = 0;
 118 static int              kq_calloutmax = (4 * 1024);
 119 SYSCTL_INT(_kern, OID_AUTO, kq_calloutmax, CTLFLAG_RW,
 120     &kq_calloutmax, 0, "Maximum number of callouts allocated for kqueue");
 121
 122 #define KNOTE_ACTIVATE(kn) do {                                         \
 123         kn->kn_status |= KN_ACTIVE;                                     \
 124         if ((kn->kn_status & (KN_QUEUED | KN_DISABLED)) == 0)           \
 125                 knote_enqueue(kn);                                      \
 126 } while(0)
 127
 128 #define KN_HASHSIZE             64              /* XXX should be tunable */
 129 #define KN_HASH(val, mask)      (((val) ^ (val >> 8)) & (mask))
 130
 131 extern struct filterops aio_filtops;
 132 extern struct filterops sig_filtops;
 133
 134 /*
 135  * Table for for all system-defined filters.
 136  */
 137 static struct filterops *sysfilt_ops[] = {
 138         &file_filtops,                  /* EVFILT_READ */
 139         &file_filtops,                  /* EVFILT_WRITE */
 140         &aio_filtops,                   /* EVFILT_AIO */
 141         &file_filtops,                  /* EVFILT_VNODE */
 142         &proc_filtops,                  /* EVFILT_PROC */
 143         &sig_filtops,                   /* EVFILT_SIGNAL */
 144         &timer_filtops,                 /* EVFILT_TIMER */
 145 };
 146
 147 static int
 148 filt_fileattach(struct knote *kn)
 149 {
 150         return (fo_kqfilter(kn->kn_fp, kn));
 151 }
 152
 153 /*
 154  * MPALMOSTSAFE - acquires mplock
 155  */
 156 static int
 157 kqueue_kqfilter(struct file *fp, struct knote *kn)
 158 {
 159         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 160
 161         get_mplock();
 162         if (kn->kn_filter != EVFILT_READ) {
 163                 rel_mplock();
 164                 return (1);
 165         }
 166
 167         kn->kn_fop = &kqread_filtops;
 168         SLIST_INSERT_HEAD(&kq->kq_sel.si_note, kn, kn_selnext);
 169         rel_mplock();
 170         return (0);
 171 }
 172
 173 static void
 174 filt_kqdetach(struct knote *kn)
 175 {
 176         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 177
 178         SLIST_REMOVE(&kq->kq_sel.si_note, kn, knote, kn_selnext);
 179 }
 180
 181 /*ARGSUSED*/
 182 static int
 183 filt_kqueue(struct knote *kn, long hint)
 184 {
 185         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 186
 187         kn->kn_data = kq->kq_count;
 188         return (kn->kn_data > 0);
 189 }
 190
 191 static int
 192 filt_procattach(struct knote *kn)
 193 {
 194         struct proc *p;
 195         int immediate;
 196
 197         immediate = 0;
 198         p = pfind(kn->kn_id);
 199         if (p == NULL && (kn->kn_sfflags & NOTE_EXIT)) {
 200                 p = zpfind(kn->kn_id);
 201                 immediate = 1;
 202         }
 203         if (p == NULL)
 204                 return (ESRCH);
 205         if (! PRISON_CHECK(curproc->p_ucred, p->p_ucred))
 206                 return (EACCES);
 207
 208         kn->kn_ptr.p_proc = p;
 209         kn->kn_flags |= EV_CLEAR;               /* automatically set */
 210
 211         /*
 212          * internal flag indicating registration done by kernel
 213          */
 214         if (kn->kn_flags & EV_FLAG1) {
 215                 kn->kn_data = kn->kn_sdata;             /* ppid */
 216                 kn->kn_fflags = NOTE_CHILD;
 217                 kn->kn_flags &= ~EV_FLAG1;
 218         }
 219
 220         /* XXX lock the proc here while adding to the list? */
 221         SLIST_INSERT_HEAD(&p->p_klist, kn, kn_selnext);
 222
 223         /*
 224          * Immediately activate any exit notes if the target process is a
 225          * zombie.  This is necessary to handle the case where the target
 226          * process, e.g. a child, dies before the kevent is registered.
 227          */
 228         if (immediate && filt_proc(kn, NOTE_EXIT))
 229                 KNOTE_ACTIVATE(kn);
 230
 231         return (0);
 232 }
 233
 234 /*
 235  * The knote may be attached to a different process, which may exit,
 236  * leaving nothing for the knote to be attached to.  So when the process
 237  * exits, the knote is marked as DETACHED and also flagged as ONESHOT so
 238  * it will be deleted when read out.  However, as part of the knote deletion,
 239  * this routine is called, so a check is needed to avoid actually performing
 240  * a detach, because the original process does not exist any more.
 241  */
 242 static void
 243 filt_procdetach(struct knote *kn)
 244 {
 245         struct proc *p = kn->kn_ptr.p_proc;
 246
 247         if (kn->kn_status & KN_DETACHED)
 248                 return;
 249
 250         /* XXX locking?  this might modify another process. */
 251         SLIST_REMOVE(&p->p_klist, kn, knote, kn_selnext);
 252 }
 253
 254 static int
 255 filt_proc(struct knote *kn, long hint)
 256 {
 257         u_int event;
 258
 259         /*
 260          * mask off extra data
 261          */
 262         event = (u_int)hint & NOTE_PCTRLMASK;
 263
 264         /*
 265          * if the user is interested in this event, record it.
 266          */
 267         if (kn->kn_sfflags & event)
 268                 kn->kn_fflags |= event;
 269
 270         /*
 271          * process is gone, so flag the event as finished.
 272          */
 273         if (event == NOTE_EXIT) {
 274                 kn->kn_status |= KN_DETACHED;
 275                 kn->kn_flags |= (EV_EOF | EV_ONESHOT);
 276                 return (1);
 277         }
 278
 279         /*
 280          * process forked, and user wants to track the new process,
 281          * so attach a new knote to it, and immediately report an
 282          * event with the parent's pid.
 283          */
 284         if ((event == NOTE_FORK) && (kn->kn_sfflags & NOTE_TRACK)) {
 285                 struct kevent kev;
 286                 int error;
 287
 288                 /*
 289                  * register knote with new process.
 290                  */
 291                 kev.ident = hint & NOTE_PDATAMASK;      /* pid */
 292                 kev.filter = kn->kn_filter;
 293                 kev.flags = kn->kn_flags | EV_ADD | EV_ENABLE | EV_FLAG1;
 294                 kev.fflags = kn->kn_sfflags;
 295                 kev.data = kn->kn_id;                   /* parent */
 296                 kev.udata = kn->kn_kevent.udata;        /* preserve udata */
 297                 error = kqueue_register(kn->kn_kq, &kev, NULL);
 298                 if (error)
 299                         kn->kn_fflags |= NOTE_TRACKERR;
 300         }
 301
 302         return (kn->kn_fflags != 0);
 303 }
 304
 305 static void
 306 filt_timerexpire(void *knx)
 307 {
 308         struct knote *kn = knx;
 309         struct callout *calloutp;
 310         struct timeval tv;
 311         int tticks;
 312
 313         kn->kn_data++;
 314         KNOTE_ACTIVATE(kn);
 315
 316         if ((kn->kn_flags & EV_ONESHOT) == 0) {
 317                 tv.tv_sec = kn->kn_sdata / 1000;
 318                 tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
 319                 tticks = tvtohz_high(&tv);
 320                 calloutp = (struct callout *)kn->kn_hook;
 321                 callout_reset(calloutp, tticks, filt_timerexpire, kn);
 322         }
 323 }
 324
 325 /*
 326  * data contains amount of time to sleep, in milliseconds
 327  */
 328 static int
 329 filt_timerattach(struct knote *kn)
 330 {
 331         struct callout *calloutp;
 332         struct timeval tv;
 333         int tticks;
 334
 335         if (kq_ncallouts >= kq_calloutmax)
 336                 return (ENOMEM);
 337         kq_ncallouts++;
 338
 339         tv.tv_sec = kn->kn_sdata / 1000;
 340         tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
 341         tticks = tvtohz_high(&tv);
 342
 343         kn->kn_flags |= EV_CLEAR;               /* automatically set */
 344         MALLOC(calloutp, struct callout *, sizeof(*calloutp),
 345             M_KQUEUE, M_WAITOK);
 346         callout_init(calloutp);
 347         kn->kn_hook = (caddr_t)calloutp;
 348         callout_reset(calloutp, tticks, filt_timerexpire, kn);
 349
 350         return (0);
 351 }
 352
 353 static void
 354 filt_timerdetach(struct knote *kn)
 355 {
 356         struct callout *calloutp;
 357
 358         calloutp = (struct callout *)kn->kn_hook;
 359         callout_stop(calloutp);
 360         FREE(calloutp, M_KQUEUE);
 361         kq_ncallouts--;
 362 }
 363
 364 static int
 365 filt_timer(struct knote *kn, long hint)
 366 {
 367
 368         return (kn->kn_data != 0);
 369 }
 370
 371 int
 372 sys_kqueue(struct kqueue_args *uap)
 373 {
 374         struct proc *p = curproc;
 375         struct filedesc *fdp = p->p_fd;
 376         struct kqueue *kq;
 377         struct file *fp;
 378         int fd, error;
 379
 380         error = falloc(p, &fp, &fd);
 381         if (error)
 382                 return (error);
 383         fp->f_flag = FREAD | FWRITE;
 384         fp->f_type = DTYPE_KQUEUE;
 385         fp->f_ops = &kqueueops;
 386
 387         kq = kmalloc(sizeof(struct kqueue), M_KQUEUE, M_WAITOK | M_ZERO);
 388         TAILQ_INIT(&kq->kq_head);
 389         kq->kq_fdp = fdp;
 390         fp->f_data = kq;
 391
 392         fsetfd(p, fp, fd);
 393         uap->sysmsg_result = fd;
 394         fdrop(fp);
 395         return (error);
 396 }
 397
 398 int
 399 sys_kevent(struct kevent_args *uap)
 400 {
 401         struct thread *td = curthread;
 402         struct proc *p = td->td_proc;
 403         struct kevent *kevp;
 404         struct kqueue *kq;
 405         struct file *fp = NULL;
 406         struct timespec ts;
 407         int i, n, nerrors, error;
 408
 409         KKASSERT(p);
 410
 411         fp = holdfp(p->p_fd, uap->fd, -1);
 412         if (fp == NULL)
 413                 return (EBADF);
 414         if (fp->f_type != DTYPE_KQUEUE) {
 415                 fdrop(fp);
 416                 return (EBADF);
 417         }
 418
 419         if (uap->timeout != NULL) {
 420                 error = copyin(uap->timeout, &ts, sizeof(ts));
 421                 if (error)
 422                         goto done;
 423                 uap->timeout = &ts;
 424         }
 425
 426         kq = (struct kqueue *)fp->f_data;
 427         nerrors = 0;
 428
 429         while (uap->nchanges > 0) {
 430                 n = uap->nchanges > KQ_NEVENTS ? KQ_NEVENTS : uap->nchanges;
 431                 error = copyin(uap->changelist, kq->kq_kev,
 432                     n * sizeof(struct kevent));
 433                 if (error)
 434                         goto done;
 435                 for (i = 0; i < n; i++) {
 436                         kevp = &kq->kq_kev[i];
 437                         kevp->flags &= ~EV_SYSFLAGS;
 438                         error = kqueue_register(kq, kevp, td);
 439                         if (error) {
 440                                 if (uap->nevents != 0) {
 441                                         kevp->flags = EV_ERROR;
 442                                         kevp->data = error;
 443                                         (void) copyout((caddr_t)kevp,
 444                                             (caddr_t)uap->eventlist,
 445                                             sizeof(*kevp));
 446                                         uap->eventlist++;
 447                                         uap->nevents--;
 448                                         nerrors++;
 449                                 } else {
 450                                         goto done;
 451                                 }
 452                         }
 453                 }
 454                 uap->nchanges -= n;
 455                 uap->changelist += n;
 456         }
 457         if (nerrors) {
 458                 uap->sysmsg_result = nerrors;
 459                 error = 0;
 460                 goto done;
 461         }
 462
 463         error = kqueue_scan(fp, uap->nevents, uap->eventlist, uap->timeout, td, &uap->sysmsg_result);
 464 done:
 465         if (fp != NULL)
 466                 fdrop(fp);
 467         return (error);
 468 }
 469
 470 int
 471 kqueue_register(struct kqueue *kq, struct kevent *kev, struct thread *td)
 472 {
 473         struct filedesc *fdp = kq->kq_fdp;
 474         struct filterops *fops;
 475         struct file *fp = NULL;
 476         struct knote *kn = NULL;
 477         int error = 0;
 478
 479         if (kev->filter < 0) {
 480                 if (kev->filter + EVFILT_SYSCOUNT < 0)
 481                         return (EINVAL);
 482                 fops = sysfilt_ops[~kev->filter];       /* to 0-base index */
 483         } else {
 484                 /*
 485                  * XXX
 486                  * filter attach routine is responsible for insuring that
 487                  * the identifier can be attached to it.
 488                  */
 489                 kprintf("unknown filter: %d\n", kev->filter);
 490                 return (EINVAL);
 491         }
 492
 493         if (fops->f_isfd) {
 494                 /* validate descriptor */
 495                 fp = holdfp(fdp, kev->ident, -1);
 496                 if (fp == NULL)
 497                         return (EBADF);
 498
 499                 if (kev->ident < fdp->fd_knlistsize) {
 500                         SLIST_FOREACH(kn, &fdp->fd_knlist[kev->ident], kn_link)
 501                                 if (kq == kn->kn_kq &&
 502                                     kev->filter == kn->kn_filter)
 503                                         break;
 504                 }
 505         } else {
 506                 if (fdp->fd_knhashmask != 0) {
 507                         struct klist *list;
 508
 509                         list = &fdp->fd_knhash[
 510                             KN_HASH((u_long)kev->ident, fdp->fd_knhashmask)];
 511                         SLIST_FOREACH(kn, list, kn_link)
 512                                 if (kev->ident == kn->kn_id &&
 513                                     kq == kn->kn_kq &&
 514                                     kev->filter == kn->kn_filter)
 515                                         break;
 516                 }
 517         }
 518
 519         if (kn == NULL && ((kev->flags & EV_ADD) == 0)) {
 520                 error = ENOENT;
 521                 goto done;
 522         }
 523
 524         /*
 525          * kn now contains the matching knote, or NULL if no match
 526          */
 527         if (kev->flags & EV_ADD) {
 528
 529                 if (kn == NULL) {
 530                         kn = knote_alloc();
 531                         if (kn == NULL) {
 532                                 error = ENOMEM;
 533                                 goto done;
 534                         }
 535                         kn->kn_fp = fp;
 536                         kn->kn_kq = kq;
 537                         kn->kn_fop = fops;
 538
 539                         /*
 540                          * apply reference count to knote structure, and
 541                          * do not release it at the end of this routine.
 542                          */
 543                         fp = NULL;
 544
 545                         kn->kn_sfflags = kev->fflags;
 546                         kn->kn_sdata = kev->data;
 547                         kev->fflags = 0;
 548                         kev->data = 0;
 549                         kn->kn_kevent = *kev;
 550
 551                         knote_attach(kn, fdp);
 552                         if ((error = fops->f_attach(kn)) != 0) {
 553                                 knote_drop(kn, td);
 554                                 goto done;
 555                         }
 556                 } else {
 557                         /*
 558                          * The user may change some filter values after the
 559                          * initial EV_ADD, but doing so will not reset any
 560                          * filter which have already been triggered.
 561                          */
 562                         kn->kn_sfflags = kev->fflags;
 563                         kn->kn_sdata = kev->data;
 564                         kn->kn_kevent.udata = kev->udata;
 565                 }
 566
 567                 crit_enter();
 568                 if (kn->kn_fop->f_event(kn, 0))
 569                         KNOTE_ACTIVATE(kn);
 570                 crit_exit();
 571         } else if (kev->flags & EV_DELETE) {
 572                 kn->kn_fop->f_detach(kn);
 573                 knote_drop(kn, td);
 574                 goto done;
 575         }
 576
 577         if ((kev->flags & EV_DISABLE) &&
 578             ((kn->kn_status & KN_DISABLED) == 0)) {
 579                 crit_enter();
 580                 kn->kn_status |= KN_DISABLED;
 581                 crit_exit();
 582         }
 583
 584         if ((kev->flags & EV_ENABLE) && (kn->kn_status & KN_DISABLED)) {
 585                 crit_enter();
 586                 kn->kn_status &= ~KN_DISABLED;
 587                 if ((kn->kn_status & KN_ACTIVE) &&
 588                     ((kn->kn_status & KN_QUEUED) == 0))
 589                         knote_enqueue(kn);
 590                 crit_exit();
 591         }
 592
 593 done:
 594         if (fp != NULL)
 595                 fdrop(fp);
 596         return (error);
 597 }
 598
 599 static int
 600 kqueue_scan(struct file *fp, int maxevents, struct kevent *ulistp,
 601         const struct timespec *tsp, struct thread *td, int *res)
 602 {
 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 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_high(&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_high(&ttv);
 642         }
 643
 644 start:
 645         kevp = kq->kq_kev;
 646         crit_enter();
 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, PCATCH, "kqread", timeout);
 653                 }
 654                 crit_exit();
 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                         crit_exit();
 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                         crit_exit();
 693                         kn->kn_fop->f_detach(kn);
 694                         knote_drop(kn, td);
 695                         crit_enter();
 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                         crit_exit();
 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                         crit_enter();
 713                         if (error)
 714                                 break;
 715                 }
 716         }
 717         TAILQ_REMOVE(&kq->kq_head, &marker, kn_tqe);
 718         crit_exit();
 719 done:
 720         if (nkev != 0)
 721                 error = copyout((caddr_t)&kq->kq_kev, (caddr_t)ulistp,
 722                     sizeof(struct kevent) * nkev);
 723         *res = maxevents - count;
 724         return (error);
 725 }
 726
 727 /*
 728  * XXX
 729  * This could be expanded to call kqueue_scan, if desired.
 730  *
 731  * MPSAFE
 732  */
 733 static int
 734 kqueue_read(struct file *fp, struct uio *uio, struct ucred *cred, int flags)
 735 {
 736         return (ENXIO);
 737 }
 738
 739 /*
 740  * MPSAFE
 741  */
 742 static int
 743 kqueue_write(struct file *fp, struct uio *uio, struct ucred *cred, int flags)
 744 {
 745         return (ENXIO);
 746 }
 747
 748 /*
 749  * MPSAFE
 750  */
 751 static int
 752 kqueue_ioctl(struct file *fp, u_long com, caddr_t data, struct ucred *cred)
 753 {
 754         return (ENOTTY);
 755 }
 756
 757 /*
 758  * MPALMOSTSAFE - acquires mplock
 759  */
 760 static int
 761 kqueue_poll(struct file *fp, int events, struct ucred *cred)
 762 {
 763         struct kqueue *kq = (struct kqueue *)fp->f_data;
 764         int revents = 0;
 765
 766         get_mplock();
 767         crit_enter();
 768         if (events & (POLLIN | POLLRDNORM)) {
 769                 if (kq->kq_count) {
 770                         revents |= events & (POLLIN | POLLRDNORM);
 771                 } else {
 772                         selrecord(curthread, &kq->kq_sel);
 773                         kq->kq_state |= KQ_SEL;
 774                 }
 775         }
 776         crit_exit();
 777         rel_mplock();
 778         return (revents);
 779 }
 780
 781 /*
 782  * MPSAFE
 783  */
 784 static int
 785 kqueue_stat(struct file *fp, struct stat *st, struct ucred *cred)
 786 {
 787         struct kqueue *kq = (struct kqueue *)fp->f_data;
 788
 789         bzero((void *)st, sizeof(*st));
 790         st->st_size = kq->kq_count;
 791         st->st_blksize = sizeof(struct kevent);
 792         st->st_mode = S_IFIFO;
 793         return (0);
 794 }
 795
 796 /*
 797  * MPALMOSTSAFE - acquires mplock
 798  */
 799 static int
 800 kqueue_close(struct file *fp)
 801 {
 802         struct thread *td = curthread;
 803         struct proc *p = td->td_proc;
 804         struct kqueue *kq = (struct kqueue *)fp->f_data;
 805         struct filedesc *fdp;
 806         struct knote **knp, *kn, *kn0;
 807         int i;
 808
 809         KKASSERT(p);
 810         get_mplock();
 811         fdp = p->p_fd;
 812         for (i = 0; i < fdp->fd_knlistsize; i++) {
 813                 knp = &SLIST_FIRST(&fdp->fd_knlist[i]);
 814                 kn = *knp;
 815                 while (kn != NULL) {
 816                         kn0 = SLIST_NEXT(kn, kn_link);
 817                         if (kq == kn->kn_kq) {
 818                                 kn->kn_fop->f_detach(kn);
 819                                 fdrop(kn->kn_fp);
 820                                 knote_free(kn);
 821                                 *knp = kn0;
 822                         } else {
 823                                 knp = &SLIST_NEXT(kn, kn_link);
 824                         }
 825                         kn = kn0;
 826                 }
 827         }
 828         if (fdp->fd_knhashmask != 0) {
 829                 for (i = 0; i < fdp->fd_knhashmask + 1; i++) {
 830                         knp = &SLIST_FIRST(&fdp->fd_knhash[i]);
 831                         kn = *knp;
 832                         while (kn != NULL) {
 833                                 kn0 = SLIST_NEXT(kn, kn_link);
 834                                 if (kq == kn->kn_kq) {
 835                                         kn->kn_fop->f_detach(kn);
 836                 /* XXX non-fd release of kn->kn_ptr */
 837                                         knote_free(kn);
 838                                         *knp = kn0;
 839                                 } else {
 840                                         knp = &SLIST_NEXT(kn, kn_link);
 841                                 }
 842                                 kn = kn0;
 843                         }
 844                 }
 845         }
 846         fp->f_data = NULL;
 847         rel_mplock();
 848
 849         kfree(kq, M_KQUEUE);
 850         return (0);
 851 }
 852
 853 static void
 854 kqueue_wakeup(struct kqueue *kq)
 855 {
 856         if (kq->kq_state & KQ_SLEEP) {
 857                 kq->kq_state &= ~KQ_SLEEP;
 858                 wakeup(kq);
 859         }
 860         if (kq->kq_state & KQ_SEL) {
 861                 kq->kq_state &= ~KQ_SEL;
 862                 selwakeup(&kq->kq_sel);
 863         }
 864         KNOTE(&kq->kq_sel.si_note, 0);
 865 }
 866
 867 /*
 868  * walk down a list of knotes, activating them if their event has triggered.
 869  */
 870 void
 871 knote(struct klist *list, long hint)
 872 {
 873         struct knote *kn;
 874
 875         SLIST_FOREACH(kn, list, kn_selnext)
 876                 if (kn->kn_fop->f_event(kn, hint))
 877                         KNOTE_ACTIVATE(kn);
 878 }
 879
 880 /*
 881  * remove all knotes from a specified klist
 882  */
 883 void
 884 knote_remove(struct thread *td, struct klist *list)
 885 {
 886         struct knote *kn;
 887
 888         while ((kn = SLIST_FIRST(list)) != NULL) {
 889                 kn->kn_fop->f_detach(kn);
 890                 knote_drop(kn, td);
 891         }
 892 }
 893
 894 /*
 895  * remove all knotes referencing a specified fd
 896  */
 897 void
 898 knote_fdclose(struct proc *p, int fd)
 899 {
 900         struct filedesc *fdp = p->p_fd;
 901         struct klist *list = &fdp->fd_knlist[fd];
 902         /* Take any thread of p */
 903         struct thread *td = LIST_FIRST(&p->p_lwps)->lwp_thread;
 904
 905         knote_remove(td, list);
 906 }
 907
 908 static void
 909 knote_attach(struct knote *kn, struct filedesc *fdp)
 910 {
 911         struct klist *list;
 912         int size;
 913
 914         if (! kn->kn_fop->f_isfd) {
 915                 if (fdp->fd_knhashmask == 0)
 916                         fdp->fd_knhash = hashinit(KN_HASHSIZE, M_KQUEUE,
 917                             &fdp->fd_knhashmask);
 918                 list = &fdp->fd_knhash[KN_HASH(kn->kn_id, fdp->fd_knhashmask)];
 919                 goto done;
 920         }
 921
 922         if (fdp->fd_knlistsize <= kn->kn_id) {
 923                 size = fdp->fd_knlistsize;
 924                 while (size <= kn->kn_id)
 925                         size += KQEXTENT;
 926                 MALLOC(list, struct klist *,
 927                     size * sizeof(struct klist *), M_KQUEUE, M_WAITOK);
 928                 bcopy((caddr_t)fdp->fd_knlist, (caddr_t)list,
 929                     fdp->fd_knlistsize * sizeof(struct klist *));
 930                 bzero((caddr_t)list +
 931                     fdp->fd_knlistsize * sizeof(struct klist *),
 932                     (size - fdp->fd_knlistsize) * sizeof(struct klist *));
 933                 if (fdp->fd_knlist != NULL)
 934                         FREE(fdp->fd_knlist, M_KQUEUE);
 935                 fdp->fd_knlistsize = size;
 936                 fdp->fd_knlist = list;
 937         }
 938         list = &fdp->fd_knlist[kn->kn_id];
 939 done:
 940         SLIST_INSERT_HEAD(list, kn, kn_link);
 941         kn->kn_status = 0;
 942 }
 943
 944 /*
 945  * should be called outside of a critical section, since we don't want to
 946  * hold a critical section while calling fdrop and free.
 947  */
 948 static void
 949 knote_drop(struct knote *kn, struct thread *td)
 950 {
 951         struct filedesc *fdp;
 952         struct klist *list;
 953
 954         KKASSERT(td->td_proc);
 955         fdp = td->td_proc->p_fd;
 956         if (kn->kn_fop->f_isfd)
 957                 list = &fdp->fd_knlist[kn->kn_id];
 958         else
 959                 list = &fdp->fd_knhash[KN_HASH(kn->kn_id, fdp->fd_knhashmask)];
 960
 961         SLIST_REMOVE(list, kn, knote, kn_link);
 962         if (kn->kn_status & KN_QUEUED)
 963                 knote_dequeue(kn);
 964         if (kn->kn_fop->f_isfd)
 965                 fdrop(kn->kn_fp);
 966         knote_free(kn);
 967 }
 968
 969
 970 static void
 971 knote_enqueue(struct knote *kn)
 972 {
 973         struct kqueue *kq = kn->kn_kq;
 974
 975         crit_enter();
 976         KASSERT((kn->kn_status & KN_QUEUED) == 0, ("knote already queued"));
 977
 978         TAILQ_INSERT_TAIL(&kq->kq_head, kn, kn_tqe);
 979         kn->kn_status |= KN_QUEUED;
 980         kq->kq_count++;
 981         crit_exit();
 982         kqueue_wakeup(kq);
 983 }
 984
 985 static void
 986 knote_dequeue(struct knote *kn)
 987 {
 988         struct kqueue *kq = kn->kn_kq;
 989
 990         KASSERT(kn->kn_status & KN_QUEUED, ("knote not queued"));
 991         crit_enter();
 992
 993         TAILQ_REMOVE(&kq->kq_head, kn, kn_tqe);
 994         kn->kn_status &= ~KN_QUEUED;
 995         kq->kq_count--;
 996         crit_exit();
 997 }
 998
 999 static void
1000 knote_init(void)
1001 {
1002         knote_zone = zinit("KNOTE", sizeof(struct knote), 0, 0, 1);
1003 }
1004 SYSINIT(knote, SI_SUB_PSEUDO, SI_ORDER_ANY, knote_init, NULL)
1005
1006 static struct knote *
1007 knote_alloc(void)
1008 {
1009         return ((struct knote *)zalloc(knote_zone));
1010 }
1011
1012 static void
1013 knote_free(struct knote *kn)
1014 {
1015         zfree(knote_zone, kn);
1016 }