sys/kern/subr_sleepqueue.c

   1 /*
   2  * Copyright (c) 2023 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 /*
  35  * DragonFly implementation of the FreeBSD sleepq*() API.  FreeBSD's sleepq*()
  36  * API differs from our tsleep*() API in several major ways.
  37  *
  38  * ONLY USE THIS FOR FREEBSD COMPATIBILITY, E.G. THE LINUX KPI
  39  *
  40  * - Explicit interlock via sleepq_lock(wchan)
  41  * - Single global wchan hash table
  42  * - Explicit blocking counts
  43  * - Expects all blockers on the same wchan to be of the same type
  44  *
  45  * In addition, the API calls have a ton of unnecessary redundancy which
  46  * creates problems with using on-stack structures for things.  To make
  47  * ends meat, DragonFly records information in the thread structure and
  48  * only enacts the actual operation when the thread issues a *wait*() API
  49  * call.  Only the spin interlock is handled in real-time.
  50  */
  51
  52 #include "opt_ddb.h"
  53
  54 #include <sys/cdefs.h>
  55 #include <sys/param.h>
  56 #include <sys/systm.h>
  57 #include <sys/lock.h>
  58 #include <sys/caps.h>
  59 #include <sys/malloc.h>
  60 #include <sys/queue.h>
  61 #include <sys/sleepqueue.h>
  62 #include <sys/objcache.h>
  63 #include <sys/sysctl.h>
  64
  65 #include <sys/time.h>
  66
  67 #include <machine/atomic.h>
  68
  69 #ifdef DDB
  70 #include <ddb/ddb.h>
  71 #endif
  72
  73 #include <sys/signal2.h>
  74 #include <sys/thread2.h>
  75 #include <sys/spinlock2.h>
  76 #include <sys/mutex2.h>
  77
  78 #include <vm/vm_extern.h>
  79
  80 #define SLEEPQ_HSIZE            1024
  81 #define SLEEPQ_HMASK            (SLEEPQ_HSIZE - 1)
  82 #define SLEEPQ_HASH(wchan)      ((((uintptr_t)(wchan) >> 10) ^ \
  83                                   ((uintptr_t)(wchan) & SLEEPQ_HMASK)))
  84
  85 #define SLEEPQ_LOOKUP(wchan)    &sleepq_chains[SLEEPQ_HASH(wchan)]
  86 #define SLEEPQ_NRQUEUES         2
  87 #define SLEEPQ_FREEPERSLOT      4
  88
  89 struct sleepqueue_wchan;
  90
  91 struct sleepqueue_chain {
  92         struct spinlock sc_spin;
  93         TAILQ_HEAD(, sleepqueue_wchan) sc_wchead;
  94         u_int   sc_free_count;
  95 };
  96
  97 struct sleepqueue_wchan {
  98         TAILQ_ENTRY(sleepqueue_wchan) wc_entry;
  99         const void *wc_wchan;
 100         struct sleepqueue_chain *wc_sc;
 101         u_int   wc_refs;
 102         int     wc_type;
 103         u_int   wc_blocked[SLEEPQ_NRQUEUES];
 104 };
 105
 106 static struct sleepqueue_chain sleepq_chains[SLEEPQ_HSIZE];
 107 static MALLOC_DEFINE(M_SLEEPQ, "sleepq", "fbsd sleepq api");
 108 static struct objcache *sleepq_wc_cache;
 109
 110 /*
 111  * Return existing wchan, assert not NULL.
 112  */
 113 static __inline
 114 struct sleepqueue_wchan *
 115 sleepq_wclookup(const void *wchan)
 116 {
 117         struct sleepqueue_chain *sc;
 118         struct sleepqueue_wchan *wc;
 119
 120         sc = SLEEPQ_LOOKUP(wchan);
 121         KKASSERT(spin_held(&sc->sc_spin));
 122         TAILQ_FOREACH(wc, &sc->sc_wchead, wc_entry) {
 123                 if (wc->wc_wchan == wchan)
 124                         return(wc);
 125         }
 126         panic("sleepq_wclookup: wchan %p not found\n", wc);
 127
 128         return NULL;    /* not reached */
 129 }
 130
 131 /*
 132  * Early initialization of sleep queues
 133  */
 134 static void
 135 init_sleepqueues(void)
 136 {
 137         int i;
 138
 139         for (i = 0; i < SLEEPQ_HSIZE; ++i) {
 140                 spin_init(&sleepq_chains[i].sc_spin, "sleepq");
 141                 TAILQ_INIT(&sleepq_chains[i].sc_wchead);
 142         }
 143         /*thread0.td_sleepqueue = sleepq_alloc();*/
 144
 145         sleepq_wc_cache = objcache_create_simple(M_SLEEPQ,
 146                                             sizeof(struct sleepqueue_wchan));
 147
 148 }
 149 SYSINIT(sysinit_sleepqueues, SI_BOOT2_LWKT_INIT, SI_ORDER_SECOND,
 150         init_sleepqueues, NULL);
 151
 152 /*
 153  * DragonFlyBSD Interface Functions
 154  *
 155  * Setup and teardown sleepq related thread structures
 156  *
 157  * sleepq_alloc() - not applicable
 158  * sleepq_free()  - not applicable
 159  */
 160 void
 161 sleepq_setup_thread(struct thread *td)
 162 {
 163 }
 164
 165 void
 166 sleepq_teardown_thread(struct thread *td)
 167 {
 168 }
 169
 170 /*
 171  * Lock the wchan, creating the structure if necessary.  Returns with
 172  * the spin-lock held.
 173  *
 174  * Also used as an interlock, so we need to actually lock something here.
 175  */
 176 void
 177 sleepq_lock(const void *wchan)
 178 {
 179         struct sleepqueue_chain *sc;
 180         struct sleepqueue_wchan *wc;
 181
 182         sc = SLEEPQ_LOOKUP(wchan);
 183         spin_lock(&sc->sc_spin);
 184
 185         for (;;) {
 186                 /*
 187                  * Look for the wchan, if not found then allocate one from
 188                  * the existing in-list cache if available.
 189                  */
 190                 TAILQ_FOREACH(wc, &sc->sc_wchead, wc_entry) {
 191                         if (wc->wc_wchan == wchan) {
 192                                 ++wc->wc_refs;
 193                                 return;
 194                         }
 195                         if (wc->wc_wchan == NULL) {
 196                                 wc->wc_wchan = wchan;
 197                                 ++wc->wc_refs;
 198                                 --sc->sc_free_count;
 199                                 return;
 200                         }
 201                 }
 202
 203                 /*
 204                  * Not found and no free entries available, allocate
 205                  * a new, free wc, then relock and repeat the search.
 206                  */
 207                 spin_unlock(&sc->sc_spin);
 208                 wc = objcache_get(sleepq_wc_cache, M_WAITOK);
 209                 KKASSERT(wc->wc_wchan == NULL && wc->wc_refs == 0);
 210                 wc->wc_sc = sc;
 211                 spin_lock(&sc->sc_spin);
 212                 TAILQ_INSERT_TAIL(&sc->sc_wchead, wc, wc_entry);
 213                 ++sc->sc_free_count;
 214                 /* loop re-search */
 215         }
 216 }
 217
 218 /*
 219  * Unlock the sleep queue chain associated with a given wait channel.
 220  */
 221 void
 222 sleepq_release(const void *wchan)
 223 {
 224         struct sleepqueue_chain *sc;
 225         struct sleepqueue_wchan *wc;
 226
 227         wc = sleepq_wclookup(wchan);
 228         sc = wc->wc_sc;
 229         KKASSERT(wc->wc_refs > 0);
 230         if (--wc->wc_refs == 0) {
 231                 /* just sanity-check one for brevity */
 232                 KKASSERT(wc->wc_blocked[0] == 0);
 233                 wc->wc_wchan = NULL;
 234                 wc->wc_type = 0;
 235                 ++sc->sc_free_count;
 236         }
 237
 238         spin_unlock(&sc->sc_spin);
 239 }
 240
 241 /*
 242  * Place the current thread on the specified wait channel and sub-queue.
 243  *
 244  * The caller must be holding the wchan lock and it will remain locked
 245  * on return.  The caller must follow-up with a sleepq_*wait*() call.
 246  *
 247  * If INVARIANTS is enabled, then it associates the passed in lock with
 248  * the sleepq to make sure it is held when that sleep queue is woken up
 249  * (XXX not implemented)
 250  */
 251 void
 252 sleepq_add(const void *wchan, struct lock_object *lock, const char *wmesg,
 253            int flags, int queue)
 254 {
 255         struct sleepqueue_wchan *wc;
 256         struct thread *td;
 257         int domain;
 258
 259         /*
 260          * Locate the wc (also asserts that the lock is held).  Bump
 261          * wc->wc_refs and wc->wc_blocked[queue] to indicate that the
 262          * thread has been placed on the sleepq.
 263          */
 264         wc = sleepq_wclookup(wchan);
 265         ++wc->wc_refs;
 266         ++wc->wc_blocked[queue];
 267         wc->wc_type = flags & SLEEPQ_TYPE;
 268
 269         /*
 270          * tsleep_interlock() sets TDF_TSLEEPQ, sets td_wchan, and td_wdomain,
 271          * and places the thread on the appropriate sleepq.
 272          */
 273         td = curthread;
 274         td->td_wmesg = wmesg;
 275         domain = PDOMAIN_FBSD0 + queue * PDOMAIN_FBSDINC;
 276         tsleep_interlock(wchan, domain);
 277
 278         /*
 279          * Clear timeout to discern a possible later sleepq_set_timeout_sbt()
 280          * call.
 281          */
 282         td->td_sqwc = wc;
 283         td->td_sqtimo = 0;
 284         td->td_sqqueue = queue;
 285 }
 286
 287 /*
 288  * Set a timeout for the thread after it has been added to a wait channel.
 289  */
 290 void
 291 sleepq_set_timeout_sbt(const void *wchan, sbintime_t sbt, sbintime_t pr,
 292                        int flags)
 293 {
 294         struct sleepqueue_wchan *wc;
 295         struct thread *td;
 296
 297         td = curthread;
 298         wc = td->td_sqwc;
 299         KKASSERT(wc && wc->wc_wchan == wchan);
 300         td->td_sqtimo = sbticks + sbt;
 301 }
 302
 303 /*
 304  * Return the number of actual sleepers for the specified queue.
 305  *
 306  * Caller must be holding the wchan locked
 307  */
 308 u_int
 309 sleepq_sleepcnt(const void *wchan, int queue)
 310 {
 311         struct sleepqueue_wchan *wc;
 312
 313         wc = sleepq_wclookup(wchan);
 314         return (wc->wc_blocked[queue]);
 315 }
 316
 317 static __inline
 318 int
 319 _sleepq_wait_begin(struct thread *td, struct sleepqueue_chain *sc,
 320                    struct sleepqueue_wchan *wc, sbintime_t timo, int tflags)
 321 {
 322         int domain;
 323         int ret;
 324
 325         spin_unlock(&sc->sc_spin);
 326
 327         domain = PDOMAIN_FBSD0 + td->td_sqqueue * PDOMAIN_FBSDINC;
 328         if (timo) {
 329                 timo -= sbticks;
 330                 if (timo > 0) {
 331                         ret = tsleep(td->td_wchan, tflags, td->td_wmesg, timo);
 332                 } else {
 333                         ret = EWOULDBLOCK;
 334                 }
 335         } else {
 336                 ret = tsleep(td->td_wchan, tflags, td->td_wmesg, 0);
 337         }
 338
 339         return ret;
 340 }
 341
 342 /*
 343  * Wait for completion
 344  */
 345 static __inline
 346 void
 347 _sleepq_wait_complete(struct thread *td, struct sleepqueue_chain *sc,
 348                       struct sleepqueue_wchan *wc)
 349 {
 350         struct sleepqueue_wchan *wcn;
 351
 352         td->td_sqwc = NULL;
 353         spin_lock(&sc->sc_spin);
 354         --wc->wc_blocked[td->td_sqqueue];
 355         if (--wc->wc_refs == 0) {
 356                 wc->wc_wchan = NULL;
 357                 wc->wc_type = 0;
 358                 ++sc->sc_free_count;
 359                 if (sc->sc_free_count <= SLEEPQ_FREEPERSLOT) {
 360                         wcn = TAILQ_NEXT(wc, wc_entry);
 361                         if (wcn && wcn->wc_wchan) {
 362                                 TAILQ_REMOVE(&sc->sc_wchead, wc, wc_entry);
 363                                 TAILQ_INSERT_TAIL(&sc->sc_wchead, wc, wc_entry);
 364                         }
 365                         spin_unlock(&sc->sc_spin);
 366                 } else {
 367                         --sc->sc_free_count;
 368                         TAILQ_REMOVE(&sc->sc_wchead, wc, wc_entry);
 369                         spin_unlock(&sc->sc_spin);
 370                         objcache_put(sleepq_wc_cache, wc);
 371                 }
 372         } else {
 373                 spin_unlock(&sc->sc_spin);
 374         }
 375 }
 376
 377 /*
 378  * Various combinations of wait until unblocked, with and without
 379  * signaling and timeouts.
 380  *
 381  * The wchan lock must be held by the caller and will be released upon
 382  * return.
 383  *
 384  * NOTE: tsleep_interlock() was already issued by sleepq_add().
 385  */
 386 void
 387 sleepq_wait(const void *wchan, int pri)
 388 {
 389         struct sleepqueue_chain *sc;
 390         struct sleepqueue_wchan *wc;
 391         struct thread *td;
 392
 393         td = curthread;
 394         wc = td->td_sqwc;
 395         KKASSERT(wc != NULL && wc->wc_wchan == wchan);
 396         sc = wc->wc_sc;
 397
 398         (void)_sleepq_wait_begin(td, sc, wc, 0, PINTERLOCKED);
 399         _sleepq_wait_complete(td, sc, wc);
 400 }
 401
 402 int
 403 sleepq_wait_sig(const void *wchan, int pri)
 404 {
 405         struct sleepqueue_chain *sc;
 406         struct sleepqueue_wchan *wc;
 407         struct thread *td;
 408         int ret;
 409
 410         td = curthread;
 411         wc = td->td_sqwc;
 412         KKASSERT(wc != NULL && wc->wc_wchan == wchan);
 413         sc = wc->wc_sc;
 414
 415         ret = _sleepq_wait_begin(td, sc, wc, 0, PINTERLOCKED | PCATCH);
 416         _sleepq_wait_complete(td, sc, wc);
 417
 418         return ret;
 419 }
 420
 421 int
 422 sleepq_timedwait(const void *wchan, int pri)
 423 {
 424         struct sleepqueue_chain *sc;
 425         struct sleepqueue_wchan *wc;
 426         struct thread *td;
 427         int ret;
 428
 429         td = curthread;
 430         wc = td->td_sqwc;
 431         KKASSERT(wc != NULL && wc->wc_wchan == wchan);
 432         sc = wc->wc_sc;
 433
 434         ret = _sleepq_wait_begin(td, sc, wc, td->td_sqtimo, PINTERLOCKED);
 435         _sleepq_wait_complete(td, sc, wc);
 436
 437         return ret;
 438 }
 439
 440 int
 441 sleepq_timedwait_sig(const void *wchan, int pri)
 442 {
 443         struct sleepqueue_chain *sc;
 444         struct sleepqueue_wchan *wc;
 445         struct thread *td;
 446         int ret;
 447
 448         td = curthread;
 449         wc = td->td_sqwc;
 450         KKASSERT(wc != NULL && wc->wc_wchan == wchan);
 451         sc = wc->wc_sc;
 452
 453         ret = _sleepq_wait_begin(td, sc, wc, td->td_sqtimo,
 454                                  PINTERLOCKED | PCATCH);
 455         _sleepq_wait_complete(td, sc, wc);
 456
 457         return ret;
 458 }
 459
 460 /*
 461  * Returns the type of sleepqueue given a waitchannel.  Returns 0 if
 462  * sleepq_add() has not been called no the wchan.
 463  *
 464  * wchan must be locked.
 465  */
 466 int
 467 sleepq_type(const void *wchan)
 468 {
 469         struct sleepqueue_wchan *wc;
 470         int type;
 471
 472         wc = sleepq_wclookup(wchan);
 473         type = wc->wc_type;
 474
 475         return type;
 476 }
 477
 478 /*
 479  * Wakeup one thread sleeping on a wait channel.
 480  *
 481  * DragonFly: Presumably callers also deal with multiple wakeups,
 482  *            our wakeup_domaoin_one() function is a bit non-deterministic.
 483  *
 484  *            Nominally returns whether the swapper should be woken up which
 485  *            is not applicable to DragonFlyBSD.
 486  */
 487 int
 488 sleepq_signal(const void *wchan, int flags, int pri, int queue)
 489 {
 490         int domain;
 491
 492         domain = PDOMAIN_FBSD0 + queue * PDOMAIN_FBSDINC;
 493         wakeup_domain_one(wchan, domain);
 494
 495         return 0;
 496 }
 497
 498 /*
 499  * Resume everything sleeping on the specified wait channel and queue.
 500  *
 501  * Nominally returns whether the swapper should be woken up which is not
 502  * applicable to DragonFlyBSD.
 503  */
 504 int
 505 sleepq_broadcast(const void *wchan, int flags, int pri, int queue)
 506 {
 507         int domain;
 508
 509         domain = PDOMAIN_FBSD0 + queue * PDOMAIN_FBSDINC;
 510         wakeup_domain(wchan, domain);
 511
 512         return 0;
 513 }