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.33 2007/02/03 17:05:57 corecode 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/queue.h>
  40 #include <sys/event.h>
  41 #include <sys/eventvar.h>
  42 #include <sys/protosw.h>
  43 #include <sys/socket.h>
  44 #include <sys/socketvar.h>
  45 #include <sys/stat.h>
  46 #include <sys/sysctl.h>
  47 #include <sys/sysproto.h>
  48 #include <sys/thread.h>
  49 #include <sys/uio.h>
  50 #include <sys/signalvar.h>
  51 #include <sys/filio.h>
  52 #include <sys/ktr.h>
  53
  54 #include <sys/thread2.h>
  55 #include <sys/file2.h>
  56 #include <sys/mplock2.h>
  57
  58 #include <vm/vm_zone.h>
  59
  60 /*
  61  * Global token for kqueue subsystem
  62  */
  63 struct lwkt_token kq_token = LWKT_TOKEN_UP_INITIALIZER(kq_token);
  64
  65 MALLOC_DEFINE(M_KQUEUE, "kqueue", "memory for kqueue system");
  66
  67 struct kevent_copyin_args {
  68         struct kevent_args      *ka;
  69         int                     pchanges;
  70 };
  71
  72 static int      kqueue_sleep(struct kqueue *kq, struct timespec *tsp);
  73 static int      kqueue_scan(struct kqueue *kq, struct kevent *kevp, int count,
  74                     struct knote *marker);
  75 static int      kqueue_read(struct file *fp, struct uio *uio,
  76                     struct ucred *cred, int flags);
  77 static int      kqueue_write(struct file *fp, struct uio *uio,
  78                     struct ucred *cred, int flags);
  79 static int      kqueue_ioctl(struct file *fp, u_long com, caddr_t data,
  80                     struct ucred *cred, struct sysmsg *msg);
  81 static int      kqueue_kqfilter(struct file *fp, struct knote *kn);
  82 static int      kqueue_stat(struct file *fp, struct stat *st,
  83                     struct ucred *cred);
  84 static int      kqueue_close(struct file *fp);
  85 static void     kqueue_wakeup(struct kqueue *kq);
  86 static int      filter_attach(struct knote *kn);
  87 static int      filter_event(struct knote *kn, long hint);
  88
  89 /*
  90  * MPSAFE
  91  */
  92 static struct fileops kqueueops = {
  93         .fo_read = kqueue_read,
  94         .fo_write = kqueue_write,
  95         .fo_ioctl = kqueue_ioctl,
  96         .fo_kqfilter = kqueue_kqfilter,
  97         .fo_stat = kqueue_stat,
  98         .fo_close = kqueue_close,
  99         .fo_shutdown = nofo_shutdown
 100 };
 101
 102 static void     knote_attach(struct knote *kn);
 103 static void     knote_drop(struct knote *kn);
 104 static void     knote_detach_and_drop(struct knote *kn);
 105 static void     knote_detach_and_drop_locked(struct knote *kn);
 106 static void     knote_enqueue(struct knote *kn);
 107 static void     knote_dequeue(struct knote *kn);
 108 static void     knote_init(void);
 109 static struct   knote *knote_alloc(void);
 110 static void     knote_free(struct knote *kn);
 111
 112 static void     filt_kqdetach(struct knote *kn);
 113 static int      filt_kqueue(struct knote *kn, long hint);
 114 static int      filt_procattach(struct knote *kn);
 115 static void     filt_procdetach(struct knote *kn);
 116 static int      filt_proc(struct knote *kn, long hint);
 117 static int      filt_fileattach(struct knote *kn);
 118 static void     filt_timerexpire(void *knx);
 119 static int      filt_timerattach(struct knote *kn);
 120 static void     filt_timerdetach(struct knote *kn);
 121 static int      filt_timer(struct knote *kn, long hint);
 122
 123 static struct filterops file_filtops =
 124         { FILTEROP_ISFD, filt_fileattach, NULL, NULL };
 125 static struct filterops kqread_filtops =
 126         { FILTEROP_ISFD, NULL, filt_kqdetach, filt_kqueue };
 127 static struct filterops proc_filtops =
 128         { 0, filt_procattach, filt_procdetach, filt_proc };
 129 static struct filterops timer_filtops =
 130         { 0, filt_timerattach, filt_timerdetach, filt_timer };
 131
 132 static vm_zone_t        knote_zone;
 133 static int              kq_ncallouts = 0;
 134 static int              kq_calloutmax = (4 * 1024);
 135 SYSCTL_INT(_kern, OID_AUTO, kq_calloutmax, CTLFLAG_RW,
 136     &kq_calloutmax, 0, "Maximum number of callouts allocated for kqueue");
 137 static int              kq_checkloop = 1000000;
 138 SYSCTL_INT(_kern, OID_AUTO, kq_checkloop, CTLFLAG_RW,
 139     &kq_checkloop, 0, "Maximum number of callouts allocated for kqueue");
 140
 141 #define KNOTE_ACTIVATE(kn) do {                                         \
 142         kn->kn_status |= KN_ACTIVE;                                     \
 143         if ((kn->kn_status & (KN_QUEUED | KN_DISABLED)) == 0)           \
 144                 knote_enqueue(kn);                                      \
 145 } while(0)
 146
 147 #define KN_HASHSIZE             64              /* XXX should be tunable */
 148 #define KN_HASH(val, mask)      (((val) ^ (val >> 8)) & (mask))
 149
 150 extern struct filterops aio_filtops;
 151 extern struct filterops sig_filtops;
 152
 153 /*
 154  * Table for for all system-defined filters.
 155  */
 156 static struct filterops *sysfilt_ops[] = {
 157         &file_filtops,                  /* EVFILT_READ */
 158         &file_filtops,                  /* EVFILT_WRITE */
 159         &aio_filtops,                   /* EVFILT_AIO */
 160         &file_filtops,                  /* EVFILT_VNODE */
 161         &proc_filtops,                  /* EVFILT_PROC */
 162         &sig_filtops,                   /* EVFILT_SIGNAL */
 163         &timer_filtops,                 /* EVFILT_TIMER */
 164         &file_filtops,                  /* EVFILT_EXCEPT */
 165 };
 166
 167 static int
 168 filt_fileattach(struct knote *kn)
 169 {
 170         return (fo_kqfilter(kn->kn_fp, kn));
 171 }
 172
 173 /*
 174  * MPSAFE
 175  */
 176 static int
 177 kqueue_kqfilter(struct file *fp, struct knote *kn)
 178 {
 179         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 180
 181         if (kn->kn_filter != EVFILT_READ)
 182                 return (EOPNOTSUPP);
 183
 184         kn->kn_fop = &kqread_filtops;
 185         knote_insert(&kq->kq_kqinfo.ki_note, kn);
 186         return (0);
 187 }
 188
 189 static void
 190 filt_kqdetach(struct knote *kn)
 191 {
 192         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 193
 194         knote_remove(&kq->kq_kqinfo.ki_note, kn);
 195 }
 196
 197 /*ARGSUSED*/
 198 static int
 199 filt_kqueue(struct knote *kn, long hint)
 200 {
 201         struct kqueue *kq = (struct kqueue *)kn->kn_fp->f_data;
 202
 203         kn->kn_data = kq->kq_count;
 204         return (kn->kn_data > 0);
 205 }
 206
 207 static int
 208 filt_procattach(struct knote *kn)
 209 {
 210         struct proc *p;
 211         int immediate;
 212
 213         immediate = 0;
 214         lwkt_gettoken(&proc_token);
 215         p = pfind(kn->kn_id);
 216         if (p == NULL && (kn->kn_sfflags & NOTE_EXIT)) {
 217                 p = zpfind(kn->kn_id);
 218                 immediate = 1;
 219         }
 220         if (p == NULL) {
 221                 lwkt_reltoken(&proc_token);
 222                 return (ESRCH);
 223         }
 224         if (!PRISON_CHECK(curthread->td_ucred, p->p_ucred)) {
 225                 lwkt_reltoken(&proc_token);
 226                 return (EACCES);
 227         }
 228
 229         kn->kn_ptr.p_proc = p;
 230         kn->kn_flags |= EV_CLEAR;               /* automatically set */
 231
 232         /*
 233          * internal flag indicating registration done by kernel
 234          */
 235         if (kn->kn_flags & EV_FLAG1) {
 236                 kn->kn_data = kn->kn_sdata;             /* ppid */
 237                 kn->kn_fflags = NOTE_CHILD;
 238                 kn->kn_flags &= ~EV_FLAG1;
 239         }
 240
 241         knote_insert(&p->p_klist, kn);
 242
 243         /*
 244          * Immediately activate any exit notes if the target process is a
 245          * zombie.  This is necessary to handle the case where the target
 246          * process, e.g. a child, dies before the kevent is negistered.
 247          */
 248         if (immediate && filt_proc(kn, NOTE_EXIT))
 249                 KNOTE_ACTIVATE(kn);
 250         lwkt_reltoken(&proc_token);
 251
 252         return (0);
 253 }
 254
 255 /*
 256  * The knote may be attached to a different process, which may exit,
 257  * leaving nothing for the knote to be attached to.  So when the process
 258  * exits, the knote is marked as DETACHED and also flagged as ONESHOT so
 259  * it will be deleted when read out.  However, as part of the knote deletion,
 260  * this routine is called, so a check is needed to avoid actually performing
 261  * a detach, because the original process does not exist any more.
 262  */
 263 static void
 264 filt_procdetach(struct knote *kn)
 265 {
 266         struct proc *p;
 267
 268         if (kn->kn_status & KN_DETACHED)
 269                 return;
 270         /* XXX locking? take proc_token here? */
 271         p = kn->kn_ptr.p_proc;
 272         knote_remove(&p->p_klist, kn);
 273 }
 274
 275 static int
 276 filt_proc(struct knote *kn, long hint)
 277 {
 278         u_int event;
 279
 280         /*
 281          * mask off extra data
 282          */
 283         event = (u_int)hint & NOTE_PCTRLMASK;
 284
 285         /*
 286          * if the user is interested in this event, record it.
 287          */
 288         if (kn->kn_sfflags & event)
 289                 kn->kn_fflags |= event;
 290
 291         /*
 292          * Process is gone, so flag the event as finished.  Detach the
 293          * knote from the process now because the process will be poof,
 294          * gone later on.
 295          */
 296         if (event == NOTE_EXIT) {
 297                 struct proc *p = kn->kn_ptr.p_proc;
 298                 if ((kn->kn_status & KN_DETACHED) == 0) {
 299                         knote_remove(&p->p_klist, kn);
 300                         kn->kn_status |= KN_DETACHED;
 301                         kn->kn_data = p->p_xstat;
 302                         kn->kn_ptr.p_proc = NULL;
 303                 }
 304                 kn->kn_flags |= (EV_EOF | EV_ONESHOT);
 305                 return (1);
 306         }
 307
 308         /*
 309          * process forked, and user wants to track the new process,
 310          * so attach a new knote to it, and immediately report an
 311          * event with the parent's pid.
 312          */
 313         if ((event == NOTE_FORK) && (kn->kn_sfflags & NOTE_TRACK)) {
 314                 struct kevent kev;
 315                 int error;
 316
 317                 /*
 318                  * register knote with new process.
 319                  */
 320                 kev.ident = hint & NOTE_PDATAMASK;      /* pid */
 321                 kev.filter = kn->kn_filter;
 322                 kev.flags = kn->kn_flags | EV_ADD | EV_ENABLE | EV_FLAG1;
 323                 kev.fflags = kn->kn_sfflags;
 324                 kev.data = kn->kn_id;                   /* parent */
 325                 kev.udata = kn->kn_kevent.udata;        /* preserve udata */
 326                 error = kqueue_register(kn->kn_kq, &kev);
 327                 if (error)
 328                         kn->kn_fflags |= NOTE_TRACKERR;
 329         }
 330
 331         return (kn->kn_fflags != 0);
 332 }
 333
 334 static void
 335 filt_timerexpire(void *knx)
 336 {
 337         struct knote *kn = knx;
 338         struct callout *calloutp;
 339         struct timeval tv;
 340         int tticks;
 341
 342         lwkt_gettoken(&kq_token);
 343
 344         kn->kn_data++;
 345         KNOTE_ACTIVATE(kn);
 346
 347         if ((kn->kn_flags & EV_ONESHOT) == 0) {
 348                 tv.tv_sec = kn->kn_sdata / 1000;
 349                 tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
 350                 tticks = tvtohz_high(&tv);
 351                 calloutp = (struct callout *)kn->kn_hook;
 352                 callout_reset(calloutp, tticks, filt_timerexpire, kn);
 353         }
 354
 355         lwkt_reltoken(&kq_token);
 356 }
 357
 358 /*
 359  * data contains amount of time to sleep, in milliseconds
 360  */
 361 static int
 362 filt_timerattach(struct knote *kn)
 363 {
 364         struct callout *calloutp;
 365         struct timeval tv;
 366         int tticks;
 367
 368         if (kq_ncallouts >= kq_calloutmax)
 369                 return (ENOMEM);
 370         kq_ncallouts++;
 371
 372         tv.tv_sec = kn->kn_sdata / 1000;
 373         tv.tv_usec = (kn->kn_sdata % 1000) * 1000;
 374         tticks = tvtohz_high(&tv);
 375
 376         kn->kn_flags |= EV_CLEAR;               /* automatically set */
 377         MALLOC(calloutp, struct callout *, sizeof(*calloutp),
 378             M_KQUEUE, M_WAITOK);
 379         callout_init(calloutp);
 380         kn->kn_hook = (caddr_t)calloutp;
 381         callout_reset(calloutp, tticks, filt_timerexpire, kn);
 382
 383         return (0);
 384 }
 385
 386 static void
 387 filt_timerdetach(struct knote *kn)
 388 {
 389         struct callout *calloutp;
 390
 391         calloutp = (struct callout *)kn->kn_hook;
 392         callout_stop(calloutp);
 393         FREE(calloutp, M_KQUEUE);
 394         kq_ncallouts--;
 395 }
 396
 397 static int
 398 filt_timer(struct knote *kn, long hint)
 399 {
 400
 401         return (kn->kn_data != 0);
 402 }
 403
 404 /*
 405  * Initialize a kqueue.
 406  *
 407  * NOTE: The lwp/proc code initializes a kqueue for select/poll ops.
 408  *
 409  * MPSAFE
 410  */
 411 void
 412 kqueue_init(struct kqueue *kq, struct filedesc *fdp)
 413 {
 414         TAILQ_INIT(&kq->kq_knpend);
 415         TAILQ_INIT(&kq->kq_knlist);
 416         kq->kq_count = 0;
 417         kq->kq_fdp = fdp;
 418         SLIST_INIT(&kq->kq_kqinfo.ki_note);
 419 }
 420
 421 /*
 422  * Terminate a kqueue.  Freeing the actual kq itself is left up to the
 423  * caller (it might be embedded in a lwp so we don't do it here).
 424  *
 425  * The kq's knlist must be completely eradicated so block on any
 426  * processing races.
 427  */
 428 void
 429 kqueue_terminate(struct kqueue *kq)
 430 {
 431         struct knote *kn;
 432
 433         lwkt_gettoken(&kq_token);
 434         while ((kn = TAILQ_FIRST(&kq->kq_knlist)) != NULL) {
 435                 if (kn->kn_status & KN_PROCESSING) {
 436                         kn->kn_status |= KN_WAITING | KN_REPROCESS;
 437                         tsleep(kn, 0, "kqtrms", hz);
 438                         continue;
 439                 }
 440                 knote_detach_and_drop(kn);
 441         }
 442         if (kq->kq_knhash) {
 443                 kfree(kq->kq_knhash, M_KQUEUE);
 444                 kq->kq_knhash = NULL;
 445                 kq->kq_knhashmask = 0;
 446         }
 447         lwkt_reltoken(&kq_token);
 448 }
 449
 450 /*
 451  * MPSAFE
 452  */
 453 int
 454 sys_kqueue(struct kqueue_args *uap)
 455 {
 456         struct thread *td = curthread;
 457         struct kqueue *kq;
 458         struct file *fp;
 459         int fd, error;
 460
 461         error = falloc(td->td_lwp, &fp, &fd);
 462         if (error)
 463                 return (error);
 464         fp->f_flag = FREAD | FWRITE;
 465         fp->f_type = DTYPE_KQUEUE;
 466         fp->f_ops = &kqueueops;
 467
 468         kq = kmalloc(sizeof(struct kqueue), M_KQUEUE, M_WAITOK | M_ZERO);
 469         kqueue_init(kq, td->td_proc->p_fd);
 470         fp->f_data = kq;
 471
 472         fsetfd(kq->kq_fdp, fp, fd);
 473         uap->sysmsg_result = fd;
 474         fdrop(fp);
 475         return (error);
 476 }
 477
 478 /*
 479  * Copy 'count' items into the destination list pointed to by uap->eventlist.
 480  */
 481 static int
 482 kevent_copyout(void *arg, struct kevent *kevp, int count, int *res)
 483 {
 484         struct kevent_copyin_args *kap;
 485         int error;
 486
 487         kap = (struct kevent_copyin_args *)arg;
 488
 489         error = copyout(kevp, kap->ka->eventlist, count * sizeof(*kevp));
 490         if (error == 0) {
 491                 kap->ka->eventlist += count;
 492                 *res += count;
 493         } else {
 494                 *res = -1;
 495         }
 496
 497         return (error);
 498 }
 499
 500 /*
 501  * Copy at most 'max' items from the list pointed to by kap->changelist,
 502  * return number of items in 'events'.
 503  */
 504 static int
 505 kevent_copyin(void *arg, struct kevent *kevp, int max, int *events)
 506 {
 507         struct kevent_copyin_args *kap;
 508         int error, count;
 509
 510         kap = (struct kevent_copyin_args *)arg;
 511
 512         count = min(kap->ka->nchanges - kap->pchanges, max);
 513         error = copyin(kap->ka->changelist, kevp, count * sizeof *kevp);
 514         if (error == 0) {
 515                 kap->ka->changelist += count;
 516                 kap->pchanges += count;
 517                 *events = count;
 518         }
 519
 520         return (error);
 521 }
 522
 523 /*
 524  * MPSAFE
 525  */
 526 int
 527 kern_kevent(struct kqueue *kq, int nevents, int *res, void *uap,
 528             k_copyin_fn kevent_copyinfn, k_copyout_fn kevent_copyoutfn,
 529             struct timespec *tsp_in)
 530 {
 531         struct kevent *kevp;
 532         struct timespec *tsp;
 533         int i, n, total, error, nerrors = 0;
 534         int lres;
 535         int limit = kq_checkloop;
 536         struct kevent kev[KQ_NEVENTS];
 537         struct knote marker;
 538
 539         tsp = tsp_in;
 540         *res = 0;
 541
 542         lwkt_gettoken(&kq_token);
 543         for ( ;; ) {
 544                 n = 0;
 545                 error = kevent_copyinfn(uap, kev, KQ_NEVENTS, &n);
 546                 if (error)
 547                         goto done;
 548                 if (n == 0)
 549                         break;
 550                 for (i = 0; i < n; i++) {
 551                         kevp = &kev[i];
 552                         kevp->flags &= ~EV_SYSFLAGS;
 553                         error = kqueue_register(kq, kevp);
 554
 555                         /*
 556                          * If a registration returns an error we
 557                          * immediately post the error.  The kevent()
 558                          * call itself will fail with the error if
 559                          * no space is available for posting.
 560                          *
 561                          * Such errors normally bypass the timeout/blocking
 562                          * code.  However, if the copyoutfn function refuses
 563                          * to post the error (see sys_poll()), then we
 564                          * ignore it too.
 565                          */
 566                         if (error) {
 567                                 kevp->flags = EV_ERROR;
 568                                 kevp->data = error;
 569                                 lres = *res;
 570                                 kevent_copyoutfn(uap, kevp, 1, res);
 571                                 if (lres != *res) {
 572                                         nevents--;
 573                                         nerrors++;
 574                                 }
 575                         }
 576                 }
 577         }
 578         if (nerrors) {
 579                 error = 0;
 580                 goto done;
 581         }
 582
 583         /*
 584          * Acquire/wait for events - setup timeout
 585          */
 586         if (tsp != NULL) {
 587                 struct timespec ats;
 588
 589                 if (tsp->tv_sec || tsp->tv_nsec) {
 590                         nanouptime(&ats);
 591                         timespecadd(tsp, &ats);         /* tsp = target time */
 592                 }
 593         }
 594
 595         /*
 596          * Loop as required.
 597          *
 598          * Collect as many events as we can. Sleeping on successive
 599          * loops is disabled if copyoutfn has incremented (*res).
 600          *
 601          * The loop stops if an error occurs, all events have been
 602          * scanned (the marker has been reached), or fewer than the
 603          * maximum number of events is found.
 604          *
 605          * The copyoutfn function does not have to increment (*res) in
 606          * order for the loop to continue.
 607          *
 608          * NOTE: doselect() usually passes 0x7FFFFFFF for nevents.
 609          */
 610         total = 0;
 611         error = 0;
 612         marker.kn_filter = EVFILT_MARKER;
 613         marker.kn_status = KN_PROCESSING;
 614         TAILQ_INSERT_TAIL(&kq->kq_knpend, &marker, kn_tqe);
 615         while ((n = nevents - total) > 0) {
 616                 if (n > KQ_NEVENTS)
 617                         n = KQ_NEVENTS;
 618
 619                 /*
 620                  * If no events are pending sleep until timeout (if any)
 621                  * or an event occurs.
 622                  *
 623                  * After the sleep completes the marker is moved to the
 624                  * end of the list, making any received events available
 625                  * to our scan.
 626                  */
 627                 if (kq->kq_count == 0 && *res == 0) {
 628                         error = kqueue_sleep(kq, tsp);
 629                         if (error)
 630                                 break;
 631
 632                         TAILQ_REMOVE(&kq->kq_knpend, &marker, kn_tqe);
 633                         TAILQ_INSERT_TAIL(&kq->kq_knpend, &marker, kn_tqe);
 634                 }
 635
 636                 /*
 637                  * Process all received events
 638                  * Account for all non-spurious events in our total
 639                  */
 640                 i = kqueue_scan(kq, kev, n, &marker);
 641                 if (i) {
 642                         lres = *res;
 643                         error = kevent_copyoutfn(uap, kev, i, res);
 644                         total += *res - lres;
 645                         if (error)
 646                                 break;
 647                 }
 648                 if (limit && --limit == 0)
 649                         panic("kqueue: checkloop failed i=%d", i);
 650
 651                 /*
 652                  * Normally when fewer events are returned than requested
 653                  * we can stop.  However, if only spurious events were
 654                  * collected the copyout will not bump (*res) and we have
 655                  * to continue.
 656                  */
 657                 if (i < n && *res)
 658                         break;
 659
 660                 /*
 661                  * Deal with an edge case where spurious events can cause
 662                  * a loop to occur without moving the marker.  This can
 663                  * prevent kqueue_scan() from picking up new events which
 664                  * race us.  We must be sure to move the marker for this
 665                  * case.
 666                  *
 667                  * NOTE: We do not want to move the marker if events
 668                  *       were scanned because normal kqueue operations
 669                  *       may reactivate events.  Moving the marker in
 670                  *       that case could result in duplicates for the
 671                  *       same event.
 672                  */
 673                 if (i == 0) {
 674                         TAILQ_REMOVE(&kq->kq_knpend, &marker, kn_tqe);
 675                         TAILQ_INSERT_TAIL(&kq->kq_knpend, &marker, kn_tqe);
 676                 }
 677         }
 678         TAILQ_REMOVE(&kq->kq_knpend, &marker, kn_tqe);
 679
 680         /* Timeouts do not return EWOULDBLOCK. */
 681         if (error == EWOULDBLOCK)
 682                 error = 0;
 683
 684 done:
 685         lwkt_reltoken(&kq_token);
 686         return (error);
 687 }
 688
 689 /*
 690  * MPALMOSTSAFE
 691  */
 692 int
 693 sys_kevent(struct kevent_args *uap)
 694 {
 695         struct thread *td = curthread;
 696         struct proc *p = td->td_proc;
 697         struct timespec ts, *tsp;
 698         struct kqueue *kq;
 699         struct file *fp = NULL;
 700         struct kevent_copyin_args *kap, ka;
 701         int error;
 702
 703         if (uap->timeout) {
 704                 error = copyin(uap->timeout, &ts, sizeof(ts));
 705                 if (error)
 706                         return (error);
 707                 tsp = &ts;
 708         } else {
 709                 tsp = NULL;
 710         }
 711
 712         fp = holdfp(p->p_fd, uap->fd, -1);
 713         if (fp == NULL)
 714                 return (EBADF);
 715         if (fp->f_type != DTYPE_KQUEUE) {
 716                 fdrop(fp);
 717                 return (EBADF);
 718         }
 719
 720         kq = (struct kqueue *)fp->f_data;
 721
 722         kap = &ka;
 723         kap->ka = uap;
 724         kap->pchanges = 0;
 725
 726         error = kern_kevent(kq, uap->nevents, &uap->sysmsg_result, kap,
 727                             kevent_copyin, kevent_copyout, tsp);
 728
 729         fdrop(fp);
 730
 731         return (error);
 732 }
 733
 734 int
 735 kqueue_register(struct kqueue *kq, struct kevent *kev)
 736 {
 737         struct filedesc *fdp = kq->kq_fdp;
 738         struct filterops *fops;
 739         struct file *fp = NULL;
 740         struct knote *kn = NULL;
 741         int error = 0;
 742
 743         if (kev->filter < 0) {
 744                 if (kev->filter + EVFILT_SYSCOUNT < 0)
 745                         return (EINVAL);
 746                 fops = sysfilt_ops[~kev->filter];       /* to 0-base index */
 747         } else {
 748                 /*
 749                  * XXX
 750                  * filter attach routine is responsible for insuring that
 751                  * the identifier can be attached to it.
 752                  */
 753                 kprintf("unknown filter: %d\n", kev->filter);
 754                 return (EINVAL);
 755         }
 756
 757         lwkt_gettoken(&kq_token);
 758         if (fops->f_flags & FILTEROP_ISFD) {
 759                 /* validate descriptor */
 760                 fp = holdfp(fdp, kev->ident, -1);
 761                 if (fp == NULL) {
 762                         lwkt_reltoken(&kq_token);
 763                         return (EBADF);
 764                 }
 765
 766                 SLIST_FOREACH(kn, &fp->f_klist, kn_link) {
 767                         if (kn->kn_kq == kq &&
 768                             kn->kn_filter == kev->filter &&
 769                             kn->kn_id == kev->ident) {
 770                                 break;
 771                         }
 772                 }
 773         } else {
 774                 if (kq->kq_knhashmask) {
 775                         struct klist *list;
 776
 777                         list = &kq->kq_knhash[
 778                             KN_HASH((u_long)kev->ident, kq->kq_knhashmask)];
 779                         SLIST_FOREACH(kn, list, kn_link) {
 780                                 if (kn->kn_id == kev->ident &&
 781                                     kn->kn_filter == kev->filter)
 782                                         break;
 783                         }
 784                 }
 785         }
 786
 787         if (kn == NULL && ((kev->flags & EV_ADD) == 0)) {
 788                 error = ENOENT;
 789                 goto done;
 790         }
 791
 792         /*
 793          * kn now contains the matching knote, or NULL if no match
 794          */
 795         if (kev->flags & EV_ADD) {
 796                 if (kn == NULL) {
 797                         kn = knote_alloc();
 798                         if (kn == NULL) {
 799                                 error = ENOMEM;
 800                                 goto done;
 801                         }
 802                         kn->kn_fp = fp;
 803                         kn->kn_kq = kq;
 804                         kn->kn_fop = fops;
 805
 806                         /*
 807                          * apply reference count to knote structure, and
 808                          * do not release it at the end of this routine.
 809                          */
 810                         fp = NULL;
 811
 812                         kn->kn_sfflags = kev->fflags;
 813                         kn->kn_sdata = kev->data;
 814                         kev->fflags = 0;
 815                         kev->data = 0;
 816                         kn->kn_kevent = *kev;
 817
 818                         /*
 819                          * KN_PROCESSING prevents the knote from getting
 820                          * ripped out from under us while we are trying
 821                          * to attach it, in case the attach blocks.
 822                          */
 823                         kn->kn_status = KN_PROCESSING;
 824                         knote_attach(kn);
 825                         if ((error = filter_attach(kn)) != 0) {
 826                                 kn->kn_status |= KN_DELETING;
 827                                 knote_drop(kn);
 828                                 goto done;
 829                         }
 830
 831                         /*
 832                          * Interlock against close races which either tried
 833                          * to remove our knote while we were blocked or missed
 834                          * it entirely prior to our attachment.  We do not
 835                          * want to end up with a knote on a closed descriptor.
 836                          */
 837                         if ((fops->f_flags & FILTEROP_ISFD) &&
 838                             checkfdclosed(fdp, kev->ident, kn->kn_fp)) {
 839                                 kn->kn_status |= KN_DELETING;
 840                         }
 841                 } else {
 842                         /*
 843                          * The user may change some filter values after the
 844                          * initial EV_ADD, but doing so will not reset any
 845                          * filter which have already been triggered.
 846                          */
 847                         kn->kn_status |= KN_PROCESSING;
 848                         kn->kn_sfflags = kev->fflags;
 849                         kn->kn_sdata = kev->data;
 850                         kn->kn_kevent.udata = kev->udata;
 851                 }
 852
 853                 /*
 854                  * Execute the filter event to immediately activate the
 855                  * knote if necessary.  We still own KN_PROCESSING so
 856                  * process any KN_REPROCESS races as well.
 857                  */
 858                 for (;;) {
 859                         if (kn->kn_status & KN_DELETING) {
 860                                 error = EBADF;
 861                                 knote_detach_and_drop_locked(kn);
 862                                 goto done;
 863                         }
 864                         if (filter_event(kn, 0))
 865                                 KNOTE_ACTIVATE(kn);
 866                         if ((kn->kn_status & KN_REPROCESS) == 0)
 867                                 break;
 868                         if (kn->kn_status & KN_WAITING) {
 869                                 kn->kn_status &= ~KN_WAITING;
 870                                 wakeup(kn);
 871                         }
 872                         kn->kn_status &= ~KN_REPROCESS;
 873                 }
 874                 kn->kn_status &= ~KN_PROCESSING;
 875         } else if (kev->flags & EV_DELETE) {
 876                 /*
 877                  * Attempt to delete the existing knote
 878                  */
 879                 knote_detach_and_drop(kn);
 880                 goto done;
 881         }
 882
 883         /*
 884          * Disablement does not deactivate a knote here.
 885          */
 886         if ((kev->flags & EV_DISABLE) &&
 887             ((kn->kn_status & KN_DISABLED) == 0)) {
 888                 kn->kn_status |= KN_DISABLED;
 889         }
 890
 891         /*
 892          * Re-enablement may have to immediately enqueue an active knote.
 893          */
 894         if ((kev->flags & EV_ENABLE) && (kn->kn_status & KN_DISABLED)) {
 895                 kn->kn_status &= ~KN_DISABLED;
 896                 if ((kn->kn_status & KN_ACTIVE) &&
 897                     ((kn->kn_status & KN_QUEUED) == 0)) {
 898                         knote_enqueue(kn);
 899                 }
 900         }
 901
 902 done:
 903         lwkt_reltoken(&kq_token);
 904         if (fp != NULL)
 905                 fdrop(fp);
 906         return (error);
 907 }
 908
 909 /*
 910  * Block as necessary until the target time is reached.
 911  * If tsp is NULL we block indefinitely.  If tsp->ts_secs/nsecs are both
 912  * 0 we do not block at all.
 913  */
 914 static int
 915 kqueue_sleep(struct kqueue *kq, struct timespec *tsp)
 916 {
 917         int error = 0;
 918
 919         if (tsp == NULL) {
 920                 kq->kq_state |= KQ_SLEEP;
 921                 error = tsleep(kq, PCATCH, "kqread", 0);
 922         } else if (tsp->tv_sec == 0 && tsp->tv_nsec == 0) {
 923                 error = EWOULDBLOCK;
 924         } else {
 925                 struct timespec ats;
 926                 struct timespec atx = *tsp;
 927                 int timeout;
 928
 929                 nanouptime(&ats);
 930                 timespecsub(&atx, &ats);
 931                 if (ats.tv_sec < 0) {
 932                         error = EWOULDBLOCK;
 933                 } else {
 934                         timeout = atx.tv_sec > 24 * 60 * 60 ?
 935                                 24 * 60 * 60 * hz : tstohz_high(&atx);
 936                         kq->kq_state |= KQ_SLEEP;
 937                         error = tsleep(kq, PCATCH, "kqread", timeout);
 938                 }
 939         }
 940
 941         /* don't restart after signals... */
 942         if (error == ERESTART)
 943                 return (EINTR);
 944
 945         return (error);
 946 }
 947
 948 /*
 949  * Scan the kqueue, return the number of active events placed in kevp up
 950  * to count.
 951  *
 952  * Continuous mode events may get recycled, do not continue scanning past
 953  * marker unless no events have been collected.
 954  */
 955 static int
 956 kqueue_scan(struct kqueue *kq, struct kevent *kevp, int count,
 957             struct knote *marker)
 958 {
 959         struct knote *kn, local_marker;
 960         int total;
 961
 962         total = 0;
 963         local_marker.kn_filter = EVFILT_MARKER;
 964         local_marker.kn_status = KN_PROCESSING;
 965
 966         /*
 967          * Collect events.
 968          */
 969         TAILQ_INSERT_HEAD(&kq->kq_knpend, &local_marker, kn_tqe);
 970         while (count) {
 971                 kn = TAILQ_NEXT(&local_marker, kn_tqe);
 972                 if (kn->kn_filter == EVFILT_MARKER) {
 973                         /* Marker reached, we are done */
 974                         if (kn == marker)
 975                                 break;
 976
 977                         /* Move local marker past some other threads marker */
 978                         kn = TAILQ_NEXT(kn, kn_tqe);
 979                         TAILQ_REMOVE(&kq->kq_knpend, &local_marker, kn_tqe);
 980                         TAILQ_INSERT_BEFORE(kn, &local_marker, kn_tqe);
 981                         continue;
 982                 }
 983
 984                 /*
 985                  * We can't skip a knote undergoing processing, otherwise
 986                  * we risk not returning it when the user process expects
 987                  * it should be returned.  Sleep and retry.
 988                  */
 989                 if (kn->kn_status & KN_PROCESSING) {
 990                         kn->kn_status |= KN_WAITING | KN_REPROCESS;
 991                         tsleep(kn, 0, "kqepts", hz);
 992                         continue;
 993                 }
 994
 995                 /*
 996                  * Remove the event for processing.
 997                  *
 998                  * WARNING!  We must leave KN_QUEUED set to prevent the
 999                  *           event from being KNOTE_ACTIVATE()d while
1000                  *           the queue state is in limbo, in case we
1001                  *           block.
1002                  *
1003                  * WARNING!  We must set KN_PROCESSING to avoid races
1004                  *           against deletion or another thread's
1005                  *           processing.
1006                  */
1007                 TAILQ_REMOVE(&kq->kq_knpend, kn, kn_tqe);
1008                 kq->kq_count--;
1009                 kn->kn_status |= KN_PROCESSING;
1010
1011                 /*
1012                  * We have to deal with an extremely important race against
1013                  * file descriptor close()s here.  The file descriptor can
1014                  * disappear MPSAFE, and there is a small window of
1015                  * opportunity between that and the call to knote_fdclose().
1016                  *
1017                  * If we hit that window here while doselect or dopoll is
1018                  * trying to delete a spurious event they will not be able
1019                  * to match up the event against a knote and will go haywire.
1020                  */
1021                 if ((kn->kn_fop->f_flags & FILTEROP_ISFD) &&
1022                     checkfdclosed(kq->kq_fdp, kn->kn_kevent.ident, kn->kn_fp)) {
1023                         kn->kn_status |= KN_DELETING | KN_REPROCESS;
1024                 }
1025
1026                 if (kn->kn_status & KN_DISABLED) {
1027                         /*
1028                          * If disabled we ensure the event is not queued
1029                          * but leave its active bit set.  On re-enablement
1030                          * the event may be immediately triggered.
1031                          */
1032                         kn->kn_status &= ~KN_QUEUED;
1033                 } else if ((kn->kn_flags & EV_ONESHOT) == 0 &&
1034                            filter_event(kn, 0) == 0) {
1035                         /*
1036                          * If not running in one-shot mode and the event
1037                          * is no longer present we ensure it is removed
1038                          * from the queue and ignore it.
1039                          */
1040                         kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE);
1041                 } else {
1042                         /*
1043                          * Post the event
1044                          */
1045                         *kevp++ = kn->kn_kevent;
1046                         ++total;
1047                         --count;
1048
1049                         if (kn->kn_flags & EV_ONESHOT) {
1050                                 kn->kn_status &= ~KN_QUEUED;
1051                                 kn->kn_status |= KN_DELETING | KN_REPROCESS;
1052                         } else if (kn->kn_flags & EV_CLEAR) {
1053                                 kn->kn_data = 0;
1054                                 kn->kn_fflags = 0;
1055                                 kn->kn_status &= ~(KN_QUEUED | KN_ACTIVE);
1056                         } else {
1057                                 TAILQ_INSERT_TAIL(&kq->kq_knpend, kn, kn_tqe);
1058                                 kq->kq_count++;
1059                         }
1060                 }
1061
1062                 /*
1063                  * Handle any post-processing states
1064                  */
1065                 while (kn->kn_status & KN_REPROCESS) {
1066                         kn->kn_status &= ~KN_REPROCESS;
1067                         if (kn->kn_status & KN_DELETING) {
1068                                 knote_detach_and_drop_locked(kn);
1069                                 goto skip;
1070                         }
1071                         if (kn->kn_status & KN_WAITING) {
1072                                 kn->kn_status &= ~KN_WAITING;
1073                                 wakeup(kn);
1074                         }
1075                         if (filter_event(kn, 0))
1076                                 KNOTE_ACTIVATE(kn);
1077                 }
1078                 kn->kn_status &= ~KN_PROCESSING;
1079 skip:
1080                 ;
1081         }
1082         TAILQ_REMOVE(&kq->kq_knpend, &local_marker, kn_tqe);
1083
1084         return (total);
1085 }
1086
1087 /*
1088  * XXX
1089  * This could be expanded to call kqueue_scan, if desired.
1090  *
1091  * MPSAFE
1092  */
1093 static int
1094 kqueue_read(struct file *fp, struct uio *uio, struct ucred *cred, int flags)
1095 {
1096         return (ENXIO);
1097 }
1098
1099 /*
1100  * MPSAFE
1101  */
1102 static int
1103 kqueue_write(struct file *fp, struct uio *uio, struct ucred *cred, int flags)
1104 {
1105         return (ENXIO);
1106 }
1107
1108 /*
1109  * MPALMOSTSAFE
1110  */
1111 static int
1112 kqueue_ioctl(struct file *fp, u_long com, caddr_t data,
1113              struct ucred *cred, struct sysmsg *msg)
1114 {
1115         struct kqueue *kq;
1116         int error;
1117
1118         lwkt_gettoken(&kq_token);
1119         kq = (struct kqueue *)fp->f_data;
1120
1121         switch(com) {
1122         case FIOASYNC:
1123                 if (*(int *)data)
1124                         kq->kq_state |= KQ_ASYNC;
1125                 else
1126                         kq->kq_state &= ~KQ_ASYNC;
1127                 error = 0;
1128                 break;
1129         case FIOSETOWN:
1130                 error = fsetown(*(int *)data, &kq->kq_sigio);
1131                 break;
1132         default:
1133                 error = ENOTTY;
1134                 break;
1135         }
1136         lwkt_reltoken(&kq_token);
1137         return (error);
1138 }
1139
1140 /*
1141  * MPSAFE
1142  */
1143 static int
1144 kqueue_stat(struct file *fp, struct stat *st, struct ucred *cred)
1145 {
1146         struct kqueue *kq = (struct kqueue *)fp->f_data;
1147
1148         bzero((void *)st, sizeof(*st));
1149         st->st_size = kq->kq_count;
1150         st->st_blksize = sizeof(struct kevent);
1151         st->st_mode = S_IFIFO;
1152         return (0);
1153 }
1154
1155 /*
1156  * MPSAFE
1157  */
1158 static int
1159 kqueue_close(struct file *fp)
1160 {
1161         struct kqueue *kq = (struct kqueue *)fp->f_data;
1162
1163         kqueue_terminate(kq);
1164
1165         fp->f_data = NULL;
1166         funsetown(kq->kq_sigio);
1167
1168         kfree(kq, M_KQUEUE);
1169         return (0);
1170 }
1171
1172 static void
1173 kqueue_wakeup(struct kqueue *kq)
1174 {
1175         if (kq->kq_state & KQ_SLEEP) {
1176                 kq->kq_state &= ~KQ_SLEEP;
1177                 wakeup(kq);
1178         }
1179         KNOTE(&kq->kq_kqinfo.ki_note, 0);
1180 }
1181
1182 /*
1183  * Calls filterops f_attach function, acquiring mplock if filter is not
1184  * marked as FILTEROP_MPSAFE.
1185  */
1186 static int
1187 filter_attach(struct knote *kn)
1188 {
1189         int ret;
1190
1191         if (!(kn->kn_fop->f_flags & FILTEROP_MPSAFE)) {
1192                 get_mplock();
1193                 ret = kn->kn_fop->f_attach(kn);
1194                 rel_mplock();
1195         } else {
1196                 ret = kn->kn_fop->f_attach(kn);
1197         }
1198
1199         return (ret);
1200 }
1201
1202 /*
1203  * Detach the knote and drop it, destroying the knote.
1204  *
1205  * Calls filterops f_detach function, acquiring mplock if filter is not
1206  * marked as FILTEROP_MPSAFE.
1207  */
1208 static void
1209 knote_detach_and_drop(struct knote *kn)
1210 {
1211         /*
1212          * If someone else is procesing the knote we cannot destroy it now,
1213          * flag the request and return.
1214          */
1215         if (kn->kn_status & KN_PROCESSING) {
1216                 kn->kn_status |= KN_DELETING | KN_REPROCESS;
1217                 return;
1218         }
1219         kn->kn_status |= KN_PROCESSING | KN_DELETING;
1220         knote_detach_and_drop_locked(kn);
1221 }
1222
1223 static void
1224 knote_detach_and_drop_locked(struct knote *kn)
1225 {
1226         if (kn->kn_fop->f_flags & FILTEROP_MPSAFE) {
1227                 kn->kn_fop->f_detach(kn);
1228         } else {
1229                 get_mplock();
1230                 kn->kn_fop->f_detach(kn);
1231                 rel_mplock();
1232         }
1233         knote_drop(kn);
1234 }
1235
1236 /*
1237  * Calls filterops f_event function, acquiring mplock if filter is not
1238  * marked as FILTEROP_MPSAFE.
1239  *
1240  * If the knote is in the middle of being created or deleted we cannot
1241  * safely call the filter op.
1242  */
1243 static int
1244 filter_event(struct knote *kn, long hint)
1245 {
1246         int ret;
1247
1248         if (kn->kn_fop->f_flags & FILTEROP_MPSAFE) {
1249                 ret = kn->kn_fop->f_event(kn, hint);
1250         } else {
1251                 get_mplock();
1252                 ret = kn->kn_fop->f_event(kn, hint);
1253                 rel_mplock();
1254         }
1255         return (ret);
1256 }
1257
1258 /*
1259  * Walk down a list of knotes, activating them if their event has triggered.
1260  *
1261  * If we encounter any knotes which are undergoing processing we just mark
1262  * them for reprocessing and do not try to [re]activate the knote.  However,
1263  * if a hint is being passed we have to wait and that makes things a bit
1264  * sticky.
1265  */
1266 void
1267 knote(struct klist *list, long hint)
1268 {
1269         struct knote *kn;
1270
1271         lwkt_gettoken(&kq_token);
1272 restart:
1273         SLIST_FOREACH(kn, list, kn_next) {
1274                 if (kn->kn_status & KN_PROCESSING) {
1275                         /*
1276                          * Someone else is processing the knote, ask the
1277                          * other thread to reprocess it and don't mess
1278                          * with it otherwise.
1279                          */
1280                         if (hint == 0) {
1281                                 kn->kn_status |= KN_REPROCESS;
1282                                 continue;
1283                         }
1284
1285                         /*
1286                          * If the note is not empty we have to wait.
1287                          *
1288                          * XXX This is a real problem, certain process
1289                          *     and signal filters will bump kn_data for
1290                          *     already-processed notes more than once if
1291                          *     we restart the list scan.  FIXME.
1292                          */
1293                         kprintf("Warning: knote() on busy "
1294                                 "knote (ev=%d hint=%08lx)\n",
1295                                 kn->kn_filter, hint);
1296                         kn->kn_status |= KN_WAITING | KN_REPROCESS;
1297                         tsleep(kn, 0, "knotec", hz);
1298                         goto restart;
1299                 }
1300
1301                 /*
1302                  * Become the reprocessing master ourselves.
1303                  */
1304                 kn->kn_status |= KN_PROCESSING;
1305                 if (filter_event(kn, hint))
1306                         KNOTE_ACTIVATE(kn);
1307                 while (kn->kn_status & KN_REPROCESS) {
1308                         kn->kn_status &= ~KN_REPROCESS;
1309                         if (kn->kn_status & KN_DELETING) {
1310                                 knote_detach_and_drop_locked(kn);
1311                                 goto restart;
1312                         }
1313                         if (kn->kn_status & KN_WAITING) {
1314                                 kn->kn_status &= ~KN_WAITING;
1315                                 wakeup(kn);
1316                         }
1317                         if (filter_event(kn, hint))
1318                                 KNOTE_ACTIVATE(kn);
1319                 }
1320                 kn->kn_status &= ~KN_PROCESSING;
1321         }
1322         lwkt_reltoken(&kq_token);
1323 }
1324
1325 /*
1326  * Insert knote at head of klist.
1327  *
1328  * This function may only be called via a filter function and thus
1329  * kq_token should already be held and marked for processing.
1330  */
1331 void
1332 knote_insert(struct klist *klist, struct knote *kn)
1333 {
1334         KKASSERT(kn->kn_status & KN_PROCESSING);
1335         ASSERT_LWKT_TOKEN_HELD(&kq_token);
1336         SLIST_INSERT_HEAD(klist, kn, kn_next);
1337 }
1338
1339 /*
1340  * Remove knote from a klist
1341  *
1342  * This function may only be called via a filter function and thus
1343  * kq_token should already be held and marked for processing.
1344  */
1345 void
1346 knote_remove(struct klist *klist, struct knote *kn)
1347 {
1348         KKASSERT(kn->kn_status & KN_PROCESSING);
1349         ASSERT_LWKT_TOKEN_HELD(&kq_token);
1350         SLIST_REMOVE(klist, kn, knote, kn_next);
1351 }
1352
1353 /*
1354  * Remove all knotes from a specified klist
1355  *
1356  * Only called from aio.
1357  */
1358 void
1359 knote_empty(struct klist *list)
1360 {
1361         struct knote *kn;
1362
1363         lwkt_gettoken(&kq_token);
1364         while ((kn = SLIST_FIRST(list)) != NULL) {
1365                 if (kn->kn_status & KN_PROCESSING) {
1366                         kn->kn_status |= KN_WAITING | KN_REPROCESS;
1367                         tsleep(kn, 0, "kqepts", hz);
1368                         continue;
1369                 }
1370                 knote_detach_and_drop(kn);
1371         }
1372         lwkt_reltoken(&kq_token);
1373 }
1374
1375 /*
1376  * remove all knotes referencing a specified fd
1377  */
1378 void
1379 knote_fdclose(struct file *fp, struct filedesc *fdp, int fd)
1380 {
1381         struct knote *kn;
1382
1383         lwkt_gettoken(&kq_token);
1384 restart:
1385         SLIST_FOREACH(kn, &fp->f_klist, kn_link) {
1386                 if (kn->kn_kq->kq_fdp == fdp && kn->kn_id == fd) {
1387                         if (kn->kn_status & KN_PROCESSING) {
1388                                 kn->kn_status |= KN_WAITING | KN_REPROCESS;
1389                                 tsleep(kn, 0, "kqepts", hz);
1390                         } else {
1391                                 knote_detach_and_drop(kn);
1392                         }
1393                         goto restart;
1394                 }
1395         }
1396         lwkt_reltoken(&kq_token);
1397 }
1398
1399 /*
1400  * Low level attach function.
1401  *
1402  * The knote should already be marked for processing.
1403  */
1404 static void
1405 knote_attach(struct knote *kn)
1406 {
1407         struct klist *list;
1408         struct kqueue *kq = kn->kn_kq;
1409
1410         if (kn->kn_fop->f_flags & FILTEROP_ISFD) {
1411                 KKASSERT(kn->kn_fp);
1412                 list = &kn->kn_fp->f_klist;
1413         } else {
1414                 if (kq->kq_knhashmask == 0)
1415                         kq->kq_knhash = hashinit(KN_HASHSIZE, M_KQUEUE,
1416                                                  &kq->kq_knhashmask);
1417                 list = &kq->kq_knhash[KN_HASH(kn->kn_id, kq->kq_knhashmask)];
1418         }
1419         SLIST_INSERT_HEAD(list, kn, kn_link);
1420         TAILQ_INSERT_HEAD(&kq->kq_knlist, kn, kn_kqlink);
1421 }
1422
1423 /*
1424  * Low level drop function.
1425  *
1426  * The knote should already be marked for processing.
1427  */
1428 static void
1429 knote_drop(struct knote *kn)
1430 {
1431         struct kqueue *kq;
1432         struct klist *list;
1433
1434         kq = kn->kn_kq;
1435
1436         if (kn->kn_fop->f_flags & FILTEROP_ISFD)
1437                 list = &kn->kn_fp->f_klist;
1438         else
1439                 list = &kq->kq_knhash[KN_HASH(kn->kn_id, kq->kq_knhashmask)];
1440
1441         SLIST_REMOVE(list, kn, knote, kn_link);
1442         TAILQ_REMOVE(&kq->kq_knlist, kn, kn_kqlink);
1443         if (kn->kn_status & KN_QUEUED)
1444                 knote_dequeue(kn);
1445         if (kn->kn_fop->f_flags & FILTEROP_ISFD) {
1446                 fdrop(kn->kn_fp);
1447                 kn->kn_fp = NULL;
1448         }
1449         knote_free(kn);
1450 }
1451
1452 /*
1453  * Low level enqueue function.
1454  *
1455  * The knote should already be marked for processing.
1456  */
1457 static void
1458 knote_enqueue(struct knote *kn)
1459 {
1460         struct kqueue *kq = kn->kn_kq;
1461
1462         KASSERT((kn->kn_status & KN_QUEUED) == 0, ("knote already queued"));
1463         TAILQ_INSERT_TAIL(&kq->kq_knpend, kn, kn_tqe);
1464         kn->kn_status |= KN_QUEUED;
1465         ++kq->kq_count;
1466
1467         /*
1468          * Send SIGIO on request (typically set up as a mailbox signal)
1469          */
1470         if (kq->kq_sigio && (kq->kq_state & KQ_ASYNC) && kq->kq_count == 1)
1471                 pgsigio(kq->kq_sigio, SIGIO, 0);
1472
1473         kqueue_wakeup(kq);
1474 }
1475
1476 /*
1477  * Low level dequeue function.
1478  *
1479  * The knote should already be marked for processing.
1480  */
1481 static void
1482 knote_dequeue(struct knote *kn)
1483 {
1484         struct kqueue *kq = kn->kn_kq;
1485
1486         KASSERT(kn->kn_status & KN_QUEUED, ("knote not queued"));
1487         TAILQ_REMOVE(&kq->kq_knpend, kn, kn_tqe);
1488         kn->kn_status &= ~KN_QUEUED;
1489         kq->kq_count--;
1490 }
1491
1492 static void
1493 knote_init(void)
1494 {
1495         knote_zone = zinit("KNOTE", sizeof(struct knote), 0, 0, 1);
1496 }
1497 SYSINIT(knote, SI_SUB_PSEUDO, SI_ORDER_ANY, knote_init, NULL)
1498
1499 static struct knote *
1500 knote_alloc(void)
1501 {
1502         return ((struct knote *)zalloc(knote_zone));
1503 }
1504
1505 static void
1506 knote_free(struct knote *kn)
1507 {
1508         zfree(knote_zone, kn);
1509 }